算法题笔记-Hot100

Remember, you are not a solution machine. You are a builder.
笔记是个人思路的速记，不完整，详细的请直接参考题解。
自 2025-5 开始记录，之前做的题会在重做的时候更新，更完后此纪录会删除

动态规划

分割等和子集

给你一个  只包含正整数  的  非空  数组  nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

这道题是 01 背包问题的一个变种，问题可以看成在整个数组当中能不能挑出一些数使得这个数刚好是总和的一半。这里就有两个限制条件首先是数组的总和必须是偶数才能够被等分，另一个是数组当中的最大元素不能超过总和的一半。用dp[i][j]表示数组前 i 个数能不能选出一些数使得总和等于 j，我们需要构造出这个二维数组，它的大小是：（数组元素的个数和速度总和的一半+1）
接下来是初始化，

  • 所有元素都能够构造出一颗总和为零的值，只要不选就可以.
  • dp[0]只能构造出 0 和nums[0]这两个总和
    构造这个二维数组，状态转移是遍历数组当中的数，考虑是不是把它加进背包当中。如果这个数已经大于了 j，那么直接不选；如果小于 J 那么可选可不选。这里要好好理解 dp[i][j] 的含义：能在前 i 个数凑出总和为 j 的情况只能是 dp[i-1][j-nums[i]] == true 刚好加上nums[i]；或者不选这个数，在此之前就能凑够。
1
2
3
4
5
6
7
8
9
for(int i = 1; i < nums.size(); i++){
	for(int j = 0; j <= target; j++){
		if(nums[i] > j)
			dp[i][j] = dp[i-1][j];
		else{
			dp[i][j] = dp[i-1][j-nums[i]] || dp[i-1][j];  // 这里用到的就是dp的核心，能不能凑出总和j，在于选不选nums[i]
		}
	}
}

最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。

回文串特性是判断回文要依赖子串，这道题先遍历子串的长度从 1…..n，这样利用之前得到的子串长度就能判断了，不需要倒着遍历。不过这样子时间复杂度有点高是$O(n^2)$ ,也有一些技巧比如说判断首尾字符相等的时候如果字串长度<3 那么直接判断为回文串。只有在判断回文串的长度能不能扩展的时候用到了动态规划的思想，这道题重点更在于对一个长串进行两层子串的遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for(int L = 2; L <= len; L++){
	for(int i = 0; i < len; i++){
		int j = i + L -1;

		if(j >= len)
			break;
		if(s[i] == s[j]){
			if(j - i < 3)   dp[i][j] = true;
			else    dp[i][j] = dp[i+1][j-1];  // 子串可以扩展
		}else{
			dp[i][j] = false;
		}

		if(dp[i][j]){
			maxlen = max(maxlen, j-i+1);
			begin = i;
		}
	}
}

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

初始化的时候要注意不能从 0 开始，要么同时初始化 00 01 10 不然就用偏移数组的方法.因为会用到
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

1
2
3
4
5
6
7
8
9
10
11
12
for(int i = 1; i <= n; i++){
	for(int j = 1; j <= m; j++){
		if(text1[i-1] == text2[j-1]){  // 偏移了，相当于把(i-1, j-1)记录在dp[i, j], 最后返回的时候是dp[n][m]
			dp[i][j] = dp[i-1][j-1] + 1;
			// lcs = max(lcs, dp[i][j]);
		}else{
			dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
		}
		lcs = max(lcs, dp[i][j]);
	}
}
return lcs;

编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

理解 word1 怎么进行操作会变成 word2，还是有最优子结构的。插入考虑的是(i, j-1 )的情况下，word1 再插入word2[j] ；删除是 word1 多了，考虑(i-1, j)+1, 替换是都后退

1
2
3
4
5
6
7
8
9
for(int i = 1; i <= n;i++){
	for(int j = 1; j <= m; j++){
		if(word1[i-1] == word2[j-1])
			dp[i][j] = dp[i-1][j-1];
		else{
			dp[i][j] = min(dp[i-1][j]+1, min(dp[i-1][j-1]+1, dp[i][j-1]+1));
		}
	}
}

链表

LRU cache

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
    函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

这道题的思路是要求在 O1 的时间内实现插入和更新，如果只使用链表的话那么遍历整个链表，寻找到需要更新的需要 $O(n)$ 时间复杂度。考虑只使用链表的话同时还需要维护每一次被访问后的更新值，用来在内存满的时候删除最久未使用节点。如果只使用哈希表，怎么没有办法维护LRU满的情况。

