左神中期提升班四

1.超级洗衣机（leetcode517）

贪心策略：本题很容易就求出能否使得洗衣机能否满足的情况，之后遍历每个节点，以该节点为中心，求出使得该节点两边整体平均所需要的最小步数。

设节点N左边高出平均值avg的值为left右边为right

1. 若left<0&&right<0 此时两边都需要节点N补充，至少需要left+right步骤

2. 若left和right至少一个大于0 ，至少需要max（|left|，|right|）步  

经过上面计算求出了以某个节点为中心，使得该节点两边整体平均所需要的最小步数。若要求出每个节点平均，至少使其能够分块平均，要满足每个节点都能分块平均，所以要满足其中的最大值。

在满足最大的分块平均时，其左右两边都是可以并行增删使得节点值靠近平均数，通过自己试算，都可以通过并行使得在满足最大的分块平均时进行调用。

 public int findMinMoves(int[] machines) {int length = machines.length;int sum = 0;for(int i = 0;i<length;i++){sum+=machines[i];}if(sum%length!=0)return -1;int avg = sum/length;int leftSum = 0;int ans = 0;for(int i = 0;i<length;i++){int left = leftSum-avg*i;int right = (sum-leftSum-machines[i])-avg*(length-1-i);if(left<0&&right<0){ans=Math.max(ans,Math.abs(left+right));}else{ans=Math.max(ans,Math.max(Math.abs(left),Math.abs(right)));}leftSum+=machines[i];}return ans;}

2、二维数组旋转问题zigzag打印（整体思想）

思路：打印时按照对角线打印，所以将对角线看成一个个独立的整体，分别遍历对角线 

private static void zigzag(int[][] matrix) {int upX = 0;int upY = 0;int downX = 0;int downY = 0;boolean flag = true;while(upX<=matrix.length){printM(matrix,upX,upY,downX,downY,flag);if (upY<matrix[0].length-1){upY++;}else {upX++;}if (downX<matrix.length-1){downX++;}else {downY++;}flag=!flag;}}private static void printM(int[][] matrix, int upX, int upY, int downX, int downY, boolean flag) {if (flag){while (downX!=(upX-1)){System.out.println(matrix[downX--][downY++]);}}else {while (upX!=(downX+1)){System.out.println(matrix[upX++][upY--]);}}}

3.螺旋打印数组(整体思想)

 思路：同上题类型，将数组一层一层地看成一个整体，这样就只用考虑每一层的情况

private static void rotatePrint(int[][] matrix) {int upX = 0;int upY = 0;int downX = matrix.length-1;int downY = matrix[0].length-1;while (upX<=downX&&upY<=downY){PrintM(matrix,upX,upY,downX,downY);upX+=1;upY+=1;downX-=1;downY-=1;}}private static void PrintM(int[][] matrix, int upX, int upY, int downX, int downY) {if (upX==downX){for (int i = upY; i <=downY ; i++) {System.out.println(matrix[upX][i]);}}else if (upY==downY){for (int i = upX; i <=downX; i++) {System.out.println(matrix[i][upY]);}}else{for (int i = upY;  i<downY ; i++) {System.out.println(matrix[upX][i]);}for (int i = upX; i<downX; i++) {System.out.println(matrix[i][downY]);}for (int i = downY; i >upX; i--) {System.out.println(matrix[downX][i]);}for (int i = downX; i > upX; i--) {System.out.println(matrix[i][upY]);}}}

4.顺时针旋转数组

