前缀和
前缀和的定义：
给定数组 nums，我们可以定义前缀和数组 prefix_sum，使得 prefix_sum[i] = nums[0] + nums[1] + ... + nums[i-1]。
这样，对于任何子数组 [l, r]，其和可以通过以下公式计算：
1
|
sum(l, r) = prefix_sum[r + 1] - prefix_sum[l]
|
典型题
437. 路径总和 III
560. 和为 K 的子数组
滑动窗口
滑动窗口
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
|
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
|
其中两处 … 表示的更新窗口数据的地方。
而且，这两个 … 处的操作分别是右移和左移窗口更新操作，它们操作是完全对称的。
套模板要思考下面的问题：
1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
2、什么条件下，窗口应该暂停扩大，开始移动 left 缩小窗口？
3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
典型题
3. 无重复字符的最长子串
76. 最小覆盖子串
递归
视频链接:递归
如何编写递归函数
第一步：确定问题
阶乘：求n的阶乘
1
2
3
|
int factorial(int n) {
}
|
斐波那契问题：求第n个斐波那契数
1
2
3
|
int fibonacci(int n) {
}
|
汉诺塔问题：将n个盘子从A移动到C
1
2
3
|
void hanoi(int n, char A, char B, char C) {
}
|
第二步：解决基准问题（边界条件）
阶乘：当n为0或1时，阶乘为1
1
2
3
4
5
|
int factorial(int n) {
if (n == 1) {
return 1;
}
}
|
斐波那契：当n小于等于2时，答案是1
1
2
3
4
5
|
int fibonacci(int n) {
if (n <= 2) {
return 1;
}
}
|
汉诺塔：当n为1时，直接从A移动到C
1
2
3
4
5
6
|
void hanoi(int n, char A, char B, char C) {
if (n == 1) {
cout << "Move disk 1 from " << A << " to " << C << endl;
return;
}
}
|
第三步：拆解问题
阶乘：n的阶乘等于n乘以(n-1)的阶乘
1
2
3
4
5
6
|
int factorial(int n) {
if (n == 1) {
return 1;
}
return n * factorial(n - 1);
}
|
斐波那契：第n个斐波那契数等于第n-1和第n-2个斐波那契数之和
1
2
3
4
5
6
|
int fibonacci(int n) {
if (n <= 2) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
|
汉诺塔：将n-1个盘子从A移动到B，将第n个盘子从A移动到C，再将n-1个盘子从B移动到C
1
2
3
4
5
6
7
8
9
|
void hanoi(int n, char A, char B, char C) {
if (n == 1) {
cout << "Move disk 1 from " << A << " to " << C << endl;
return;
}
hanoi(n - 1, A, C, B);
cout << "Move disk " << n << " from " << A << " to " << C << endl;
hanoi(n - 1, B, A, C);
}
|
思维小技巧
在编写函数时，可以当系统库中有一个同名函数，能实现你所需要的功能，直接调用即可。
典型题
138. 随机链表的复制
哈希表
更多是起到一个辅助
典型题
1. 两数之和
236. 二叉树的最近公共祖先