实现的方式是：哈希表实现 get 的 O1 定位，每一次的访问后把节点提前到链表首部，如果满了就删除链表末尾的节点（最久未使用/访问）。
注意这里只有在 cache 满的时候才会删除节点 delete ，更新节点并不需要删除节点，只需要移动，这里就是双向链表的好处。注意，这里 head，tail 都是固定的节点，不包含真正的数据。map 记录了key -> node* 关系，如果要删除节点需要删除哈希表项。每一次的更新都是删去老节点，增加新结点，避免了在链表当中移动节点。在这个过程当中哈希表项也是变化的，因为记录的节点指针不同。

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
int get(int key) {
	if(map.find(key) == map.end())
		return -1;

	Node* iter = map[key];
	// 已经更新了键值对，不能直接返回
	remove(iter);
	add(iter);
	return iter->val;
}

void put(int key, int value) {
	if(map.find(key) == map.end()){
		Node* p = new Node(key, value);
		if(map.size() == cap){
			Node* last = tail->pre;
			removeLast();
			map.erase(last->key);
			delete(last);
		}
		add(p);
		map[key] = p;
	}else{
		Node* p = map[key];
		p->val = value;
		remove(p);
		add(p);
	}
}
.....
void remove(Node* node){
	node->pre->next = node->next;
	node->next->pre = node->pre;
}

// 新节点放在最前面
void add(Node* node){
	node->next = head->next;
	head->next->pre = node;
	head->next = node;
	node->pre = head;
}

void removeLast(){
	tail->pre->pre->next = tail;
	tail->pre = tail->pre->pre;
}

K 个一组反转链表

创建一个虚节点对每 k 各一组的节点进行翻转，还需要连接下一组的起始节点，HARD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
while(true){
	ListNode* tail = pre;
	for(int i = 0; i < k; i++){
		tail = tail->next;
		if(tail == nullptr)
			return dummy->next;
	}

	ListNode *nextGroup = tail->next;
	ListNode* index = pre->next, *prev = nextGroup;

	while(index != nextGroup){
		ListNode* tmp = index->next;
		index->next = prev;
		prev = index;
		index = tmp;
	}

	ListNode* oldhead = pre->next;
	pre->next = tail;
	pre = oldhead;   // 现在oldhead是反转过后的尾节点，正好是下一组要反转的前一个节点
}

随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

todo

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
Node *new_head = new Node(head->val), *p = head, *q = new_head;
int index = 0;

while(p){
	if(p->next){
		q->next = new Node(p->next->val);
		listmap[p] = index;
		newmap[index] = q;
		index++;
		p = p->next;
		q = q->next;
	}
	else{
		listmap[p] = index;
		newmap[index] = q;
		q->next = nullptr;
		p = p->next;
		q = q->next;
	}
}

for(q = new_head, p = head; p || q; p = p->next, q = q->next){
	if(p->random == nullptr) { q->random = nullptr; continue;}
		
	int random_index = listmap[p->random];
	q->random = newmap[random_index];
}

合并 k 个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

所有链表的表头都放到最小堆里，每次产生一个最小值加到新链表的末尾，如果判断使用的节点还有 next 节点下一个节点也加入到堆当中。注意维护如果一个链表为空，则不继续添加。

1
2
3
4
5
6
7
8
9
10
while(!heap.empty()){
	ListNode* curr = heap.top();
	index->next = curr;
	index = index->next;

	heap.pop();
	if(curr->next)  // 后面还有节点
		heap.push(curr->next);

}

双指针

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

两数之和的解法是用哈希表，边遍历边查表几乎只需要 $O(n^2)$ 时间复杂度即可。哈希表相当于一层快速查询，那么三数之和就需要固定两个游标，这样的确可以快速找到一个解，但是不能继续移动维护游标。考虑去重的话，也不好操作。所以三数 四叔都是用双指针写法，排序后固定一个数，之后进行剪枝和双指针查询。

具体剪枝是在找到一个三数之和等于0下，跳过了左右指针相同的数字；第一个固定指针相同数字也被跳过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i = 0; i < nums.size(); i++){
	if(i && nums[i] == nums[i-1])
		continue;

	int l = i+1, r = nums.size()-1;
	while(l < r){
		int sum = nums[i] + nums[l] + nums[r];
		if(!sum){
			ans.push_back({nums[i], nums[l], nums[r]});
			while(l < r && nums[l] == nums[l+1]) l++;
			while(l < r && nums[r] == nums[r-1]) r--;
			l++, r--;
		}
		else if(sum < 0)    l++;
		else if(sum > 0)    r--;
	}
}

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

