【21】中级提升

本文主要是介绍【21】中级提升，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目一

	public static int MinOps(int[] arr) {if (arr == null || arr.length == 0) {return 0;}int size = arr.length; // 获取数组长度int sum = 0; // 统计数组元素和for (int i = 0; i < size; i++) { // 累加sum += arr[i]; }if (sum % size != 0) { // 判断是否可以分配平均return -1;}int avg = sum / size; // 求平均值int leftSum = 0; // 第i个位置左侧的累加和int ans = 0; // 返回至少轮次// ans就是所有位置的情况中取最坏的，但最糟糕的情况解决了，较好的情况也一定解决了for (int i = 0; i < arr.length; i++) { // 从左到右模型 // 负值需要输入 正值需要输出（i位置左侧情况）int L = leftSum - i * avg;// 负值需要输入 正值需要输出（i位置右侧情况）int R =  (sum - leftSum - arr[i]) - (size - i - 1) * avg;if (L < 0 && R < 0) { // 左侧和右侧都<0// i位置需要分别向左侧和右侧输出东西，但一轮只能输出一个，所以需要|L|+|R|伦次ans = Math.max(ans, Math.abs(L) + Math.abs(R));} else {ans = Math.max(ans, Math.max(Math.abs(L), Math.abs(R)));}leftSum += arr[i];}return ans;}

题目三

public static void printMatrixZigZag(int[][] arr) {if(arr==null || arr[0]==null )return;int x1=0, y1=0, x2=0, y2=0;System.out.print(arr[x1][y1]+" ");int m=arr.length-1, n=arr[0].length-1;boolean flag=false;while(true) {x1=y1==n?x1+1:x1;y1=y1==n?y1:y1+1;y2=x2==m?y2+1:y2;x2=x2==m?x2:x2+1;if(x1>m||x2>m||y1>n||y2>n)break;//System.out.println("("+x1+","+y1+") ("+x2+","+y2+")");process(arr, x1, y1, x2, y2, flag);flag=!flag;}}// flag = false 从右上往左下打印，flag = true 从左下往右上打印public static void process(int[][] arr, int x1, int y1, int x2, int y2, boolean flag) {int tx1=x1, ty1=y1, tx2=x2, ty2=y2;if(flag==false) {while(tx1<=tx2) {System.out.print(arr[tx1++][ty1--]+" ");}}else {while(tx1<=tx2) {System.out.print(arr[tx2--][ty2++]+" ");}}}public static void main(String[] args) {int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };printMatrixZigZag(matrix);}

补充：螺旋打印

	public static void printMatrixZigZag(int[][] arr) {int x1=0, y1=0;int x2=arr.length-1, y2=arr[0].length-1;while(x1<=x2&&y1<=y2) {process(arr, x1++, y1++, x2--, y2--);}}public static void process(int[][] arr, int x1, int y1, int x2, int y2) {if(x1==x2) {for(int i=y1;i<=y2;i++) {System.out.print(arr[x1][i]+" ");}}else if(y1==y2) {for(int i=x1;i<=x2;i++) {System.out.print(arr[i][y1]+" ");}}else {int endR=x1, endC=y1;while(endR!=y2)System.out.print(arr[x1][endR++]+" ");while(endC!=x2)System.out.print(arr[endC++][y2]+" ");while(endR!=y1)System.out.print(arr[x2][endR--]+" ");while(endC!=x1)System.out.print(arr[endC--][y1]+" ");}}

题目四

	public static void rotate(int[][] matrix) {int tR = 0;int tC = 0;int dR = matrix.length - 1;int dC = matrix[0].length - 1;while (tR < dR) {rotateEdge(matrix, tR++, tC++, dR--, dC--);}}// 旋转以点(tR, tC) (dR, dC)确定出的边框public static void rotateEdge(int[][] m, int tR, int tC, int dR, int dC) {int times = dC - tC; // 选装组数int tmp = 0; // 辅助变量for (int i = 0; i != times; i++) {tmp = m[tR][tC + i]; // 第tR行的tC列右侧第i位置m[tR][tC + i] = m[dR - i][tC]; // 第tC列的dR行上侧第i位置m[dR - i][tC] = m[dR][dC - i]; // 第dR行的dC列左侧第i位置m[dR][dC - i] = m[tR + i][dC]; // 第dC列的tR行下侧第i位置m[tR + i][dC] = tmp;}}// 打印矩阵public static void printMatrix(int[][] matrix) {for (int i = 0; i != matrix.length; i++) {for (int j = 0; j != matrix[0].length; j++) {System.out.print(matrix[i][j] + " ");}System.out.println();}}public static void main(String[] args) {int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 },{ 13, 14, 15, 16 } };printMatrix(matrix);rotate(matrix);System.out.println("=========");printMatrix(matrix);}

题目五

	public static boolean isContains(int[][] matrix, int K) {// 贪心，从数组的右上角元素开始找int row = 0; int col = matrix[0].length - 1;while (row < matrix.length && col > -1) { // 越界判断if (matrix[row][col] == K) { // 如果找到return true;} else if (matrix[row][col] > K) { // 当前数值比K大，往左走col--;} else { // 当前数值比K小，往下走row++;}}return false; // 没找到}

题目六

// 附加题：怎么判断一个数是不是质数？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;}// 请保证n不是质数// 返回:// 0) 所有因子的和，但是因子不包括1// 1) 所有因子的个数，但是因子不包括1public static int[] divsSumAndCount(int n) {int sum = 0;int count = 0;for (int i = 2; i <= n; i++) {while (n % i == 0) {sum += i;count++;n /= i;}}return new int[] { sum, count };}public static int minOps(int n) {if (n < 2) {return 0;}if (isPrim(n)) {return n - 1;}int[] divSumAndCount = divsSumAndCount(n);return divSumAndCount[0] - divSumAndCount[1];}

题目七

package class03;import java.util.Comparator;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.PriorityQueue;public class Problem07_TopKTimes {public static class Node {public String str; // 字符串public int times; // 词频public Node(String s, int t) {str = s;times = t;}}// 比较器，升序public static class NodeComparator implements Comparator<Node> {@Overridepublic int compare(Node o1, Node o2) {return o2.times - o1.times;}}public static void printTopKAndRank(String[] arr, int topK) {if (arr == null || arr.length == 0 || topK < 1) { // 边界信息return;}// 词频统计HashMap<String, Integer> map = new HashMap<>(); for (String str : arr) {// 如果没有出现过在表上，在表上初始化一个位置if (!map.containsKey(str)) { map.put(str, 0);}// 词频++map.put(str, map.get(str) + 1);}// 有可能数组元素个数少于要求的个数 细节！！！topK = Math.min(arr.length, topK);// 优先队列按照升序排列（小根堆）PriorityQueue<Node> heap = new PriorityQueue<>(new NodeComparator());for (Entry<String, Integer> entry : map.entrySet()) {Node cur = new Node(entry.getKey(), entry.getValue());// 如果堆没有满if (heap.size() < topK) {heap.add(cur);} // 堆满了else {// 如果cur把堆顶元素干掉了if (heap.peek().times < cur.times) {heap.poll();heap.add(cur);}}}// 最后打印堆中元素while (!heap.isEmpty()) {System.out.println(heap.poll().str);}}// 随机数生成器public static String[] generateRandomArray(int len, int max) {String[] res = new String[len];for (int i = 0; i != len; i++) {res[i] = String.valueOf((int) (Math.random() * (max + 1)));}return res;}// 打印前K个出现次数最多的public static void printArray(String[] arr) {for (int i = 0; i != arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}//public static void main(String[] args) {String[] arr1 = { "A", "B", "A", "C", "A", "C", "B", "B", "K" };printTopKAndRank(arr1, 2);String[] arr2 = generateRandomArray(50, 10);int topK = 3;printArray(arr2);printTopKAndRank(arr2, topK);}
}

补充

现在需要设计一个结构，可以动态添加字符串，并随时可以返回出现次数最多的前K个。

这篇关于【21】中级提升的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---