第一节课：滑动窗口、打表和预处理数据_滑窗法处理数据

---

题目一

方法一：每个点作为绳子右侧端点的情况下能覆盖几个点，遍历每个点，结果一定在其中。基础班有个技巧，找到大于等于某个数最左的位置（二分）。时间复杂度：一共检查了N个点，每次做二分，所有时间复杂度为O(N*logN)。

方法二：滑动窗口。L、R两个指针，R向右移动，但L、R两指针对应元素的差不要超过绳子的长度；当R不能再移动时，L向右移动一个位置；然后重复上述操作。时间复杂度：O(N)
方法一是用二分的方式确定一个七点，而方法二是用滑动窗口单调不递减的方式确定一个终点，构造了一个左边界和右边界都不需要回退的模型
代码实现：

//方法一
int getNearestPos(vector<int>& arr, int i, int num) {
	int l = 0;
	int r = i;
	while (l <= r) {
		//mid = r - ((r - l) >> 1);
		int mid = l + ((r - l) >> 1);
		if (arr[mid] > num) {
			r = mid - 1;
			i = mid;
		}
		else if (arr[mid] < num) {
			l = mid + 1;
		}
		else {
			return mid;
		}
	}
	return i;
}

int maxCoverPoint01(vector<int>& arr, int len) {
	int res = 0;
	for (int i = 0; i < arr.size(); i++) {
		int nearestIndex = getNearestPos(arr, i, arr[i] - len);
		res = max(res, i - nearestIndex + 1);
	}
	return res;
}

//方法二
int maxCoverPoint02(vector<int>& arr, int len) {
	int l = 0;
	int r = 0;
	int res = 0;
	while (r < arr.size()) {
		if (arr[r] - arr[l] < len) {
			r++;
		}
		else if (arr[r] - arr[l] > len) {
			res = max(res, r - l);
			l++;
			r++;
		}
		else {
			res = max(res, r - l + 1);
			l++;
			r++;
		}
	}
	return res;
}
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
51
52

---

题目二

方法一：尽量使用装8个的袋子，剩下的再尝试用装6个的袋子，如果能装下则返回，如果装不下，则让装8个的袋子依次递减

优化：当用装8个的袋子装剩下的苹果数超过24时，后面的尝试都不成立，因为，超过24个苹果可以用三个8袋子，二不必用4个6袋子
方法二：打表：输入是一个正数，输出也是一个正数，先写出一个好想的的代码，然后分析输出的规律，根据规律对代码进行优化，对应的数学规律不管。大概能解决4成的题目。

//方法一
int minBags(int n) {
	if (n < 0 || n % 2 == 1) {
		return -1;
	}
	for (int i = n / 8; i >= 0; i--) {
		if ((n - i * 8) % 6 == 0) {
			return i + (n - i * 8) / 6;
		}
		if (n - i * 8 > 24) {
			break;
		}
	}
	return -1;
}

//方法二
int minBags02(int n) {
	if (n % 2 == 1) {
		return -1;
	}
	if (n < 18) {
		return n == 0 ? 0 : (n == 6 || n == 8 ? 1 : (n == 12 || n == 14 || n == 16 ? 2 : -1));
	}
	return n % 8 == 0 ? n / 8 : n / 8 + 1;
}
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

---

题目三

方法一：暴力递归。确定basecase；先手依次尝试吃4的幂次方份草，只要后序结果有一种能让先手获胜，即先手获胜（因为他们都是绝顶聪明的）；另外，先手在进入递归函数之后变成了后手；最后还需注意整数溢出的情况
方法二：打表。根据方法一的解决，找规律，发现总是“后先后先先”进行循环，直接编写代码，不去管具体的数学原理。
代码实现：

//方法一：
string f(int n) {
	// 0 1 2 3 4
	//后先后先先
	//n<5时只有一种选择，确定为basecase
	if (n < 5) {
		return n == 0 || n == 2 ? "后手" : "先手";
	}
	int base = 1;
	while(base<=n) {
		//当前一共n份草，先手吃掉base份，n-base留给后手的草
		//木过程的先手，在子过程中是后手
		if (f(n - base)=="后手") {
			return "先手";
		}
		if (base > n / 4) {//防止溢出
			break;
		}
		base *= 4;
	}
	return "后手";
}
//方法二：打表
string f2(int n) {
	
	if (n % 5 == 0 || n % 5 == 2) {
		return "后手";
	}
	return "先手";
}
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

---

题目四