滑动窗口

寻找异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

固定目标串长度的窗口，并且每个窗口都是用字母计数桶标记的，依次和匹配串比较，如果两个桶相同，那么就找到了

1
2
3
4
5
6
7
for(int i = 0; i < s.length() - p.length(); i++){
	window[s[i] - 'a']--;
	window[s[i+p.length()] - 'a']++;

	if(arrp == window)
		ans.push_back(i+1);
}

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

窗口内记录无重复字符的子串，是用哈希表判断右指针遇到的字符是不是已经出现过了。如果没有出现，右边界继续移动；否则找到哈希表记录的重复字符索引，左边界跳转。在这个过程中更新最大窗口长度。

1
2
3
4
5
6
7
8
while(r < s.length()){
	if(map.find(s[r]) != map.end() && map[s[r]] >= l){  // 保证L只会向前移动
		l = map[s[r]] + 1;
	}
	map[s[r]] = r;
	maxw = max(maxw, r-l+1);
	r++;
}

栈

柱状图中的最大矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
输入： heights = [2,1,5,6,2,3]
输出： 10

限制这道题面积的是长和宽，我们尽量找更高的矩形，尽可能的拓宽宽度边界。这道题的思路是：找到一个区间确保能快速找到左右的比他低的索引，保证除了这两个边界，这个范围内最低的高度就是它本身，即高度。相当于一个 “凹” 字形，计算出来的矩形面级物理意义是：当前柱子高度作为某个区间内的最矮，以此计算可能的最大面积。保证了当前柱子这是用单调栈做到的，和下面的接雨水题目很类似，思想是共通的。

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 0; i < n; ++i) {
	// 当前柱子高度 < 栈顶柱子高度，说明可以结算了，不满足单调特性
	while (!st.empty() && heights[i] < heights[st.top()]) {
		int height = heights[st.top()];  // 当前出栈柱子的高度
		st.pop();

		int right = i;
		int left = st.top();  // 出栈后的栈顶是“左边第一个比它矮的”
		int width = right - left - 1;  // 注意这里要减去两个边界，非常迷惑，其实是一个“凹”区间
		maxArea = max(maxArea, height * width);  // 最低高度
	}
	st.push(i);  // 当前柱子入栈
}

接雨水

单调栈的做法，构成一个单调减的栈，出现高的柱子代表出现了一个洼地，可以计算这一部分的雨水。雨水的计算是分割成一个又一个小块的，最终堆出来。

1
2
3
4
5
6
7
8
9
10
11
for(int i = 0; i < height.size(); i++){
	while(!st.empty() && height[i] > height[st.top()]){
		int bottom = st.top();
		st.pop();
		if(st.empty())
			break;
		int left = st.top();
		ans += (min(height[i], height[left]) - height[bottom]) * (i - left - 1);
	}
	st.push(i);
}

每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

单调栈的典型题目。维护一个单调递减的温度序列，如果下一个温度违反了单调性，那么依次将栈中的温度 pop，计算索引之间的差（即下一个更高的温度天数）。

1
2
3
4
5
6
7
8
9
10
11
for(int i = 0; i < temperatures.size(); i++){
	if(tem.empty())
		tem.push(make_pair(i, temperatures[i]));
	else{
		while(!tem.empty() && tem.top().second < temperatures[i]){
			ans[tem.top().first] = i - tem.top().first;
			tem.pop();
		}
		tem.push(make_pair(i, temperatures[i]));
	}
}

字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
例如：s = "3[a]2[bc]" 输出："aaabcbc"

