• 打表技巧和矩阵处理技巧

    打表找规律应用场景

    1. 某个面试题，输入参数类型简单，并且只有一个实际参数。
    2. 要求的返回值类型也简单，并且只有一个
    3. 用暴力方法，把输入参数对应的返回值，打印出来看看，进而优化代码。

    1.打表技巧实际案例

    案例一：

            小虎去买苹果，商店只提供两种类型的塑料袋，每种类型都有任意数量。1.能装下6个苹果的袋子，2.能装下8个苹果的袋子。小虎可以自由使用两种袋子来装苹果，但是小虎有强迫症，他要求自己使用的袋子数量必须最少，且使用的每个袋子必须装满。给定一个正整数N，返回至少使用多少袋子。如果N无法让使用的每个袋子必须装满，返回-1。

    1. public class AppleMinBags {
    2.     
    3. 	public static int minBags(int apple) {
    4. 		if (apple < 0) {
    5. 			return -1;
    6. 		}
    7. 		int bag8 = (apple >> 3);
    8. 		int rest = apple - (bag8 << 3);
    9. 		while(bag8 >= 0) {
    10. 			// rest 个
    11. 			if(rest % 6 ==0) {
    12. 				return bag8 + (rest / 6);
    13. 			} else {
    14. 				bag8--;
    15. 				rest += 8;
    16. 			}
    17. 		}
    18. 		return -1;
    19. 	}
    20.  
    21. 	public static int minBagAwesome(int apple) {
    22. 		if ((apple & 1) != 0) { // 如果是奇数，返回-1
    23. 			return -1;
    24. 		}
    25. 		if (apple < 18) {
    26. 			return apple == 0 ? 
    27. 					0 : (apple == 6 || apple == 8) ? 
    28. 						1: (apple == 12 || apple == 14 || apple == 16) ? 
    29. 							2 : -1;
    30. 		}
    31. 		return (apple - 18) / 8 + 3;
    32. 	}
    33.  
    34. 	public static void main(String[] args) {
    35. 		for(int apple = 1; apple < 200;apple++) {
    36. 			System.out.println(apple + " : "+ minBags(apple));
    37. 		}
    38.  
    39. 	}
    40.  
    41. }

    案例二：

            给定一个正整数N，表示有N份青草统一堆放在仓库里。有一只牛和一只羊，牛先吃，羊后吃，它俩轮流吃草。不管是牛还是羊，每一轮能吃的草量必须是：1，4，16，64…(4的某次方)。谁最先把草吃完，谁获胜。假设牛和羊都绝顶聪明，都想赢，都会做出理性的决定。根据唯一的参数N，返回谁会赢。

    1. public class EatGrass {
    2.  
    3. 	// 如果n份草，最终先手赢，返回"先手"
    4. 	// 如果n份草，最终后手赢，返回"后手"
    5. 	public static String winner1(int n) {
    6. 		//0  1  2  3  4
    7. 		//后 先 后 先 先
    8. 		if (n < 5) {
    9. 			return (n == 0 || n == 2) ? "后手" : "先手";
    10. 		}
    11. 		int base = 1;
    12. 		while (base <= n) {
    13. 			if (winner1(n - base).equals("后手")) {
    14. 				return "先手";
    15. 			}
    16. 			if (base > n / 4) { // 防止base*4之后溢出
    17. 				break;
    18. 			}
    19. 			base *= 4;
    20. 		}
    21. 		return "后手";
    22. 	}
    23.  
    24. 	public static String winner2(int n) {
    25. 		if (n % 5 == 0 || n % 5 == 2) {
    26. 			return "后手";
    27. 		} else {
    28. 			return "先手";
    29. 		}
    30. 	}
    31.  
    32. 	public static void main(String[] args) {
    33. 		for (int i = 0; i <= 50; i++) {
    34. 			System.out.println(i + " : " + whoWin(i));
    35. 		}
    36. 	}
    37.  
    38. }

    案例三：

            对于一个正整数x（3≤x≤1000），寻找一种方案，将x分解成连续正整数的和。即x=x1+x2+…+xn。其中x1、x2、…、xn是自小至大的连续正整数，且n>1。
            比如，对于输入的数字10，可以分解成"10=1+2+3+4"。
            如果存在多于一种的可行方案，则选取等式右边项的个数最多的那一种。比如，9可以分解为"9=2+3+4"，也可以分解为"9=4+5"。但是前一种分解成3个数的和，后一种分解成2个数的和，所以前一种是有效解。

    1. public class MSumToN {
    2.  
    3. 	public static boolean isMSum1(int num) {
    4. 		for (int start = 1; start <= num; start++) {
    5. 			int sum = start;
    6. 			for (int j = start + 1; j <= num; j++) {
    7. 				if (sum + j > num) {
    8. 					break;
    9. 				}
    10. 				if (sum + j == num) {
    11. 					return true;
    12. 				}
    13. 				sum += j;
    14. 			}
    15. 		}
    16. 		return false;
    17. 	}
    18.  
    19. 	public static boolean isMSum2(int num) {
    20.  
    21.         //判断num是不是2的某次方 	==0是2的某次方           ！=0不是2的某次方   
    22. 		//十进制8的二进制表示为  
    23.          //   00001000 减去1后二进制形式为00000111 与原来二进制数字与操作后结果为0
    24.         //再例如十进制10二进制表示为    00001010  减去1后二进制表示为00001001
    25.         //00001010 & 00001001 = 00001000 不为0
    26.         if (num < 3) {
    27. 			return false;
    28. 		}
    29. 		return (num & (num - 1)) != 0;
    30.  
    31. 	}
    32.  
    33. 	public static void main(String[] args) {
    34. 		for (int num = 1; num < 200; num++) {
    35. 			System.out.println(num + " : " + isMSum1(num));
    36. 		}
    37. //		System.out.println("test begin");
    38. //		for (int num = 1; num < 5000; num++) {
    39. //			if (isMSum1(num) != isMSum2(num)) {
    40. //				System.out.println("Oops!");
    41. //			}
    42. //		}
    43. //		System.out.println("test end");
    44.  
    45. 	}
    46. }

    2.矩阵处理实际案例

    案例一：zigzag打印矩阵。

            给定一个正方形或者长方形矩阵matrix，实现zigzag打印。[[0,1,2],[3,4,5],[6,7,8]]的打印顺序是0,1,3,6,4,2,5,7,8。

    1. public class ZigZagPrintMatrix {
    2.  
    3. 	public static void printMatrixZigZag(int[][] matrix) {
    4. 		int Ar = 0;
    5. 		int Ac = 0;
    6. 		int Br = 0;
    7. 		int Bc = 0;
    8. 		int Endr = matrix.length - 1;
    9. 		int Endc = matrix[0].length - 1;
    10. 		boolean fromUp = false;//是不是从右上向左下打印
    11. 		while (Ar != Endr + 1) {
    12. 			printLevel(matrix, Ar, Ac, Br, Bc, fromUp);
    13. 			Ar = Ac == Endc ? Ar + 1 : Ar;
    14. 			Ac = Ac == Endc ? Ac : Ac + 1;
    15. 			
    16. 			Bc = Br == Endr ? Bc + 1 : Bc;
    17. 			Br = Br == Endr ? Br : Br + 1;
    18. 			fromUp = !fromUp;
    19. 		}
    20. 		System.out.println();
    21. 	}
    22.  
    23. 	public static void printLevel(int[][] m, 
    24. 			int tR, int tC, int dR, int dC, boolean f) {
    25. 		if (f) {
    26. 			while (tR != dR + 1) {
    27. 				System.out.print(m[tR++][tC--] + " ");
    28. 			}
    29. 		} else {
    30. 			while (dR != tR - 1) {
    31. 				System.out.print(m[dR--][dC++] + " ");
    32. 			}
    33. 		}
    34. 	}
    35.  
    36. 	public static void main(String[] args) {
    37. 		int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
    38. 		printMatrixZigZag(matrix);
    39.  
    40. 	}
    41.  
    42. }

    案例二：转圈打印矩阵

            给定一个整型矩阵matrix，请按照顺时针转圈的方式打印它。
    输入[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
    返回值[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]

    1. public class PrintMatrixSpiralOrder {
    2.  
    3. 	public static void spiralOrderPrint(int[][] matrix) {
    4. 		int tR = 0;
    5. 		int tC = 0;
    6. 		int dR = matrix.length - 1;
    7. 		int dC = matrix[0].length - 1;
    8. 		while (tR <= dR && tC <= dC) {
    9. 			printEdge(matrix, tR++, tC++, dR--, dC--);
    10. 		}
    11. 	}
    12.  
    13. 	public static void printEdge(int[][] m, 
    14. 			int a, int b, int c, int d) {
    15. 		if (a == c) {
    16. 			for (int i = b; i <= d; i++) {
    17. 				System.out.print(m[a][i] + " ");
    18. 			}
    19. 		} else if (b == d) {
    20. 			for (int i = a; i <= c; i++) {
    21. 				System.out.print(m[i][b] + " ");
    22. 			}
    23. 		} else {
    24. 			int curC = b;
    25. 			int curR = a;
    26. 			while (curC != d) {
    27. 				System.out.print(m[a][curC] + " ");
    28. 				curC++;
    29. 			}
    30. 			while (curR != c) {
    31. 				System.out.print(m[curR][d] + " ");
    32. 				curR++;
    33. 			}
    34. 			while (curC != b) {
    35. 				System.out.print(m[c][curC] + " ");
    36. 				curC--;
    37. 			}
    38. 			while (curR != a) {
    39. 				System.out.print(m[curR][b] + " ");
    40. 				curR--;
    41. 			}
    42. 		}
    43. 	}
    44.  
    45. 	public static void main(String[] args) {
    46. 		int[][] matrix = { 
    47. 				{ 1, 2, 3, 4 }, 
    48. 				{ 5, 6, 7, 8 }, 
    49. 				{ 9, 10, 11, 12 },
    50. 				{ 13, 14, 15, 16 } };
    51. 		spiralOrderPrint(matrix);
    52.  
    53. 	}
    54.  
    55. }

    案例三：原地旋转正方形矩阵

            给定一个正方形矩阵matrix，原地调整成顺时针90度转动的样子。[[a,b,c],[d,e,f],[g,h,i]]变成[[g,d,a],[h,e,b],[i,f,c]]。

    1. public class RotateMatrix {
    2.  
    3. 	public static void rotate(int[][] matrix) {
    4. 		int a = 0;
    5. 		int b = 0;
    6. 		int c = matrix.length - 1;
    7. 		int d = matrix[0].length - 1;
    8. 		while (a < c) {
    9. 			rotateEdge(matrix, a++, b++, c--, d--);
    10. 		}
    11. 	}
    12.  
    13. 	public static void rotateEdge(int[][] m, 
    14. 			int a, int b, int c, int d) {
    15. 		int tmp = 0;
    16. 		for (int i = 0; i < d - b; i++) {
    17. 			tmp = m[a][b + i];
    18. 			m[a][b + i] = m[c - i][b];
    19. 			m[c - i][b] = m[c][d - i];
    20. 			m[c][d - i] = m[a + i][d];
    21. 			m[a + i][d] = tmp;
    22. 		}
    23. 	}
    24.  
    25. 	public static void printMatrix(int[][] matrix) {
    26. 		for (int i = 0; i != matrix.length; i++) {
    27. 			for (int j = 0; j != matrix[0].length; j++) {
    28. 				System.out.print(matrix[i][j] + " ");
    29. 			}
    30. 			System.out.println();
    31. 		}
    32. 	}
    33.  
    34. 	public static void main(String[] args) {
    35. 		int[][] matrix = { 
    36. 				{ 1, 2, 3, 4 }, 
    37. 				{ 5, 6, 7, 8 }, 
    38. 				{ 9, 10, 11, 12 }, 
    39. 				{ 13, 14, 15, 16 } };
    40. 		printMatrix(matrix);
    41. 		rotate(matrix);
    42. 		System.out.println("=========");
    43. 		printMatrix(matrix);
    44.  
    45. 	}
    46.  
    47. }

  • 相关阅读:
    windows10安装其他版本cuda环境
    数据结构与算法之美10（排序）
    简明 SQL 子查询指南：掌握 EXISTS 实现数据筛选
    深入多线程锁
    VSCode中Java程序入口的数据输入流的常用形式
    Python学习之CSDN21天学习挑战赛计划之4
    自定义过滤器配置 Shiro 认证失败返回 json 数据
    嵌入式单片机无刷电机FOC控制与实现详解
    Express 路由
    面试 | Python 自动化测试技术面试真题
  • 原文地址：https://blog.csdn.net/z1171127310/article/details/127415372