1 打表技巧和矩阵处理技巧
在一个数组arr[]中，每个数的大小不超过1000，例如[10,9,6,12],所有的数，求所有数质数因子的个数总和？
10=2*5
9=3*3
6=3*3
12=3*2*2
我们可以把1000以内的数的质数因子个数求出来，存到我们的表中，查表即可
1.1 打表法
1）问题如果返回值不太多，可以用hardcode的方式列出，作为程序的一部分
2）一个大问题解决时底层频繁使用规模不大的小问题的解，如果小问题的返回值满足条件1），可以把小问题的解列成一张表，作为程序的一部分
3）打表找规律（本节课重点），有关1）和2）内容欢迎关注后序课程
1.1.1 打表找规律
1）某个面试题，输入参数类型简单，并且只有一个实际参数
2）要求的返回值类型也简单，并且只有一个
3）用暴力方法，把输入参数对应的返回值，打印出来看看，进而优化code
1.1.2 例题1 小虎买苹果
小虎去买苹果，商店只提供两种类型的塑料袋，每种类型都有任意数量。
1）能装下6个苹果的袋子
2）能装下8个苹果的袋子
小虎可以自由使用两种袋子来装苹果，但是小虎有强迫症，他要求自己使用的袋子数量必须最少，且使用的每个袋子必须装满。 给定一个正整数N，返回至少使用多少袋子。如果N无法让使用的每个袋子必须装满，返回-1
暴力思路，例如N=100个苹果，我们全部用8号袋装，最多使用12个8号袋子，剩4个苹果，6号袋没装满。8号袋减1，需要2个6号袋，满足。如果依次递减8号袋，为0个仍未有答案，则无解
public class Code01_AppleMinBags {
public static int minBags(int apple) {
if (apple < 0) {
return -1;
}
int bag6 = -1;
int bag8 = apple / 8;
int rest = apple - 8 * bag8;
while (bag8 >= 0 && rest < 24) {
int restUse6 = minBagBase6(rest);
if (restUse6 != -1) {
bag6 = restUse6;
break;
}
rest = apple - 8 * (--bag8);
}
return bag6 == -1 ? -1 : bag6 + bag8;
}
// 如果剩余苹果rest可以被装6个苹果的袋子搞定，返回袋子数量
// 不能搞定返回-1
public static int minBagBase6(int rest) {
return rest % 6 == 0 ? (rest / 6) : -1;
}
// 根据打表规律写code
public static int minBagAwesome(int apple) {
if ((apple & 1) != 0) { // 如果是奇数，返回-1
return -1;
}
if (apple < 18) {
return apple == 0 ? 0 : (apple == 6 || apple == 8) ? 1
: (apple == 12 || apple == 14 || apple == 16) ? 2 : -1;
}
return (apple - 18) / 8 + 3;
}
// 打表看规律，摒弃数学规律
public static void main(String[] args) {
for(int apple = 1; apple < 100;apple++) {
System.out.println(apple + " : "+ minBags(apple));
}
}
}
1.1.2 例题2 牛羊吃草
给定一个正整数N，表示有N份青草统一堆放在仓库里 有一只牛和一只羊，牛先吃，羊后吃，它俩轮流吃草 不管是牛还是羊，每一轮能吃的草量必须是：
1，4，16，64…(4的某次方)
谁最先把草吃完，谁获胜
假设牛和羊都绝顶聪明，都想赢，都会做出理性的决定
根据唯一的参数N，返回谁会赢
暴力思路打表找规律
public class Code02_EatGrass {
// n份青草放在一堆
// 先手后手都绝顶聪明
// string "先手" "后手"
public static String winner1(int n) {
// 0 1 2 3 4
// 后 先 后 先 先
// base case
if (n < 5) { // base case
return (n == 0 || n == 2) ? "后手" : "先手";
}
// n >= 5 时
int base = 1; // 当前先手决定吃的草数
// 当前是先手在选
while (base <= n) {
// 当前一共n份草，先手吃掉的是base份，n - base 是留给后手的草
// 母过程 先手 在子过程里是 后手
if (winner1(n - base).equals("后手")) {
return "先手";
}
if (base > n / 4) { // 防止base*4之后溢出
break;
}
base *= 4;
}
return "后手";
}
// 根据打表的规律，写代码
public static String winner2(int n) {
if (n % 5 == 0 || n % 5 == 2) {
return "后手";
} else {
return "先手";
}
}
// 暴力打表找规律
public static void main(String[] args) {
for (int i = 0; i <= 50; i++) {
System.out.println(i + " : " + winner1(i));
}
}
}
1.1.3 例题3
定义一种数：可以表示成若干（数量>1）连续正数和的数 比如:
5 = 2+3，5就是这样的数
12 = 3+4+5，12就是这样的数
1不是这样的数，因为要求数量大于1个、连续正数和
2 = 1 + 1，2也不是，因为等号右边不是连续正数
给定一个参数N，返回是不是可以表示成若干连续正数和的数
public class Code03_MSumToN {
// 暴力法
public static boolean isMSum1(int num) {
for (int i = 1; i <= num; i++) {
int sum = i;
for (int j = i + 1; j <= num; j++) {
if (sum + j > num) {
break;
}
if (sum + j == num) {
return true;
}
sum += j;
}
}
return false;
}
// 根据打表的规律写代码
public static boolean isMSum2(int num) {
if (num < 3) {
return false;
}
return (num & (num - 1)) != 0;
}
// 打表
public static void main(String[] args) {
for (int num = 1; num < 200; num++) {
System.out.println(num + " : " + isMSum1(num));
}
System.out.println("test begin");
for (int num = 1; num < 5000; num++) {
if (isMSum1(num) != isMSum2(num)) {
System.out.println("Oops!");
}
}
System.out.println("test end");
}
}
1.2 矩阵处理技巧
1）zigzag打印矩阵
2）转圈打印矩阵
3）原地旋转正方形矩阵
核心技巧：找到coding上的宏观调度
1.2.1 zigzag打印矩阵
矩阵的特殊轨迹问题，不要把思维限制在具体某个坐标怎么变化
对于一个矩阵，如何绕圈打印，例如：
\begin{matrix}
1&2&3 \\
4&5&6 \\
7&8&9 \\
\end{matrix}
打印的顺序为：1，2，4，7，5，3，6，8，9
思路：准备A和B两个点，坐标都指向0，0位置。A和B同时走，A往右走，走到尽头后往下走，B往下走，走到不能再走了往右走。通过这么处理，A和B每个位置的连线都是一条斜线，且无重复。A和B每同时走一步，打印每次逆序打印，即开始时从B往A打印，下一步从A往B打印，循环往复
public class Code06_ZigZagPrintMatrix {
public static void printMatrixZigZag(int[][] matrix) {
// A的行row
int tR = 0;
// A的列coulum
int tC = 0;
// B的行row
int dR = 0;
// B的列coulum
int dC = 0;
// 终止位置的行和列
int endR = matrix.length - 1;
int endC = matrix[0].length - 1;
// 是不是从右上往左下打印
boolean fromUp = false;
// A的轨迹不会超过最后一行
while (tR != endR + 1) {
// 告诉当前A和B,打印方向，完成打印
printLevel(matrix, tR, tC, dR, dC, fromUp);
// 打印完之后，A和B再移动。A到最右再向下，B到最下再向右
tR = tC == endC ? tR + 1 : tR;
tC = tC == endC ? tC : tC + 1;
dC = dR == endR ? dC + 1 : dC;
dR = dR == endR ? dR : dR + 1;
// A和B来到下一个位置之后，改变打印方向
fromUp = !fromUp;
}
System.out.println();
}
public static void printLevel(int[][] m, int tR, int tC, int dR, int dC,
boolean f) {
if (f) {
while (tR != dR + 1) {
System.out.print(m[tR++][tC--] + " ");
}
} else {
while (dR != tR - 1) {
System.out.print(m[dR--][dC++] + " ");
}
}
}
public static void main(String[] args) {
int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
printMatrixZigZag(matrix);
}
}
1.2.2 转圈打印矩阵
\begin{matrix}
1&2&3&4 \\
5&6&7&8 \\
9&10&11&12 \\
13&14&15&16 \\
\end{matrix}
打印轨迹是：1，2，3，4，8，12，16，15，14，13，9，5，6，7，11，10
思路：每个圈，我们知道左上角的位置，和右下角的位置，我们就可以得到需要转圈的圈的大小，
public class Code05_PrintMatrixSpiralOrder {
public static void spiralOrderPrint(int[][] matrix) {
// A行
int tR = 0;
// A列
int tC = 0;
// B行
int dR = matrix.length - 1;
// B列
int dC = matrix[0].length - 1;
while (tR <= dR && tC <= dC) {
printEdge(matrix, tR++, tC++, dR--, dC--);
}
}
// 当前打印，左上角和右下角的位置
public static void printEdge(int[][] m, int tR, int tC, int dR, int dC) {
// 表示区域只剩下一条横线的时候
if (tR == dR) {
for (int i = tC; i <= dC; i++) {
System.out.print(m[tR][i] + " ");
}
} else if (tC == dC) { // 表示区域只剩下一条竖线了
for (int i = tR; i <= dR; i++) {
System.out.print(m[i][tC] + " ");
}
} else {
int curC = tC;
int curR = tR;
while (curC != dC) {
System.out.print(m[tR][curC] + " ");
curC++;
}
while (curR != dR) {
System.out.print(m[curR][dC] + " ");
curR++;
}
while (curC != tC) {
System.out.print(m[dR][curC] + " ");
curC--;
}
while (curR != tR) {
System.out.print(m[curR][tC] + " ");
curR--;
}
}
}
public static void main(String[] args) {
int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
spiralOrderPrint(matrix);
}
}
1.2.3 矩阵调整-原地旋转正方形矩阵
必须要是正方形矩阵，非正方形的旋转会越界；题意的意思是每一个数都顺时针旋转90度
\begin{matrix}
1&2&3&4 \\
5&6&7&8 \\
9&10&11&12 \\
13&14&15&16 \\
\end{matrix}
调整后的结构为：
\begin{matrix}
13&9&5&1 \\
14&10&6&2 \\
5&11&7&3 \\
16&12&8&4 \\
\end{matrix}
思路：一圈一圈的转，和旋转打印思路比较像。按圈，再按小组旋转，第一圈的第一个小组为四个角。分别为：1，4，16，13；第二小组为：2，8，15，9；依次旋转小组，最终达到旋转该圈的目的。接着旋转下一个圈的各个小组。每一层的小组数目等于该圈的边长减1
public class Code04_RotateMatrix {
public static void rotate(int[][] matrix) {
// a行
int a = 0;
// b列
int b = 0;
// c行
int c = matrix.length - 1;
// d列
int d = matrix[0].length - 1;
// 由于是正方形矩阵，只需要判断行不越界，等同于判断列不越界
while (a < c) {
rotateEdge(matrix, a++, b++, c--, d--);
}
}
// 当前需要转的圈的左上角和右下角
public static void rotateEdge(int[][] m, int a, int b, int c, int d) {
int tmp = 0;
// 得到左上角右下角坐标，我们可以知道右上角和左下角的位置，这四个位置先旋转。这四个位置称为一个小组。
// 旋转完之后，找下四个位置的小组再旋转
for (int i = 0; i < d - b; i++) {
tmp = m[a][b + i];
m[a][b + i] = m[c - i][b];
m[c - i][b] = m[c][d - i];
m[c][d - i] = m[a + i][d];
m[a + i][d] = 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);
}
}
大量的矩阵变换都会涉及到一个宏观调度，不到万不得已，不要把自己陷入每个位置怎么变，扣每个位置的变化，会非常难