解题的思路是一直记忆最长的匹配到的字符串 currentString，如果出现了 [，就表示 currentString 需要清空给 [ 里面的字符串重复操作。用 numstack 维护需要重复的次数，] 遇到之后进行结算。同时测试样例还给了 []嵌套出现的例子，我们临时的string需要保存在栈中，这样不会进入下一个 [的时候丢失前面的string导致连不上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for(auto ch : s){
	if(ch >= '0' && ch <= '9'){
		n = n*10 + ch - '0';
	}else if (ch >= 'a' && ch <= 'z'){
		currentString += ch;
	}else if(ch == '['){
		numStack.push(n);  // []内部需要循环多少次，在这里保存
		stringStack.push(currentString);  // []可能是嵌套递归出现的，所以暂时的string都需要保存下来
		currentString.clear();
		n = 0;
	}else if(ch == ']'){
		int times = numStack.top();
		string loop = "";
		while(times--){
			loop += currentString;
		}
		currentString = stringStack.top() + loop;
		stringStack.pop();
		numStack.pop();
	}

}

堆

寻找数据流的中位数

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。
  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

维护一个最小堆和最大堆，这里理解上相反。小于中位数的位于最大堆，top 是最接近中位数的；同样，大于中位数的是最小堆。每次先把数加到最大堆，然后给最小堆 top。如果不满足两个堆个数相差 1，则进行调整。这里就是维护中位数了。具体来说是哪一步保证了两个堆的堆顶就是中位数区间呢？是判断大顶堆和小顶堆个数相差 1，并且大顶堆进行了内部的调整（包括小顶堆的内部调整）共同来决定的。

至于为什么是相差 1，是为了正好平分找到中位数，不过不能直接修改相差值找中位数后的第 N 大数
如果要找到第 K 大的数，可以维护一个大小为 K 的最小堆，不断遍历加入所有的数，最后堆顶就是第 K 大的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
priority_queue<int, vector<int>, less<int>> minHeap;  // 初始化大顶堆的比较函数是less<int>
priority_queue<int, vector<int>, greater<int>> maxHeap;
……

void addNum(int num) {
	if(minHeap.size() == 0 || num < minHeap.top()){
		minHeap.push(num);
		if(maxHeap.size() + 1 < minHeap.size()){
			maxHeap.push(minHeap.top());
			minHeap.pop();
		}
	}else{
		maxHeap.push(num);
		if(maxHeap.size() > minHeap.size()){
			minHeap.push(maxHeap.top());
			maxHeap.pop();
		}
	}
}

数组

轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。要求只使用 $O(1)$ 的空间复杂度。

轮转的思路是从第K个位置将数组分为两半，分别对两段进行倒置，最后对整个数组在倒置，即可达成数组元素向右轮转K个位置的效果。至于对每一段进行倒置，用类似双指针的思路只需要 $O(1)$ 空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void rotate(vector<int>& nums, int k) {
	int size = nums.size();
	int p1 = size - (k%size) -1;
	rearray(nums.begin(), nums.begin()+p1);
	rearray(nums.begin()+((p1+1)%size), nums.end()-1);
	rearray(nums.begin(), nums.end()-1);

}

void rearray(vector<int>::iterator begin, vector<int>::iterator end){
	for(; begin <= end; begin++, end--){
		int tmp = *begin;
		*begin = *end;
		*end = tmp;
	}
}

最小缺失的正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

数组重新置位的方法感觉比较有趣，对每一个 nums[i] 都去正确的位置 nums[nums[i] - 1] ，这里暗示了能够处理的只有 val 属于(1, nums.size)范围内，如果超出了范围，保持不动。如果超出了数组的长度，这个数在数组当中就会被保留，最后检查的时候就会发现这个数是错误的。以290 300 310 3个数字为例，这三个数字在调换位置的时候都不会动，但是检查的时候会发现第一个299就不符合规则直接返回1，其余的也类似。

在调换位置的时候对每一个检查的位置都会不断的把 A 位置放到它应该去的位置，并且把替换的位置 B 不断地重复操作，直到替换的 B 位置正好和 A 位置的值相同那么就可以迭代下一个位置。

1
2
3
4
5
6
7
8
9
10
11
for(int i = 0; i < nums.size(); i++){
	while(nums[i] > 0 && nums[i] < nums.size() && nums[i] != nums[nums[i]-1]){
		swap(nums[i], nums[nums[i]-1]);
	}
}

for(int i = 0; i < nums.size(); i++){
	if(nums[i] != i+1){
		return i == 0 ? 1 : nums[i-1]+1;
	}
}

子串

[!tip]
滑动窗口是子串中经常出现的，核心是找到移动左右边界的情况，在循环中不断移动边界，在所有的极值中找到最值。判断什么情况要移动边界是有针对题目的技巧，下面有题目思考。

滑动窗口最大值

维护一个单调递减的双端队列，这个队列向右滑动的时候，判断如果比队列当中最后一个数还要大那么就循环弹出队列尾部，这里面的道理是：因为新进来的数要比原窗口当中的数要大，并且它的位置更靠右，所以后面要找窗口内的最大值一定找更”新“的，并且它的值还更大，那么就肯定不会用到那些被弹出的数。那么窗口什么时候缩小呢？检查 队列队首元素它的下标如果不满足窗口的长度，那么就可以把它弹出去了，因为它已经不在窗口里了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i = 0; i < nums.size(); i++){
	while(!q.empty() && nums[q.back()] < nums[i]){
		q.pop_back();
	}

	// 可能会出现队列当中的数要小于窗口长度, 因为上一个循环弹出的数太多了也有可能
	q.push_back(i);
	if(q.front() < i-k+1){
		q.pop_front();
	}

	if(i >= k-1)
		ans.push_back(nums[q[0]]);
}

最小窗口

找到串中包含目标穿的最小子串，窗口就必然是要伸缩的。为了确认重复字符，数量也需要考虑。哈希表维护目标串和当前窗口内字符种类和数量，右指针不断移动，在找到了包含完整的一个目标串后，左指针尝试能不能右移，更新最小值。注意维护窗口的哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 while(r < s.size()){
	cnt[s[r]]++;

	while(check() && l <= r){
		if(r-l+1 < len){
			len = r - l + 1;
			ans = l;
		}

		cnt[s[l]]--;
		l++;
	}
	r++;
}

最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

还是用哈希表存储目标串和窗口串的字符种类和数量，因为需要考虑到重复字符的出现所以必须是哈希 map。算法是首先找到一个包含目标串的子串（如果不满足 check 函数的话右边界会一直向右）然后在不断尝试缩小窗口（ 重要，否则左边界没办法移动，不可以找到一个极值之后直接跳跃左边界） ，每一次缩小窗口都会减去窗口哈希表里面的项，同时更新最小长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
while(r < s.size()){
	cnt[s[r]]++;

	while(check() && l <= r){
		if(r-l+1 < len){
			len = r - l + 1;
			ans = l;
		}

		cnt[s[l]]--;
		l++;
	}
	r++;
}

和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

简单的我们可以用前缀和数组查找整个数组中某一段子数组是不是存在 sum == K 的情况，由于每一次都是检查任意的中间一段所以这种遍历是全局的，没有遗漏。时间复杂度是 $O(n^2)$ ，也可以说这是一种窗口。

1
2
3
4
5
6
7
8
for(int i = 1; i <= nums.size(); i++){
	for(int j = i; j<= nums.size(); j++){
		int m = sum[j] - sum[i-1];

		if(m == k)
			cnt++;
	}
}

或者可以用哈希表来简化查找是否存在这个步骤，保留每个前缀在哈希表中的 count，如果发现 mp.find(pre - k) != mp.end() 那么就表示中间的一段 sum == K。子数组的解是可以复用的，边遍历边查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
int subarraySum(vector<int>& nums, int k) {
	unordered_map<int, int> mp;
	mp[0] = 1;
	int count = 0, pre = 0;
	for (auto& x:nums) {
		pre += x;
		if (mp.find(pre - k) != mp.end()) {
			count += mp[pre - k];
		}
		mp[pre]++;
	}
	return count;
}

树

二叉树中的最大路径和

找到二叉树中的最大路径和，抽象出一个小二叉树，全局的最大路径可能是包含了顶点的，也可能是路径的一个边不包含顶点。所以对于全局来说，要更新的是 maxLen = max(maxLen, node->val+left+right) ，递归到某一层的时候，不能把一个经过顶点的路径交给上层，也就是上层不能在下面分叉处两条路，所以是 return node->val + max(left, right) 。注意这里可能出现左右子树的最长路径和为负数，要及时终止：找的路径不一定是要从最下面层开始，递归只返回一个节点也是可以的。

1
2
3
4
5
6
7
8
9
10
11
12
13
int maxhelper(TreeNode* node){
	if(!node)
		return 0;
	if(node->left == nullptr && node->right == nullptr){
		maxLen = max(node->val, maxLen);
		return node->val;
	}
	int left = max(0, maxhelper(node->left));
	int right = max(0, maxhelper(node->right));

	maxLen = max(maxLen, node->val+left+right);
	return node->val + max(left, right);    // 也可能子节点都是负数，不选子节点也可以
}

图论

DFS 或者 BFS

岛屿数量

这道题用 DFS 的方法解决，依次遍历二维网格的每一个点，如果发现当前是岛屿，那么就继续向下探索其他附近的岛屿。一直不断递归。如果是岛屿那么就把网格当中这个格子给重新标记，注意这里是一个不会被使用的值。如果 DFS超出了数组范围的话或者识别当前已经到了岛屿的水，那么就应该返回。这样回到最初的遍历所有和岛屿相关的格子都已经被标记过，不会重复叠加，这样就可以数出正确的岛屿。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int numIslands(vector<vector<char>>& grid) {
	int n = grid.size(), m = grid[0].size();
	int count = 0;
	for(int i = 0; i < grid.size(); i++){
		for(int j = 0; j < grid[0].size(); j++){
			if(grid[i][j] == '1'){
				count++;
				dfs(grid, i ,j);
			}
		}
	}
	return count;
}

void dfs(vector<vector<char>>& grid, int x, int y){
	if(x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] != '1')
		return ;
	grid[x][y] = '#';
	dfs(grid, x+1, y);
	dfs(grid, x-1, y);
	dfs(grid, x, y+1);
	dfs(grid, x, y-1);
}