思考：本题同样用到整体思想，一个n×n矩阵，将矩阵按不同层分组，分成n/2组，在每一组内，按照0 3 15 12 0的顺序依次旋转，第一行德1、2同理，共需循环n-1次，设开始点为M[a][i],则一次循环内的点依次为M[a+1][d] 、M[c][d-i]、M[c-i][b]; 

 private static void rotate1(int[][] matrix) {int upX = 0;int upY = 0;int downX = matrix.length-1;int downY = matrix[0].length-1;while (upX<downX){rotate2(matrix,upX,upY,downX,downY);upX+=1;upY+=1;downX-=1;downY-=1;}}private static void rotate2(int[][] matrix, int a, int b, int c, int d) {for (int i = 0; i < d-b; i++) {int cur = matrix[a][b+i];int next = matrix[a+i][d];matrix[a+i][d]=cur;cur = next;next = matrix[c][d-i];matrix[c][d-i]=cur;cur=next;next = matrix[c-i][b];matrix[c-i][b] = cur;matrix[a][b+i]=next;}}

5.质数问题 

 思路：设某一步时 m=k*a;此时再经过一次步骤一，m=ka,s=2ka;m由s决定，s只能翻倍或+m，则以后s=n*k*m,s必为k的倍数，

当k==1时，nk可以为质数，

 k!=1时，nk只能为合数 

所以s长度为n时，若n为质数，只能第一步使用操作一，其最终步数只能为n-1；

若n为合数则可以将n分为若干个质数的积，n=k1*k2*k3*k4....;若要使得最小的操作步骤，则应该尽可能的调用步骤一，将n分成质数的相乘操作正好对应步骤一的翻倍操，如将k1*k2*k3看成整体，要翻k4倍，k4是质数；此时先调用步骤一：m=(k1*k2*k3),s =2（k1*k2*k3），再调用n-2步操作二，共k4-1步；这一步相当于于将多个a看成一个a拼到长度为s

private static int minOps(int n) {if(n<2)return 0;if(isPrim(n))return n-1;int[] result = lengthAndSum(n);return result[0]-result[1];}private static int[] lengthAndSum(int n) {int sum=0;int count =0;for (int i = 2; i <=n; i++) {while (n%i==0){count+=1;sum+=i;n=n/i;}}return new int[]{sum, count};}private static boolean isPrim(int n) {for (int i = 2; i <Math.sqrt(n); i++) {if (n%2==0)return false;}return true;}

6.自定义堆排序问题（使用排行榜方式解决）

思路： 本题可以定义一个大根堆找出最大的前k个，同时也可以用一个大小为k的小根堆，小根堆顶为最小值，若某个元素个数大于最小值，才可以进入小根堆。本题采用的一种动态方式，不是最简单解决方法，但是可以通过遍历不断更新排行榜。

 private static void getMost(char[] arr, int k) {char[] heap = new char[k];//堆中节点个数int index = 0;for (int i = 0; i < arr.length; i++) {char c= arr[i];//元素在堆中位置int preIndex = -1;if (!mapCount.containsKey(c)){mapCount.put(c,1);mapLocate.put(c,-1);}else {mapCount.put(c, mapCount.get(c)+1);preIndex = mapLocate.get(c);}//堆中无此节点if (preIndex==-1){if(index==k){// 与守门员判断if (mapCount.get(heap[0])<mapCount.get(c)){mapLocate.put(heap[0],-1);heap[0] = c;heapify(0,index, heap);}}else{//直接加入heap[index]=c;mapLocate.put(c,index);heapInsert(index++,c,heap);}}else{heapify(preIndex,index,heap);}}System.out.println(Arrays.toString(heap));}private static void heapify(int k, int index, char[] heap) {char c = heap[k];int count = mapCount.get(c);int i = 2*k+1;while(i<index){int minIndex = i+1<index&&mapCount.get(heap[i+1])<mapCount.get(heap[i])?i+1:i;int min = mapCount.get(heap[minIndex])<count?minIndex:k;if (min==k){break;}mapLocate.put(heap[min],k);heap[k]= heap[min];k=min;i=2*k+1;}heap[k]=c;}private static void heapInsert(int i, char c, char[] heap) {while (mapLocate.get(heap[(i-1)/2])>mapLocate.get(heap[i])){mapLocate.put(heap[(i-1)/2],i);heap[i]=heap[(i-1)/2];i = (i-1)/2;}heap[i]=c;mapLocate.put(c,i);}