Skip to the content.

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);

	}

}

大量的矩阵变换都会涉及到一个宏观调度,不到万不得已,不要把自己陷入每个位置怎么变,扣每个位置的变化,会非常难