中级提升三
题目一：机器移动物品
- 题目：
- 情况分析：
（1）若物品的总数为sum，sum % n != 0，直接返回 -1
（2）avg = sum / n，将机器分为三部分： 左 | 中 | 右；其中左右左右不一定只有一个机器，将左右看为两个整体，中间只有一个机器。分别算出目前左右两部分机器上物品的数量 - avg的值，记为 left，right
（3）若left < 0，right < 0；则至少需要移动 | left | + | right |
（4）若left > 0 ,right > 0；则至少需要移动 max(left，right)
（5）若一正一负，则至少需要移动 max(| left |，| right |)
（6）综上所述：只有均小于0为：| left | + | right |；其余均为：max(| left |，| right |) - 思路：
根据情况分析，将每个机器均尝试作为中间位置计算至少需要移动的次数，其中的最大值就是整个的最小移动次数 - 代码实现：
public static int minOps(int[] arr){ if (arr == null || arr.length == 0){ return 0; } int size = arr.length; int sum = 0; for (int i : arr) { sum += i; } if (sum % size != 0){ return -1; } int avg = sum / size; //每个位置应该的数量 int leftSum = 0;//记录左侧的数目 int num = 0; for (int i = 0; i < size; i++){ //left与right计算，分别表示左右与标准的差值 int left = leftSum - avg * i; int right = (sum - leftSum - arr[i]) - (size - i - 1) * avg; if (left < 0 && right < 0){ num = Math.max(num, Math.abs(left) + Math.abs(right)); }else { num = Math.max(num, Math.max(Math.abs(left), Math.abs(right))); } leftSum += arr[i]; } return num; }
题目二：螺旋打印矩阵
- 题目：
- 思路：
（1）每次确定左上角与右下的点坐标，打印两点构成的四条边，以及可能在同一水平线或者竖直线
（2）再将两点分别向右下方，左上方移动
（3）当两点相互错开后停止
- 代码：
public static void printEdge(int[][] martix){ //初始的两点坐标 int leftX = 0; int leftY = 0; int rightX = martix.length - 1; int rightY = martix[0].length - 1; while (leftX <= rightX && leftY <= rightY){ //两点的移动 process(martix, leftX++, leftY++, rightX--, rightY--); } } public static void process(int[][] martix, int leftX, int leftY, int rightX, int rightY){ //打印左上角与右下角构成的边 if (leftX == rightX){ //一条竖线 for (int i = leftY; i <= rightY; i++){ System.out.print(martix[leftX][i] + " "); } }else if (leftY == rightY){ //一条横线 for (int i = leftX; i <= rightX; i++){ System.out.print(martix[i][leftY] + " "); } }else { //一般情况打印四条边 for (int i = leftY; i < rightY; i++){ System.out.print(martix[leftX][i] + " "); } for (int i = leftX; i < rightX; i++){ System.out.print(martix[i][rightY] + " "); } for (int i = rightY; i > leftY; i--){ System.out.print(martix[rightX][i] + " "); } for (int i = rightX; i > leftX; i--){ System.out.print(martix[i][leftY] + " "); } } }
题目三：旋转矩阵
- 题目：
- 思路：
（1）如图：因为矩阵为正方形，所以可以将整个的旋转看为一层一层的调整，每次的交换只在每层的内部发生
（2）因为是整体转动90度，又可以在一层的内部进行分组，如图：圆，正方形，三角形为一组，每次又是在组内进行交换
（3）可以发现不管有多少组，每组中一定有四个元素，将4个元素依次交换，便可以实现旋转
（4）第一组便是对应的四个角，通过四个角可以确定所有元素的交换次序：第一组，1：（a，b），4：（a，d），16：（c，d），13：（c，b）；那么第二组2：（a，b + 1)，8：（c + 1，d），15：（c，d - 1），9：（c - 1，b）
（5）一层的组数的可以通过右下角x - 左上角x确定
（6）每次同时移动四个角，不相交是打印，确定层数 - 代码：
public static void rotationMatrix(int[][] martix){ int leftX = 0; int leftY = 0; int rightX = martix.length - 1; int rightY = martix[0].length - 1; while (leftX <= rightX && leftY <= rightY){ process(martix, leftX++, leftY++, rightX--, rightY--); } } public static void process(int[][] martix, int leftX, int leftY, int rightX, int rightY){ //一层的交换 for (int i = 0; i < rightX - leftX; i++){ //一组的交换 int temp = martix[leftX][leftY + i]; martix[leftX][leftY + i] = martix[rightX - i][leftY]; martix[rightX - i][leftY] = martix[rightX][rightY - i]; martix[rightX][rightY - i] = martix[leftX + i][rightY]; martix[leftX + i][rightY] = temp; } }
题目四：zigzag的方式打印矩阵
- 题目：
- 思路：
（1）双框A，B，A每次向右移动，到边界后向下移动；B每次向下移动，到达边界后向右移动；每次A，B同时移动一步
（2）打印A，B之间的斜线，一次从A到B，一次从B到A轮流进行，可以使用一个boolean值控制
- 代码：
public static void zigzag(int[][] martix){ int AX = 0; int AY = 0; int BX = 0; int BY = 0; int endX = martix[0].length - 1; int endY = martix.length - 1; boolean flag = true; //flag控制打印方向 while (AY != endY){ process(martix, AX, AY, BX, BY, flag); AX = AX == endX ? AY++ : AX + 1; BY = BY == endY ? BX++ : BY + 1; flag = !flag; } } public static void process(int[][] martix, int AX, int AY, int BX, int BY, boolean flag){ //flag == true，从A到B；flag == false，从B到A if (flag){ while (AX != BX - 1){ System.out.print(martix[AX--][AY++] + " "); } }else { while (AX != BX - 1){ System.out.print(martix[BX++][BY--] + " "); } } }
题目五：字符串长度的最小操作数
- 题目：
- 问题分析：
（1）若n为质数，只能调用最多一次操作一，因为多次调用调用操作一：m = k个“a”，s = 2k个“a”，此时一定无法达到n为质数，有因为只掉一次操作一与掉一次操作二的效果相同；故：若n为质数就一直调用操作二，结果就是n - 1次
（2）若n为合数，n一定为几个质数的成绩若 n = x * y * z；x，y，z均为质数，结合操作一总的次数就是（x - 1）+（y - 1）+（z - 1）；即：质数相加 - 质数的个数
public static int minOps(int n){ if (n < 2){ return 0; } if (isPrim(n)){ return n - 1; } int sum = 0; int count = 0; for (int i = 2; i <= n; i++){ while (n % i == 0){ sum += i; count++; n /= i; } } return sum - count; } public static boolean isPrim(int n){ if (n < 2){ return false; } int max = (int) Math.sqrt((double)n); for (int i = 2; i <= max; i++){ if (n % i == 0){ return false; } } return true; }
