滑动窗口
绳子覆盖
给定一个有序数组 arr，代表数轴上从左到右有 n 个点 arr[0]、arr[1] ... arr[n-1]，给定一个正数 L，代表一根长度为 L 的绳子，求绳子最多能覆盖其中的几个点？
思路：绳子左侧在第 i 个数时，能覆盖几个点，求最多的情况就可以。类似滑动窗口解决
import java.util.Arrays;public class CordCoverMaxPoint {public static int cordCoverMaxPoint(int[] arr, int L) {if (arr == null || arr.length == 0) return 0;System.out.println(Arrays.toString(arr));int max = 0;int curMax = 0;int startIndex = 0;for (int i = 0; i < arr.length; ) {if (arr[i] < arr[startIndex] + L) {curMax++;i++;} else {curMax--;startIndex++;}max = Math.max(max, curMax);}return max;}public static void main(String[] args) {System.out.println(cordCoverMaxPoint(new int[]{1, 3, 4, 5}, 3));System.out.println(cordCoverMaxPoint(new int[]{0, 13, 24, 35, 46, 57, 60, 72, 87}, 6));}}
打表法
最少袋子
小虎去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供 6 个每袋和 8 个每袋的包装，包装不可拆分。可是小虎现在只想购买恰好 n 个苹果，小虎想购买尽量少的袋数方便携带。如果不能购买恰好 n 个苹果，小虎将不会购买。输入一个整数 n，表示小虎想购买的个苹果，返回最小使用多少袋子。如果无论如何都不能正好装下，返回-1。
思路一：
用袋子去尝试，从 0 个 6 袋子到 n/6 个袋子依次去去试，如果剩下的 n - 6*i 正好能被 8 整除，那么这种情况是可以去分开 n 个苹果的。把所有的情况求出后取最小就可以得到结果
思路二：
思路一的优化，6 和 8 的最小公倍数是 24，这样的话，如使用了 m 个 6 之后可以将剩下的苹果数量如果小于 24，就可以直接抛弃了
思路三：
通过观察可以发现：
- 在 6 个苹果时，只需要一个袋子
- 在 8 个苹果时，只需要一个袋子
- 在 12 个苹果时，12 - 8 = 4，4 个苹果不能装； 12 - 6 = 6 ，即 12 个苹果时，需要 6 个苹果的袋子 + 1
- 在 14 个苹果时，14 - 8 = 6，6 个苹果能装； 14 - 6 = 8 ，即 14 个苹果时，需要min( 6 个苹果的袋子, 8 个苹果的袋子) + 1
- ……
这样就可以通过计算来得到在 n 个苹果时需要多少个袋子
代码实现：
import java.util.Random;
public class AppleMinBags {
/**
* 尝试版本
*
* @param n
* @return
*/
public static int appleMinBags(int n) {
if (n == 0) return 0;
if (n < 0 || n % 2 == 1 || n < 6) return -1;
int num = Integer.MAX_VALUE;
for (int i = 0; i <= n / 6; i++) {
int temp = n - 6 * i;
if (temp % 8 == 0 || temp == 0) {
num = Math.min(i + temp / 8, num);
}
}
return num == Integer.MAX_VALUE ? -1 : num;
}
/**
* 尝试版本 - 优化
*
* @param n
* @return
*/
public static int appleMinBags1(int n) {
if (n == 0) return 0;
if (n < 0 || n % 2 == 1 || n < 6) return -1;
int bag6 = -1;
int bag8 = n / 8;
int rest = n - 8 * bag8;
while (bag8 >= 0 && rest < 24) {
int restUse6 = rest % 6 == 0 ? rest / 6 : -1;
if (restUse6 != -1) {
bag6 = restUse6;
break;
}
rest = n - 8 * (--bag8);
}
return bag6 == -1 ? -1 : bag6 + bag8;
}
/**
* 规律
*
* @param n
* @return
*/
public static int appleMinBags2(int n) {
if (n == 0) return 0;
if (n < 0 || n % 2 == 1 || n < 6) return -1;
int[] arr = new int[n + 1];
arr[6] = 1;
arr[8] = 1;
for (int i = 0; i < n + 1; i++) {
if (i <= 8) {
arr[i] = i == 6 || i == 8 ? 1 : -1;
} else {
if (arr[i - 6] != -1 && arr[i - 8] != -1) {
arr[i] = Math.min(arr[i - 6], arr[i - 8]) + 1;
} else if (arr[i - 6] != -1) {
arr[i] = arr[i - 6] + 1;
} else if (arr[i - 8] != -1) {
arr[i] = arr[i - 8] + 1;
} else {
arr[i] = -1;
}
}
}
return arr[n];
}
public static void main(String[] args) {
for (int i = 0; i < 1000; i++) {
int n = new Random().nextInt(100000);
int num = appleMinBags(n);
if (num != appleMinBags2(n) || num != appleMinBags1(n)) {
System.out.println("出错了 ------ " + n);
break;
}
}
System.out.println("测试完成");
}
}
反正都已经实现，那么我们来看一下前 100 个的概率
0 -1
1 -1
2 -1
3 -1
4 -1
5 -1
6 1
7 -1
8 1
9 -1
10 -1
11 -1
12 2
13 -1
14 2
15 -1
16 2
17 -1
18 3
19 -1
20 3
21 -1
22 3
23 -1
24 3
25 -1
26 4
27 -1
28 4
29 -1
30 4
31 -1
32 4
33 -1
34 5
35 -1
36 5
37 -1
38 5
39 -1
40 5
41 -1
42 6
43 -1
44 6
45 -1
46 6
47 -1
48 6
49 -1
50 7
51 -1
52 7
53 -1
54 7
55 -1
56 7
57 -1
58 8
59 -1
60 8
61 -1
62 8
63 -1
64 8
65 -1
66 9
67 -1
68 9
69 -1
70 9
71 -1
72 9
73 -1
74 10
75 -1
76 10
77 -1
78 10
79 -1
80 10
81 -1
82 11
83 -1
84 11
85 -1
86 11
87 -1
88 11
89 -1
90 12
91 -1
92 12
93 -1
94 12
95 -1
96 12
97 -1
98 13
99 -1
可以发现：
- 从 12 开始，所有的奇数都是 -1，所有的偶数都是有值的
- 从 18 开始，每 8 个数，偶数得到的结果就会 + 1
直接把上面的规律写成代码，就是该题的解
public static int minBagAwesome(int n) {
if ((n & 1) != 0) {
return -1;
}
if (n < 18) {
return n == 0 ? 0 : (n == 6 || n == 8) ? 1
: (n == 12 || n == 14 || n == 16) ? 2 : -1;
}
return (n - 18) / 8 + 3;
}
所以这里，可以得到一个规律：
如果一个题目是整数输入并且整数输出的话，这个题可以使用暴力解法得到结果后，通过观察部分结果来总结出规律，直接将这个规律转变为程序。这个解法被称为打表法
请注意：并不是所有的整数输入整数输出的方法都可以用打表法来解决，但是有相当大的一部分可以使用
吃草
牛牛和羊羊都很喜欢青草。今天他们决定玩青草游戏。
最初有一个装有 n 份青草的箱子，牛牛和羊羊依次进行，牛牛先开始。在每个回合中，每个玩家必须吃一些箱子中的青草，所吃的青草份数必须是 4 的 x 次幂，比如 1, 4, 16, 64 等等。不能在箱子中吃到有效份数青草的玩家落败。假定牛牛和羊羊都是按照最佳方法进行游戏，请输出胜利者的名字。
思路：
根据题意：不能在箱子中吃到有效份数青草的玩家落败。不是有效份数是多少呢？不论在玩家选择吃了多少草，剩下的草如果不能被 4 的幂组成，那就不是有效的。而由于 
，所以说，剩下的草要不能被 1 组成，那么就只有 0 是符合无效的结果，即吃到最后一份草的玩家获胜。
列举例子：
- n = 1，先手赢
- n = 2，后手赢
- n = 3，先手赢
- n = 4，先手直接吃 4 份草，先手赢
- n = 5
- 先手吃 1 份，转化为 n = 4 的结果，此时后手为 n = 4 的先手，后手赢
- 先手吃 4 份，转化为 n = 1 的结果，此时后缀为 n = 1 的先手，后手赢
- n = 6
- 先手 1 份，转为 n = 5 的结果，此时后手为 n = 5 的先手，先手赢
- 先手 4 份，转为 n = 2 的结果，此时后手为 n = 2 的先手，先手赢
- n = 7
- 先手 1 份，转为 n = 6 的结果，此时后手为 n = 6 的先手，后手赢
- 先手 4 份，转为 n = 3 的结果，此时后手为 n = 3 的先手，后手赢
- ……
如此推论下棋，不论是 n 多大的结果都可以使用 n - 1 或者 n - 4 的结果推导出来
代码实现：
public class Eat {
/**
* 推论版本
*
* @param n
* @return
*/
public static boolean[] eat(int n) {
if (n < 0) return null;
boolean[] arr = new boolean[n + 1];
for (int i = 1; i < arr.length; i++) {
// true 代表先手赢，false 代表 后手赢
if (i == 0) {
arr[0] = false;
} else if (i == 1) {
arr[1] = true;
} else if (i == 2) {
arr[2] = false;
} else if (i == 3) {
arr[3] = true;
} else if (i == 4) {
arr[4] = true;
} else {
arr[i] = !arr[i - 1] || !arr[i - 4];
}
}
return arr;
}
/**
* 递归版本
*
* @param n
* @return
*/
public static String eat2(int n) {
if (n < 5) {
return (n == 0 || n == 2) ? "后手" : "先手";
}
int base = 1; // 先手决定吃的草
while (base <= n) {
// 当前一共 n 份草，先手吃掉了 base 份， n - base 是剩余的草
// 在子过程中，先手变成了后手
if (eat2(n - base).equals("后手")) {
return "先手";
}
if (base > n / 4) {
// 防止 base * 4 之后溢出
break;
}
// 这里是 4 的幂的体现
base *= 4;
}
return "后手";
}
public static void main(String[] args) {
boolean[] arr = eat(50);
for (int i = 0; i < arr.length; i++) {
// System.out.println(i + "\t" + (arr[i] ? "牛" : "羊"));
if (eat2(i).equals("先手") != arr[i]) {
System.out.println("出现错误：" + i);
break;
}
}
for (int i = 0; i < arr.length; i++) {
System.out.println(i + "\t" + (arr[i] ? "牛" : "羊"));
}
System.out.println("测试完成");
}
}
打印出前 50 个结果：
0 羊
1 牛
2 羊
3 牛
4 牛
5 羊
6 牛
7 羊
8 牛
9 牛
10 羊
11 牛
12 羊
13 牛
14 牛
15 羊
16 牛
17 羊
18 牛
19 牛
20 羊
21 牛
22 羊
23 牛
24 牛
25 羊
26 牛
27 羊
28 牛
29 牛
30 羊
31 牛
32 羊
33 牛
34 牛
35 羊
36 牛
37 羊
38 牛
39 牛
40 羊
41 牛
42 羊
43 牛
44 牛
45 羊
46 牛
47 羊
48 牛
49 牛
50 羊
可以发现规律，从 1 开始所有的就出现了 “牛羊牛牛羊”的规律，所以这个规律也可以做如下的实现：
public static void printWinner(int n) {
if (n % 5 == 0 || n % 5 == 2) {
System.out.println("羊");
} else {
System.out.println("牛");
}
}
预处理
染色方案
牛牛有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。牛牛现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色，这个正方形的颜色将会被覆盖。牛牛的目标是在完成染色之后，每个红色 R 都比每个绿色 G 距离最左侧近（也就是绿色 G 在右侧）。牛牛想知道他最少需要涂染几个正方形。
如样例所示：s = RGRGR
我们涂染之后变成 RRRGG 满足要求了：涂染的个数为2，没有比这个更好的涂染方案。
例如：s = GGGGGR
涂染后变成 GGGGGG：个数为 1。
思路一：
假设 s 有 i 个正方形都是 R，如果是 G，就将涂染成 R；大于 i 的范围内的都是 G，是 R 就涂染成 G。i 范围是 [0, s.length()]，记录最小的涂染次数。
思路二：
思路一的优化：思路一需要有两层遍历嵌套（分别是遍历 i，遍历 s），那么能不能将这个循环嵌套优化掉呢？
在遍历时，可以使用两个数组 gArr 和 rArr 来分别统计在 [0, i] 范围 G 出现的次数 和 [i, s.length() - 1] 范围上 R 出现的次数，这样就可以通过这两个数组计算出各种情况的涂染方案，并且取最小值即可得到最佳方案。
这个思路是将复杂的查询使用一些容器记录结果，以空间换时间，减少时间复杂度。
代码实现：
public class ColorLeftRight {
/**
* 思路一：循环统计
* @param s
* @return
*/
public static int minPaint(String s) {
char[] arr = s.toCharArray();
int time = -1;
for (int i = 0; i <= arr.length; i++) {
int cTime = 0;
for (int j = 0; j < arr.length; j++) {
if (j < i && arr[j] == 'G' || j > i && arr[j] == 'R') {
cTime++;
}
}
time = time == -1 ? cTime : Math.min(cTime, time);
}
return time;
}
/**
* 思路二：数组统计版
* @param s
* @return
*/
public static int minPaint2(String s) {
char[] arr = s.toCharArray();
// 统计左侧的 G
int[] gArr = new int[arr.length];
// 统计右侧的 R
int[] rArr = new int[arr.length];
for (int i = 0; i <= arr.length; i++) {
if (i < arr.length)
if (arr[i] == 'G') {
gArr[i] = i == 0 ? 1 : gArr[i - 1] + 1;
} else {
gArr[i] = i == 0 ? 0 : gArr[i - 1];
}
int j = arr.length - 1 - i;
if (j >= 0)
if (arr[j] == 'R') {
rArr[j] = i == 0 ? 1 : rArr[j + 1] + 1;
} else {
rArr[j] = i == 0 ? 0 : rArr[j + 1];
}
}
int time = rArr[0];
for (int i = 1; i < arr.length - 1; i++) {
time = Math.min(time, rArr[i] + gArr[i - 1]);
}
return Math.min(time, gArr[gArr.length - 1]);
}
public static void main(String[] args) {
System.out.println(minPaint("RGRGR"));
System.out.println(minPaint("GGGGGR"));
System.out.println(minPaint("RGGGGG"));
System.out.println(minPaint("GGGGG"));
System.out.println(minPaint2("RGRGR"));
System.out.println(minPaint2("GGGGGR"));
System.out.println(minPaint2("RGGGGG"));
System.out.println(minPaint2("GGGGG"));
}
}
矩阵边长
给定一个 NN 的矩阵 matrix，只有0和1两种值，返回边框全是1的最大正方形的边长长度。
例如:
01111
01001
01001
01111
01011
其中边框全是 1 的最大正方形的大小为 44，所以返回 4。
思路：
遍历矩阵，判断 [i, j] 为左上点的正方形是否存在
代码实现：
public class MaxOneBorderSize {
public static int getMax(int[][] matrix) {
int size = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
int cur = matrix[i][j];
if (cur == 1) {
// 边长循环
for (int k = 1; k < Math.min(matrix.length - i, matrix.length - j); k++) {
boolean flag = true;
// 上
for (int s = 0; s < k; s++) {
if (matrix[i][j + s] != 1) {
flag = false;
break;
}
}
// 下
for (int s = 0; s < k; s++) {
if (matrix[i + k][j + s] != 1) {
flag = false;
break;
}
}
// 左
for (int s = 0; s < k; s++) {
if (matrix[i + s][j + k] != 1) {
flag = false;
break;
}
}
// 右
for (int s = 0; s < k; s++) {
if (matrix[i + s][j + k] != 1) {
flag = false;
break;
}
}
if (flag) {
size = Math.max(size, k + 1);
}
}
}
}
}
return size;
}
public static void main(String[] args) {
int[][] matrix = {
{0, 1, 1, 1, 1},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 1},
{0, 1, 1, 1, 1},
{0, 1, 0, 1, 1},
};
System.out.println(getMax(matrix));
}
}
可以看到，上面的逻辑有 4 层循环嵌套（两层遍历矩阵嵌套，一层边长嵌套，一层验证正方形嵌套），时间复杂度为 
。
从思路分析，前三层嵌套属于代码逻辑，都不能优化。第四层嵌套如何优化呢？
两个数组：
- rightArr：统计矩阵每个点右侧有多少个连续的 1
- downArr：统计矩阵每个点下面有多少个连续的 1
有里这两个数组，就可以判断是否能围成正方形
代码实现如下：
public static int getMax2(int[][] matrix) {
int size = 0;
int length = matrix.length;
// 统计矩阵每个点右侧有多少个连续的 1
int[][] rightArr = new int[length][length];
for (int i = length - 1; i >= 0; i--) {
for (int j = length - 1; j >= 0; j--) {
if (matrix[i][j] == 1) {
rightArr[i][j] = j == length - 1 ? 1 : rightArr[i][j + 1] + 1;
}
}
}
// 统计矩阵每个点下面有多少个连续的 1
int[][] downArr = new int[length][length];
for (int i = length - 1; i >= 0; i--) {
for (int j = length - 1; j >= 0; j--) {
if (matrix[j][i] == 1) {
downArr[j][i] = j == length - 1 ? 1 : downArr[j + 1][i] + 1;
}
}
}
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
if (matrix[i][j] == 1) {
// 边长循环
for (int k = 1; k < Math.min(length - i, length - j); k++) {
if (rightArr[i][j] >= k && downArr[i][j] >= k && rightArr[i + k][j] >= k && downArr[i][j + k] >= k) {
size = Math.max(size, k + 1);
}
}
}
}
}
return size;
}
小结
滑动窗口的应用场景有几个特点：
1. 需要输出或比较的结果在原数据结构中是连续排列的；
2. 每次窗口滑动时，只需观察窗口两端元素的变化，无论窗口多长，每次只操作两个头尾元素，当用到的窗口比较长时，可以显著减少操作次数；
3. 窗口内元素的整体性比较强，窗口滑动可以只通过操作头尾两个位置的变化实现，但对比结果时往往要用到窗口中所有元素
打表法常见的做法：
- 在程序中一次性计算出所有用到的结果，之后的查询直接取这些结果。（最常用）
- 在程序 B 中分一次或多次计算出所有需要用到的结果，手动把结果写在程序 A 的数组中，然后在程序 A 中就可以直接使用这些结果。
使用场景：从程序的一部分过程的消耗时间过多，或是没有想到好的算法，因此可以在另外一个程序中使用暴力算法求出结果。
- 对一些不会做的题目，先用暴力程序计算小范围数据的结果，然后找规律，或许能找出答案。
使用场景：在数据范围大时容易用到。
预处理数组的使用场景：
在完成算法逻辑的流程中，如果某些步骤的查询代价特别大。想办法将这个遍历查询转变为一些单次的查询
若有收获，就点个赞吧
0 人点赞