腐烂的橘子

这道题的要求是输出腐烂的时间数，所以可以用每一轮的腐烂来模拟，是一个 BFS。需要注意每一次处理腐烂的是上一轮新增的腐烂橘子，只有在这一轮腐烂的橘子都处理完之后时间数才会自增。直到没有新增的腐烂橘子为止。队列当中存放的是腐烂的橘子，代码执行的时候队列里的元素应该是增长又减少的。
gpt 写的比我好，四个方向的处理很优雅。

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
std::array<std::pair<int, int>, 4> directions = {{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
queue<pair<int, int>> rote;
while(!rote.empty()) {
	int size = rote.size();
	bool rottedThisRound = false;

	while(size--) {
		auto [x, y] = rote.front();
		rote.pop();

		for(auto [dx, dy] : directions) {
			int nx = x + dx, ny = y + dy;
			if(nx >= 0 && ny >= 0 && nx < m && ny < n && grid[nx][ny] == 1) {
				grid[nx][ny] = 2; // 腐烂新鲜橘子
				rote.emplace(nx, ny);
				freshCount--;
				rottedThisRound = true;
			}
		}
	}

	if(rottedThisRound) minute++;  // 只有实际腐烂时才增加时间
}
// 还有新鲜橘子没腐烂到
return freshCount == 0 ? minute : -1;

课程表

思想是检查一个数组链当中会不会出现环，由于每一次都需要对前置课程进行确认，所以不断的前置就构成了 DFS。访问过的课程标记，并且加上了优化（如果确认到达某一个课程之前的所有课程都不会出现依赖闭环，那么就可以在这里截止）。
初始化访问数组为0，表示没有检查这个课程；1 表示开始检查此课程，接下来要对所有的依赖课程检查，并且不断递归。如果检查到了合法的课程，那么最后的 for 遍历应该会顺利结束（因为最后一个课程不会依赖一个环，会直接到 visited[course] = 2 ）。最后依次返回，2 表示访问的课程已经检查过了是合法的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> visited(numCourses, 0);
for(int i = 0; i < numCourses; i++){
	if(!dfs(graph, i, visited))  return false;

}
......
bool dfs(vector<vector<int>>& graph, int course, vector<int>& visited){
	if(visited[course] == 1)    return false;
	if(visited[course] == 2)    return true;  // 提前返回，优化

	visited[course] = 1;
	for(auto c : graph[course]){
		if(!dfs(graph, c, visited))     return false;

	}
	visited[course] = 2;
	return true;
}

动态规划

最长有效匹配括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

用的是栈的方法。栈记录的是索引，每当发生一次 () 匹配，就应当更新一下最长的长度 i-st.top()，其中 i 是移动的游标，栈顶表示最远没有匹配的 ( ，两者的差就是一次可能的最大值。这里还要加上一个分界节点，如果起点开始就是 ) ，或者栈中的符号都被匹配清空了，开始下一轮结果开始碰到了 ( 那应该要及时跳过。所以可以理解一下，多个匹配串中间夹着不能匹配的之后又碰到了，就是这个起点不断更新的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
st.push(-1);
for(int i = 0; i < s.length(); i++){
	if(s[i] == '(')
		st.push(i);
	else{
	   st.pop();
	   if(st.empty())
			st.push(i); 
		else{
			maxlen = max(maxlen, i-st.top());
		}
	}
}

回溯

全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

回溯本质上还是一个递归的算法，终止条件是：如果找到的路径元素个数是原数组个数的话那么就把它加到结果集里面。每一次遍历的时候还要维护一个只用数组，因为这里要求的是不重复元素，所以已经添加的路径元素不能在下一次递归的时候使用，需要用一个全局的使用数组标记。传入的是一个空路径然后每一次递归的时候添加一个元素进去，直到元素满了中止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void backtrack(vector<int> &nums, vector<int> &path, vector<bool> &used, vector<vector<int>> &result){
	if(path.size() == nums.size()){
		result.push_back(path);
		return ;
	}

	for(int i = 0; i < nums.size(); i++){
		if(used[i]) continue;

		path.push_back(nums[i]);
		used[i] = true;

		backtrack(nums, path, used, result);

		path.pop_back();
		used[i] = false;
	}
}

子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

这些问题和全排列不同是，在搜索的过程当中每一个中间的结果都需要加到结果集里面，他改变的一点是每一次自己只是在后面的元素当中去找，不会向前搜索已经遍历过的元素。[2,1] 和 [1,2]是重复的，但是[1,2] 和 [2,1] 是不同的排列！ 所以子集问题传入了一个开始下标 (这种也是一种剪枝)

1
2
3
4
5
6
7
8
9
10
11
12
13
void backtrack(vector<int> &nums, vector<vector<int>> &result, vector<int> path, int startIndex){  //这里是下标
	result.push_back(path);
	if(path.size() == nums.size())  return ;

	for(int i = startIndex; i < nums.size(); i++){
		path.push_back(nums[i]);

		backtrack(nums, result, path, i+1);

		path.pop_back();

	}
}

电话号码的组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 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
vector<string> letterCombinations(string digits) {
	unordered_map<char, string> map = {
		{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
		{'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
	};
	vector<string> result;
	string path;
	backtrack(map, digits, path, result, 0);
	return result;
}
    
void backtrack(unordered_map<char, string> &map, string &digits, string &path, vector<string> &result, int startIndex){
	if(digits.length() == path.length()){
		if(digits.length() != 0)
			result.push_back(path);
		return;
	}
	for(int i = startIndex; i < digits.length(); i++){
		for(char c : map[digits[i]]){
			path.push_back(c);
			backtrack(map, digits, path, result, i+1);
			path.pop_back();
		}
	}
}

组合总和

递归很容易想到，只要一直去减列表数组里的数就可以。然后下一次迭代的时候，传入的目标数是减过后的数。这道题不一样的地方是，它一个数字可以用多次，但还是需要去掉重复组合。所以还是子集做题的思路，不过这一次不需要从下一个数开始找，从当前数找就可以，因为可以用多次。终止的条件是，如果目标数被减到了零，那么说明这个组合的和就是 target；如果小于零那么这个搜索就不成立直接返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void backtrack(vector<int>& candidate, int target, vector<vector<int>>& result, vector<int> path, int start){
	if(target == 0){
		result.push_back(path);
		return ;
	}else if(target < 0)
		return ;

	for(int i = start; i < candidate.size(); i++){
		int num = candidate[i];
		path.push_back(num);
		// target -= num;
		backtrack(candidate, target-num, result, path, i);
		path.pop_back();
	}
}

单词搜索

从找到的第一个字符找到开始继续向下搜索，只能上下左右搜索，带着下标一起，如果下标达到了目标字符串的长度就确定找到，立刻停止所有地搜索（剪枝优化）。注意不能重复使用之前的格子，可能会绕了一圈回到之前的，虽然本来没有带入原下标搜索，所以每一个搜索的位置都要标记，搜完了再回填。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void backtrack(vector<vector<char>>& board, string word, int x, int y, int index){
	if(ans) return;  // 全局的，一旦某个搜索找到，立刻停止所有递归
	if(x >= board.size() || y >= board[0].size() || x < 0 || y < 0 || board[x][y] != word[index])
		return ;
	else if(index == word.size()-1 && board[x][y] == word[index]){
		ans = true;
		return ;
	}else{
		char tmp = board[x][y];
		board[x][y] = '#';
		backtrack(board, word, x+1, y, index+1);
		backtrack(board, word, x, y+1, index+1);
		backtrack(board, word, x-1, y, index+1);
		backtrack(board, word, x, y-1, index+1);
		board[x][y] = tmp;
	}
}

分割回文串

思路类似，依次从字符串的开始遍历，字串长度不断递增，如果发现前面的串是回文串，就把后面的字符串分割出来传递给下一个继续迭代。回溯体现在一个搜索结束之后，是要把他之前的每一步向下搜索都要抹去，这样才能记录所有其他的路径。最后传递的是空串，搜索结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void backtrack(string s, vector<vector<string>>& result, vector<string>& path){
	// 怎么处理结束呢
	if(s.empty()){
		result.push_back(path);
		return ;
	}

	int len = s.length();
	// 如果substr(s.length)会返回一个空字符串
	for(int i = 1; i <= s.length(); i++){
		if(check_palindrome(s.substr(0, i))){
			path.push_back(s.substr(0, i));
			backtrack(s.substr(i, len-i), result, path);
			path.pop_back();  // 回溯
		}
	}
}

N 皇后

还是回溯的思路，一层一层的判断，如果到达了最后一层，那么就表示找到了一种符合 N 皇后的排列局面。所以只需要对每一个 col 进行遍历看能否放皇后，如果可以就进入下一层，然后再消除痕迹。这里比较巧妙的就是判断了，行列对角线。行不会出现重复，列、对角线需要的。这里用的是哈希表维护每一个局面的用到的列、对角线，在返回上级的时候也需要擦除痕迹。

写的时候还要注意，string 是一行，vector<string>代表一个局面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int row, vector<string>& board){
	if(row == N){
		ans.push_back(board);
		return ;
	}

	for(int j = 0; j < N; j++){
		if(check(row, j)){
			board[row][j] = 'Q';
			colMark.insert(j), masterMark.insert(row-j), secondMark.insert(row+j);
			dfs(row+1, board);
			colMark.erase(j), masterMark.erase(row-j), secondMark.erase(row+j);
			board[row][j] = '.';
		}
	}
}

技巧

只出现一次的数字

位运算

多数元素

简单哈希表，不需要用迭代器判断是否为空，kv map 可以直接 map[i] = num, 也可以简化边插入边判断

1
2
3
4
5
6
7
 for(int num: nums){
	map[num]++;
	if(map[num] > half){
		ans = num;
		break;
	}
}

颜色分类

三个数字的排序问题但是这里要求原地进行更改所以用三指针方法，左指针左边的是 0，右指针右边的是 2，中间是待整理的。遍历整个数组进行排序：和 high 减缓的时候 i 不能移动，此时还不清楚 i 之后的位置元素，没有被整理，所以交换来的还需要再次检查，i 不动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int low = 0, high = nums.size()-1;

for(int i = 0; i < high;){
	if(nums[i] == 0){
		swap(nums[i], nums[low]);
		low++;
		i++;
	}else if(nums[i] == 1){
		i++;
	}else if(nums[i] == 2){
		swap(nums[i], nums[high]);
		high--;
	}
}

下一个排列

从数组最后开始扫描，目标是找到递减序列，然后之前的一个拐点，后面都是递减序列的话，怎么调变得更小，不会变大。所以找到拐点之后，和后面的比他稍大一点的数交换，并且把后面的递减序列改成递增序列，这样就是最小的下一个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for(int i = nums.size()-2; i >= 0; i--){
	if(nums[i] < nums[i+1]){
			turn = i;
			break;
		}
	}
	if(turn != -1){
		for(int i = nums.size()-1; i > turn; i--){
			if(nums[i] > nums[turn]){
				next = i;
				break;
			}
		}
	}

	if(turn != -1 && next != -1){
		swap(nums[turn], nums[next]);
		reverse(nums.begin()+turn+1, nums.end());
	}else{
		reverse(nums.begin(), nums.end());
}

寻找重复数

把数组看成一个链表，不重复的数字就是每一个不同的节点，重复的数字相当于有环，用检测环的快慢指针法可以找到。

1
2
3
4
5
6
7
8
9
10
11
12
13
int fast = 0, slow = 0;
do{
	slow = nums[slow];
	fast = nums[nums[fast]];
}while(slow != fast);

slow = 0;
do{
	slow = nums[slow];
	fast = nums[fast];
}while(slow != fast);

return slow;
技术笔记 > 算法题
#算法
算法题笔记-Hot100
http://whale-withme.github.io/leetcode-hot100/
作者
yzc
发布于
2025年5月31日
许可协议