方法一：暴力尝试。遍历整个字符串，将遍历到的位置及之后全部变成G，之前全部变成R，统计涂色次数的最小值。
方法二。数据预处理：研究代码，发现那一块的查询是频繁的，想办法用低代价的方式生成某个结构，后序就不需要遍历，直接从辅助结构中那答案，加速整个过程。方法一每次遍历到一个位置，还需要前后扫描有多少R和G，变成了一个双层循环，时间复杂度为O(N^2)。可以生成两个数组，分别记录当前位置及之前有多少G（前缀和），当前位置及之后有多少R（后缀和）；对方法一中每次遍历到的位置需要的数据，直接从数组中取出即可。

//方法一：O(N^2)
int f(string& s) {
	int res = INT_MAX;
	for (int i = 0; i < s.length() + 1; i++) {
		int count = 0;
		for (int j = 0; j < i - 1; j++) {
			if (s[j] == 'G') {
				count++;
			}
		}
		for (int j = i; j < s.length(); j++) {
			if (s[j] == 'R') {
				count++;
			}
		}
		res = min(res, count);
	}
	return res;
}

//方法二：O(N)
int f2(string& s) {
	int N = s.length();
	vector<int>arr(N);
	arr[0] = s[0] == 'G' ? 1 : 0;
	for (int i = 1; i < N; i++) {
		//R:0  G:1，当前位置及之前有多少个1
		arr[i] = s[i] == 'G' ? arr[i - 1] + 1 : arr[i - 1];
	}
	int res = N - arr[N - 1];//全部变成G-->总共R的个数
	for (int i = 1; i < N; i++) {
		//当前位置及后面全部变成G：1
		//当前位置之前的1：
		int num_1 = arr[i - 1];//这么多1要全部变成0
		//当前位置及之后有多少0：
		int num_0 = N - i - (arr[N - 1] - arr[i - 1]);//这么多0要全部变成1
		res = min(res, num_1 + num_0);
	}
	return res;
}
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

---

题目五

方法一：N*N大小的矩阵的子矩阵（长方形）有N^{4规模个，均以N}2分之一的概率选两个点，以这两个点为对角线画矩阵；若规定必须是正方形，则是N^{3规模，以N}2分之一的概率选一个点，以该点为左上角枚举各个边长的正方形个数。

遍历矩阵的各个位置，以当前位置为正方形的左上顶点，每次向下/向右扩一个位置，判断当前正方形是否符合条件
方法二：数据预处理。用两个数组right和down分别记录原数组某一位置向右（包括当前）有多少连续的1、原数组某一位置向下（包括当前）有多少连续的1

代码实现：

//方法一：O(N^4)!!!!
//代码错误，不想改了。。。
int f(vector<vector<int>>& arr) {
	int N = arr.size();
	int res = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (arr[i][j] == 1) {
				int k = 1;
				while (i + k < N && j + k < N && arr[i + k][j]==1 && arr[i][j + k]==1) {
					bool flag = true;
					for (int r = 1; r <= k; r++) {
						if (arr[r+i][j + k] != 1||arr[i+k][j+r]!=1) {
							flag = false;
							break;
						}
					}
					if (flag == false) {
						break;
					}
					k++;
				}
				res = max(res, k);
			}
		}
	}
	return res;
}

//方法二：O(N^3)
int f2(vector<vector<int>>& arr) {
	int N = arr.size();
	vector<vector<int>>right(N, vector<int>(N));
	vector<vector<int>>down(N, vector<int>(N));
	for (int i = 0; i < N; i++) {
		right[i][N - 1] = arr[i][N - 1];
		for (int j = N - 2; j >= 0; j--) {
			right[i][j] = arr[i][j] == 0 ? 0 : 1 + right[i][j + 1];
		}
	}

	for (int j = 0; j < N; j++) {
		down[N - 1][j] = arr[N - 1][j];
		for (int i = N - 2; i >= 0; i--) {
			down[i][j] = arr[i][j] == 0 ? 0 : 1 + down[i + 1][j];
		}
	}

	int res = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (arr[i][j] == 1) {
				for (int k = 1; k + i < N && k + j < N; k++) {
					if (right[i][j] >= k + 1 && down[i][j] >= k + 1 && right[i + k][j] >= k + 1 && down[i][j + k] >= k + 1) {
						res = max(res, 1 + k);
					}
				}
			}
		}
	}
	return res;
}

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
51
52
53
54
55
56
57
58
59
60
61
62
63

---

题目六

