中级班第一节
技巧一：窗口法。构造两个边界（指针），并且这两个指针都不需要回退（只往一个方向走）
例题：给定一个有序数组 arr，代表数轴上从左到右有 n 个点 arr[0], arr[1]...arr[n-1]。给定一个正数 L，代表一根长度为 L 的绳子，求绳子最多能覆盖其中的几个点
方法一
分别以每个点为右边界，查看该点为绳子右边界时最多能覆盖多少个点。 确定后右边界后。利用二分查找，找到大于等于左边界最左的点。此时就得到了左右两个边界（即 arr 数组中左右两个下标），所以此时能覆盖的点的数量就是 r-l+1 时间复杂度 O(N*logN)
方法二，利用技巧
以每个点为左边界，查看以该点为左边界所能覆盖的数量。 利用两个指针（组成窗口）l 和 r，l 和 r 就是数组的下标，首先让 r 走，走到 r 不能走（也就是说 r 再走一个就会导致 arr[R]-arr[l] > L）此时 L 和 R 之间的元素数量就是以 L 所在点为左边界所能覆盖的最大点数量。 该方法中，r 和 l 只会往右走，每次都一定会有一个点移动，所以时间复杂度是 O(N)
测试代码：
from bisect import bisect_left
def resolve(arr, L):
ans = 0
for right_i, right in enumerate(arr):
left = right - L
left_i = bisect_left(arr, left)
ans = max(ans, right_i - left_i + 1)
return ans
def resolve2(arr, L):
ans = 0
left, right = 0, 0
n = len(arr)
while right < n:
if left == right or arr[right] -arr[left] <= L:
right += 1
else:
ans = max(ans, right - left)
left += 1
ans = max(ans, right - left)
return ans
from random import randint as rd
for _ in range(100000):
arr = sorted(list(set([rd(1, 10000) for _ in range(100)])))
L = rd(1, 100000)
ans1 = resolve(arr, L)
ans2 = resolve2(arr, L)
if ans1 != ans2:
print(ans1, ans2, L, '\n', arr, )
break技巧二：打表法。输入是整数，输出也是整数时，通过对数器查看答案规律，然后直接给出最优解。（大概 4 成题目能用）
例题：小虎去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装。包装不可拆分。可是小虎现在只想购买恰好n个苹果，小虎想购买尽量少的袋数方便携带。如果不能购买恰好 n 个苹果，小虎将不会购买。输入一个整数 n，表示小虎想购买的苹果数量，返回最小使用多少袋子。如果无论如何都不能正好装下，返回-1
简单的就说就是 N = 6x + 8y 要求 x+y 的值最小，如果 N = 6x + 8y 无法成立，则返回 -1.
方法一
先求 y，然后让剩下的值给 6 处理，如果能够整除，则返回当前的 x+y。 如果不能整除，则让 y-1，然后继续。 当 y 等于 0 时还无法整除，则返回 -1。
简单优化：当要交给 6 解决的苹果数量大于 24 后，直接停止循环。原因在于 24 是 6 和 8 的最小公倍数。当需要解决的苹果数量大于 24 时，如果能被 6 解决，那么也一定能被 8 解决，既然如此，那我肯定会选择用 8 类型袋子来装，何必需要 6 呢？所以当交给 6 的苹果数量大于 24 时，说明一定是 8 无法解决的，那自然也就无法被 6 解决了。
方法二，打表法
写出方法一的代码后，通过对数器直接输出一些答案，然后会发现规律——大于 24 的数字中，奇数全为 -1，偶数是每 8 个数字就加一。 根据这个规律直接写出代码。
打表法最终的结果就是发现方法一中的简单优化结果。但打表法的好处在于你不需要了解其原理。
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;
}
int minBagBase6(int rest) {
return rest % 6 == 0? (rest / 6) : -1;
}
// 打表法总结出的规律
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;
}例题：先手后手吃草，每次吃的数量只能选择 4 的 n 次方（1,4,16,32...）。给定总的数量，问你先手后手谁赢
比如总数为 1，那么先手直接吃完 1，所以先手赢。 比如总数为 2，先手不能不吃，所以先手只能吃 1，于是后手赢。 比如总数为 3，先手先吃 1，后手只能吃 1，于是先手赢。 比如总数为 4，先手直接吃掉 4，先手赢。 ……
方法一：正常逻辑写出代码
先手吃 1 份，然后让子过程判断是谁赢，不是无法赢，那么就再试试吃 4 份谁赢，一直进行下去……
方法二：打表法
写出方法一的代码后，输出前 50 个答案，然后发现规律：先后先先后，先后先先后，…… 于是利用该规律直接输出！
String winner1(int n) {
// 进来的默认是当前进程的“先手”
// 0 1 2 3 4
// 后 先 后 先 先
if (n < 5) {
return (n == 0 || n == 2) ? "后手" : "先手";
}
int base = 1; // 先手决定吃的草
while (base <= n) {
// 当前角色在当前过程中是”先手“，但到了子过程中就变成了”后手“。所以如果子过程说“后手”赢了，就是当前过程赢了。
if (winner1(n - base).equals("后手")) {
return "先手";
}
if (base > n / 4) { // 因为 base*4 可能溢出，所以提前判断一下。
break;
}
base *= 4;
}
// 如果先手没有赢，那就是后手赢。
return "后手";
}技巧三：预处理。也就是空间换时间的思路，查看代码中有哪些查询是频繁的，思考能不能利用一个辅助空间来帮助优化这些查询
例题：小明有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。小明现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将会被覆盖。小明的目标是在完成染色之后,每个红色 R 都在每个绿色 G 的左边。小明想知道他最少需要涂染几个正方形
比如初始的正方形是：s =RGRGR 染成 RRRGG 所需要的染色操作最少，其他操作，比如染成 RRRRR, GGGGG 等等，所需要的操作数都更多。
依次查看左侧的 R 数量为 0, 1, 2, ... N 时，所需要的染色操作数，然后返回一个最小的操作数。伪代码如下：
int minPaint(String s) {
char[] str = s.toCharArray();
int N = str.length;
// 左侧 R 右侧 G
for (int L = 0; L <= N; L++) {
if (L == 0) { // 即最终要全部染色成 G
统计 arr[0...N-1] 上一共有多少个 R，R 的数量就是我们需要染色的操作数
} else if (L == N) { // 即最终全部染色呈 R
统计 arr[0...N-1] 上一共有多少个 G，G 的数量就是我们需要染色的操作数
} else {
统计 arr[0...L] 上一共有多少个 G
加上 统计 [L+1,...N-1] 上一共有多少个 R
两者相加的数量就是所需要的染色操作数
}
}
}上面伪代码中，数字描述部分可以通过遍历的方式实现，但这样一来时间复杂度就是 O(N^2) 。因为每次都需要遍历完整的数组。这就是一个频繁的查询操作，我们完全可以借助一个辅助数组来存储这些信息。定义两个辅助数组 left_right_G, right_left_R。
- left_right_G 中每个元素表示的是，0 位置到当前位置上一共有多少个 G。
- right_left_R 中每个元素表示的是，N-1 位置到当前为止上一共有多少个 R。
这样一来，我们就将时间复杂度降低到了 O(N)，这就是数组预处理技巧。
例题：给定一个只有 0 1 的矩阵，查看边框全为 1 的正方形子矩阵有多少个
首先，对于一个矩阵，查看其一共有多少个子矩阵的时间规模是 O(N^4)。理由是：在矩阵都找一个点，该点的情况是 N^2，然后再找一个点，同样是 N^2 。两个点可以确定一个矩阵，所以时间规模是 N^4 。当然，实际情况会小一点，因为可能出现情况重复，但规模就是这个规模
然后，查看矩阵中有多少个正方形的子矩阵的时间规模是 O(N^3)。理由是：第一个点的总情况数量同样是 N^2。问题是第二个点有要求，它只能从当前点的右下方上找，所以情况是 N 个。总的情况就是 N^3。
所以该题的伪代码如下：
int maxAllOneBorder(int[][] m) {
int N = m.length;
int M = m[0].length;
for (int row = 0; row < N; row++ ) {
for (int col = 0; col < M; col++ ) {
// 枚举边长
for (int border = 1; border < Math.min(N-row, M-col); border++) {
// 此处这里确定了两个信息：子正方形矩阵的左上角为 (row, col), 边长为 border。
// 所以此时唯一确定了一个子正方形矩阵
// 剩下的工作就是判断该子矩阵的四个边框是否全为 1
验证这个正方形的四条边上的值是不是都是值为 1.
}
}
}
}上面代码中验证时，如果不做优化，那么就需要遍历四条边进行判断。这样会导致时间复杂度变成 O(N^4)。
但可以通过辅助空间来优化这个判断过程。方法是创建两个辅助矩阵 right 和 down，大小和原矩阵一样。right 中每一个元素的值表示从当前点开始计算右方有多少个连续值为 1 的点。所以如果原矩阵中某个点是 0，则直接赋值为 0，如果为 1，则只需要加上右侧的元素的值。同理，down 矩阵就是计算当前点的下方一共有多少个连续值为 1 的点。
有了两个辅助矩阵 right 和 down 后，当判断矩阵边框是否全为 1 时，只需要查看三个点的信息：左上角的点的右方和下方连续的 1 数量、右上角的下方连续的 1 数量、左下角的右方连续的 1 的数量。此时就将判断的时间复杂度降低为 O(1) 级别了！
例题：加工概率函数
给定一个函数f，可以等概率返回 1~5。请根据该函数 f 加工出等概率返回 1~7 的函数 g
首先，f 能等概率返回 1~5，那么就可以通过这个 f 加工出等概率返回 0 和 1 的函数。方法是：f 返回 1,2 时返回 0，f 返回 3,4 时返回 1，f 返回 5 时忽略。
根据该思路，由于二进制是由 0,1 组成的，所以可以利用随机返回 0,1 这个函数来生成一个等概率随机的数字。
目的是等概率返回 1~7，那么我们就实现一个等概率返回 0~6 的函数。首先查看 6 的二进制是三位（110），所以我们可以通过 0,1 随机生成 0~7(111)个数字，当随机生成的数字是 7 时，直接忽略，这样一来就实现了等概率随机返回 0~6，将它加 1 就变成了 1~7.
给定一个函数f，可以等概率返回 a~b。请根据该函数 f 加工出等概率返回 c~d 的函数 g
方法是一样的：
- 将 f 加工成等概率返回 0 1 的函数
- 计算 d-c+1=x，然后查看 x 占用 y 位，此时就能够通过 0 1 随机生成函数能够随机生成
~ 范围的数字，当生成的数字大于 x 时，就忽略掉 - 将随机生成的 0~x 上的数字加上 d，然后返回。
给定一个函数f，以 p 概率返回 0，以 1-p 概率返回 1。请加工出等概率返回 0 和 1 的函数 g
很简单，调用两次 f，如果生成 00 则忽略，生成 11 也忽略。当生成 01 时返回 1，当生成 10 时返回 0。因为生成 10 和生成 01 的概率都是 p*(1-p) 的概率。