用二进制拼：将等概率返回a-b的数字的函数加工成等慨率返回0/1的函数：如果a-b有偶数个，则可以规定返回前一半数字认为是0；返回后一半数字认为是1，如果a-b有奇数个，认为返回中间的数字重置，直到返回前半数字或者后半数字；生成c-d等价于生成0-d-c，然后再+c；假设d-c用二进制表示有n位，则用0/1生成器决定每一位是0还是1；如果d-c不是n位二进制最大的数，则每次出现n位二进制最大的数，进行重置

f函数以概率p返回0，以概率1-p返回1，调用两次f函数，则可能出现四种结果：00：pp、01：p(1-p)、10：(1-p)p和11：(1-p)(1-p)；出现01和10的概率相等，可以将他们分别与0/1对应；如果出现00或者11，则进行重置

代码实现：

/随机返回1-5
int f() {
	//srand((unsigned)time(NULL));
	return rand() % 5 + 1;
}
//随机生成1-7
int g() {
	int res = 0;
	int i = 0;
	do {
		while (i < 3) {
			int rd = f();
			cout << rd << endl;
			while (rd == 3) {
				rd = f();
				cout << rd << endl;
			}
			if (rd > 3) {
				//置1
				res = (res | (1 << i));
			}
			else {
				res = (res | (0 << i));
			}
			i++;
		}
	} while (res == 7);
	return res + 1;
}


//以概率2/5生成0，以概率3/5生成1
int f2() {
	int rd = rand() % 5;
	return rd < 2 ? 0 : 1;
}
//等概率返回0/1
int g2() {
	int rd1 = f2();
	int rd2 = f2();
	while (rd1 == rd2) {
		rd1 = f2();
		rd2 = f2();
	}
	cout << rd1 << endl;
	cout << rd2 << endl;
	return rd1 > rd2 ? 0 : 1;
}
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

---

题目七

动态规划题目：basecase：1) 0个节点–>空树、2) 1个节点–>1种结构、3) 2个节点–>2种结构

一般情况：假设有N个节点，1) 左树没有节点，右树N-1个节点；2) 左树1个节点，右树N-2个节点…

代码实现：

//暴力递归
int numTrees(int n) {
	if (n < 0) {
		return 0;
	}
	if (n == 0 || n == 1) {
		return 1;
	}
	if (n == 2) {
		return 2;
	}
	int res = 0;
	for (int leftNum = 0; leftNum <= n - 1; leftNum++) {
		int leftWays = numTrees(leftNum);
		int rightWays = numTrees(n - 1 - leftNum);
		res = res + leftWays * rightWays;
	}
	return res;
}
//改动态规划
int numTrees02(int n) {
	if (n < 2) {
		return 1;
	}
	vector<int>dp(n + 1);
	dp[0] = 1;
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			dp[i] = dp[i] + dp[j] * dp[i - 1 - j];
		}
	}

	return dp[n];
}

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

---

题目八

如何判断括号字符串是否完整？遍历字符串，用一个变量count，遇到‘（’count++，遇到‘）’count–；1) 如果遍历过程种count有小于0的时刻，则括号字符串肯定不完整，因为如果出现这种情况，说明‘）’多，而‘）’多后面是每办法再进行匹配了；2) 遍历完之后，count必须等于0，括号字符串才是完整的
对于不完整的括号字符串，这么让他完整？借用上述过程：用一个变量count，遇到‘（’count++，遇到‘）’count–，再用一个变量存储最终的结构res；1) 如果某时刻出现count==-1，res++（count==-1说明‘）’多了，需要在前面补一个‘（’），然后让count置0；2) 如果遍历到最后count>0，说明‘（’多了，需要在后面补count个‘）’

代码实现：

//判断括号字符串是否完整
bool isWhole(string& s) {
	int count = 0;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '(') {
			count++;
		}
		else {
			count--;
			if (count < 0) {
				return false;
			}
		}
	}
	return count == 0 ? true : false;
}
//最少补多少字符使之完整
int needParentheses(string& s) {
	int count = 0;
	int ans = 0;
	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '(') {
			count++;
		}
		else {
			count--;
			if (count < 0) {
				ans++;
				count = 0;
			}
		}
	}
	return ans + count;
}
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

---

总结

本节课讲到三个技巧：窗口不回退模型，当发现窗口的左右边界可以不回退时，算法流程之和左右边界运动的距离有关，很多O(N)的算法是这么加工而来的。打表，当发现输入参数和输出参数都比较简单时，利用笨方法找规律改代码。数据预处理，当定出流程，发现查询很频繁，代价很大，想办法将查询变成O(1)级别的查询