19/03/2023 更新：119 题都写完了，接下来简单复盘+补充其他解法和思路
001. 整数除法
https://leetcode.cn/tag/hash-table
位运算·数学·1
// 重点处理溢出
002. 二进制加法
https://leetcode.cn/tag/math
位运算·数学·字符串·模拟·1
2
3
4// 逆序运算
auto ite = a.rbegin();
while ( ite < a.rend());
003. 前 n 个数字二进制中 1 的个数
https://leetcode.cn/tag/simulation
位运算·动态规划·1
2// 移位运算
004. 只出现一次的数字
https://leetcode.cn/tag/dynamic-programming
位运算·数组·1
// 利用位运算
005. 单词长度的最大乘积
https://leetcode.cn/tag/array
位运算·数组·字符串·1
2
3// 位运算掩码
// 使用 int 表示
mask |= 1<<(word[j]-'a');006. 排序数组中两个数字之和
https://leetcode.cn/tag/string
数组·双指针·二分查找·1
// 双指针剪枝
007. 数组中和为 0 的三个数
https://leetcode.cn/tag/binary-search
数组·双指针·排序·1
2
3
4
5
6
7// 三元组如何不重复
(a){
(b c){
// 双指针
}
}
// 每一重循环内，相邻两个遍历的元素不同008. 和大于等于 target 的最短子数组
https://leetcode.cn/tag/sorting
数组·二分查找·前缀和·滑动窗口·1
2
3// 数组全是正整数
// 1) 前缀和 + set::lower_bound() 即二分查找
// 2) 滑动窗口009. 乘积小于 K 的子数组
https://leetcode.cn/tag/sliding-window
数组·滑动窗口·1
2// 数组全是正整数
//010. 和为 k 的子数组
https://leetcode.cn/tag/sliding-window
数组·哈希表·前缀和·1
011. 0 和 1 个数相同的子数组
https://leetcode.cn/tag/prefix-sum
数组·哈希表·前缀和·1
012. 左右两边子数组的和相等
https://leetcode.cn/tag/prefix-sum
数组·前缀和·1
013. 二维子矩阵的和
https://leetcode.cn/tag/prefix-sum
设计·数组·矩阵·前缀和·1
014. 字符串中的变位词
https://leetcode.cn/tag/prefix-sum
哈希表·双指针·字符串·滑动窗口·1
015. 字符串中的所有变位词
https://leetcode.cn/tag/sliding-window
哈希表·字符串·滑动窗口·1
016. 不含重复字符的最长子字符串
https://leetcode.cn/tag/sliding-window
哈希表·字符串·滑动窗口·1
017. 含有所有字符的最短字符串
https://leetcode.cn/tag/sliding-window
哈希表·字符串·滑动窗口·1
018. 有效的回文
https://leetcode.cn/tag/sliding-window
双指针·字符串·1
019. 最多删除一个字符得到回文
https://leetcode.cn/tag/string
贪心·双指针·字符串·1
020. 回文子字符串的个数
https://leetcode.cn/tag/string
字符串·动态规划·1
021. 删除链表的倒数第 n 个结点
https://leetcode.cn/tag/dynamic-programming
链表·双指针·1
022. 链表中环的入口节点
https://leetcode.cn/tag/two-pointers
哈希表·链表·双指针·1
023. 两个链表的第一个重合节点
https://leetcode.cn/tag/two-pointers
哈希表·链表·双指针·1
024. 反转链表
https://leetcode.cn/tag/two-pointers
递归·链表·1
025. 链表中的两数相加
https://leetcode.cn/tag/linked-list
栈·链表·数学·1
026. 重排链表
https://leetcode.cn/tag/math
栈·递归·链表·双指针·1
027. 回文链表
https://leetcode.cn/tag/two-pointers
栈·递归·链表·双指针·1
028. 展平多级双向链表
https://leetcode.cn/tag/two-pointers
深度优先搜索·链表·双向链表·1
029. 排序的循环链表
https://leetcode.cn/tag/doubly-linked-list
链表·1
// 如何简化问题？
030. 插入、删除和随机访问都是 O(1) 的容器
https://leetcode.cn/tag/linked-list
设计·数组·哈希表·数学·随机化·1
int randomIndex = rand()%nums.size();
031. 最近最少使用缓存
https://leetcode.cn/tag/randomized
设计·哈希表·链表·双向链表·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
38list<pair<int, int>> ll;
map<int, pair<int, int> *> dict;
class LRUCache {
list<pair<int, int>> l;
unordered_map<int, decltype(l.begin())> m;
int capacity;
public:
LRUCache(int capacity) {
this->capacity = capacity;
}
int get(int key) {
auto ite = m.find(key);
if (ite == m.end()) return -1;
int val = ite->second->second;
l.erase(ite->second);
l.emplace_back(key, val);
m[key] = --l.end();
return val;
}
void put(int key, int value) {
if (m.find(key) != m.end()) {
l.erase(m.find(key)->second);
}
l.emplace_back(key, value);
m[key] = --l.end();
if (m.size() > capacity) {
auto top = l.begin();
m.erase(top->first);
l.pop_front();
}
}
};
032. 有效的变位词
https://leetcode.cn/tag/doubly-linked-list
哈希表·字符串·排序·1
21) 排序比较
2) 哈希表统计033. 变位词组
https://leetcode.cn/tag/sorting
数组·哈希表·字符串·排序·1
034. 外星语言是否排序
https://leetcode.cn/tag/sorting
数组·哈希表·字符串·1
035. 最小时间差
https://leetcode.cn/tag/string
数组·数学·字符串·排序·1
036. 后缀表达式
https://leetcode.cn/tag/sorting
栈·数组·数学·1
037. 小行星碰撞
https://leetcode.cn/tag/math
栈·数组·1
038. 每日温度
https://leetcode.cn/tag/array
栈·数组·单调栈·1
// 单调栈模版题
039. 直方图最大矩形面积
https://leetcode.cn/tag/monotonic-stack
栈·数组·单调栈·1
// 用单调栈：转化矩形面积算法
040. 矩阵中最大的矩形
https://leetcode.cn/tag/monotonic-stack
栈·数组·动态规划·矩阵·单调栈·1
// 分层单调栈
041. 滑动窗口的平均值
https://leetcode.cn/tag/monotonic-stack
设计·队列·数组·数据流·1
042. 最近请求次数
https://leetcode.cn/tag/data-stream
设计·队列·数据流·1
043. 往完全二叉树添加节点
https://leetcode.cn/tag/data-stream
树·广度优先搜索·设计·二叉树·1
044. 二叉树每层的最大值
https://leetcode.cn/tag/binary-tree
树·深度优先搜索·广度优先搜索·二叉树·1
045. 二叉树最底层最左边的值
https://leetcode.cn/tag/binary-tree
树·深度优先搜索·广度优先搜索·二叉树·1
046. 二叉树的右侧视图
https://leetcode.cn/tag/binary-tree
树·深度优先搜索·广度优先搜索·二叉树·1
047. 二叉树剪枝
https://leetcode.cn/tag/binary-tree
树·深度优先搜索·二叉树·1
048. 序列化与反序列化二叉树
https://leetcode.cn/tag/binary-tree
树·深度优先搜索·广度优先搜索·设计·字符串·二叉树·1
049. 从根节点到叶节点的路径数字之和
https://leetcode.cn/tag/binary-tree
树·深度优先搜索·二叉树·1
050. 向下的路径节点之和
https://leetcode.cn/tag/binary-tree
树·深度优先搜索·二叉树·1
2
3// multiset + dfs
// 效率较差
051. 节点之和最大的路径
https://leetcode.cn/tag/binary-tree
树·深度优先搜索·动态规划·二叉树·1
// 分解问题
052. 展平二叉搜索树
https://leetcode.cn/tag/binary-tree
栈·树·深度优先搜索·二叉搜索树·二叉树·1
053. 二叉搜索树中的中序后继
https://leetcode.cn/tag/binary-tree
树·深度优先搜索·二叉搜索树·二叉树·1
054. 所有大于等于节点的值之和
https://leetcode.cn/tag/binary-tree
树·深度优先搜索·二叉搜索树·二叉树·1
055. 二叉搜索树迭代器
https://leetcode.cn/tag/binary-tree
栈·树·设计·二叉搜索树·二叉树·迭代器·1
056. 二叉搜索树中两个节点之和
https://leetcode.cn/tag/iterator
树·深度优先搜索·广度优先搜索·二叉搜索树·哈希表·双指针·二叉树·1
057. 值和下标之差都在给定的范围内
https://leetcode.cn/tag/binary-tree
数组·桶排序·有序集合·排序·滑动窗口·1
2
3
4
5
6
7
8
9
10
11// multiset 和 priority_queue 的区别
// multiset 由 BST 实现，建立的复杂度为 O(N logN)
// priority_queue 由 heap 实现，建立复杂度为 O(N)
// multiset 全部有序，pq 只能进行取堆顶的访问
// multiset 的最小最大值
multiset<int> m;
*m.begin(); // minimum
*m.rbegin(); // maximum
// 如何判断是否有 [x-t,x+t] 之间的数字？058. 日程表
https://leetcode.cn/tag/sliding-window
设计·线段树·二分查找·有序集合·1
2
3
4auto cmp = [&](){}
set<int, decltype(cmp)> c(cmp);
// use stl to perform bin search
c.upper_bound()059. 数据流的第 K 大数值
https://leetcode.cn/tag/ordered-set
树·设计·二叉搜索树·二叉树·数据流·堆（优先队列）·1
// priority_queue
060. 出现频率最高的 k 个数字
https://leetcode.cn/tag/heap-priority-queue
数组·哈希表·分治·桶排序·计数·快速选择·排序·堆（优先队列）·1
2
3
4
5
6// 1) 先遍历一遍，然后用size=k的pq
// 2) 边遍历边维护size=k的pq
// 用 pq + map + set(记录哪些元素已经在pq里)
// 这个方法不行，因为pq没法动态更新
061. 和最小的 k 个数对
https://leetcode.cn/tag/heap-priority-queue
数组·堆（优先队列）·1
2
3
4// priority_queue 的 constructor
std::priority_queue<pair<int,int>, vector<pair<int,int>>, (type of cmp)>(cmp func)
// greater = min-heap
// less = max-heap1
2
3// 复杂小顶堆的实现
// 自定义 greater
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);062. 实现前缀树
https://leetcode.cn/tag/heap-priority-queue
设计·字典树·哈希表·字符串·1
063. 替换单词
https://leetcode.cn/tag/string
字典树·数组·哈希表·字符串·1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17// split 字符串
std::stringstream test("this_is_a_test_string");
std::string segment;
std::vector<std::string> seglist;
while(std::getline(test, segment, '_')){
seglist.push_back(segment);
}
//Member access within misaligned address with linked-list
for(int i=0;i<26;i++){
dict[i] = nullptr;
}064. 神奇的字典
https://leetcode.cn/tag/string
设计·字典树·哈希表·字符串·1
2// 前缀树，带有标记的dfs
065. 最短的单词编码
https://leetcode.cn/tag/string
字典树·数组·哈希表·字符串·1
2// 字典树
// 清理标记位066. 单词之和
https://leetcode.cn/tag/string
设计·字典树·哈希表·字符串·1
067. 最大的异或
https://leetcode.cn/tag/string
位运算·字典树·数组·哈希表·1
2
3
4
5// 转二进制字符串
std::string s = std::bitset<64>( 12345 ).to_string();
// 二进制字符串转数值
bitset<64> bs(res);
long val = bs.to_ulong;068. 查找插入位置
https://leetcode.cn/tag/hash-table
数组·二分查找·1
2
3
4
5
6
7
8
9
10
11// 练习二分查找如何不死循环不重不漏
while(begin<end){
int mid = (begin+end)/2;
if(nums[mid] == target){
return mid;
}else if(nums[mid]>target){
end = mid - 1;
}else{
begin = mid + 1;
}
}069. 山峰数组的顶部
https://leetcode.cn/tag/binary-search
数组·二分查找·1
070. 排序数组中只出现一次的数字
https://leetcode.cn/tag/binary-search
数组·二分查找·1
071. 按权重生成随机数
https://leetcode.cn/tag/binary-search
数组·数学·二分查找·前缀和·随机化·1
2
3
4
5
6
7// 数轴 + 二分查找
std::random_device rd; // Only used once to initialise (seed) engine
std::mt19937 rng(rd()); // Random-number engine used (Mersenne-Twister in this case)
std::uniform_int_distribution<int> uni(min,max); // Guaranteed unbiased
auto random_integer = uni(rng);072. 求平方根
https://leetcode.cn/tag/randomized
数学·二分查找·1
2
3
4while (begin<end-1){
}
// 最后需要判断 end 是否符合073. 狒狒吃香蕉
https://leetcode.cn/tag/binary-search
数组·二分查找·1
2// 最大值
std::max_element(vec.begin(),vec.end());074. 合并区间
https://leetcode.cn/tag/binary-search
数组·排序·1
2
3// 排序后用 priority_queue
// 时间复杂度不佳075. 数组相对排序
https://leetcode.cn/tag/sorting
数组·哈希表·计数排序·排序·1
// 注意，heap不是全排序的，set才是
076. 数组中的第 k 大的数字
https://leetcode.cn/tag/sorting
数组·分治·快速选择·排序·堆（优先队列）·1
2
3
4
5
6
7
8
9// 快速排序
int l = left;
int r = right;
while (l < r) {
while (nums[l] <= pivot && l < r) l++;
while (nums[r] >= pivot && l < r) r--;
swap(nums[l], nums[r]);
}
swap(nums[right], nums[r]);077. 链表排序
https://leetcode.cn/tag/heap-priority-queue
链表·双指针·分治·排序·归并排序·1
2
3
4
5Node* sort(){
l = sort(left);
r = sort(right);
return merge(l, r);
}078. 合并排序链表
https://leetcode.cn/tag/merge-sort
链表·分治·堆（优先队列）·归并排序·1
2//
079. 所有子集
https://leetcode.cn/tag/merge-sort
位运算·数组·回溯·1
2
3
4
5
6
7
8
9
10
11
12void traverse(int cur_pos, vector<int> &nums, vector<int> &cur){
if(cur_pos==nums.size()){
vec.emplace_back(cur);
return;
}
cur.emplace_back(nums[cur_pos]);
traverse(cur_pos+1, nums, cur);
cur.pop_back();
traverse(cur_pos+1, nums, cur);
}080. 含有 k 个元素的组合
https://leetcode.cn/tag/backtracking
数组·回溯·1
081. 允许重复选择元素的组合
https://leetcode.cn/tag/backtracking
数组·回溯·1
082. 含有重复元素集合的组合
https://leetcode.cn/tag/backtracking
数组·回溯·1
2// 如何在回溯时去重
// bfs时，同一层不遍历重复的083. 没有重复元素集合的全排列
https://leetcode.cn/tag/backtracking
数组·回溯·1
// dfs
084. 含有重复元素集合的全排列
https://leetcode.cn/tag/backtracking
数组·回溯·1
// multimap 只能同时删除所有相同的元素
085. 生成匹配的括号
https://leetcode.cn/tag/backtracking
字符串·动态规划·回溯·1
086. 分割回文子字符串
https://leetcode.cn/tag/backtracking
深度优先搜索·广度优先搜索·图·哈希表·1
// dp+记忆化搜索
087. 复原 IP
https://leetcode.cn/tag/hash-table
字符串·回溯·1
088. 爬楼梯的最少成本
https://leetcode.cn/tag/backtracking
数组·动态规划·1
089. 房屋偷盗
https://leetcode.cn/tag/dynamic-programming
数组·动态规划·1
090. 环形房屋偷盗
https://leetcode.cn/tag/dynamic-programming
数组·动态规划·1
// 两轮 dp，实质上也是dp
091. 粉刷房子
https://leetcode.cn/tag/dynamic-programming
数组·动态规划·1
092. 翻转字符
https://leetcode.cn/tag/dynamic-programming
字符串·动态规划·1
// 注意多状态转移，如何设置dp的意义？
093. 最长斐波那契数列
https://leetcode.cn/tag/dynamic-programming
数组·哈希表·动态规划·1
// 二维dp
094. 最少回文分割
https://leetcode.cn/tag/dynamic-programming
字符串·动态规划·1
// 注意如何设置dp子问题
095. 最长公共子序列
https://leetcode.cn/tag/dynamic-programming
字符串·动态规划·1
// TODO：压缩成一维dp
096. 字符串交织
https://leetcode.cn/tag/dynamic-programming
字符串·动态规划·1
// dp, 思考一下怎么设置子问题
097. 子序列的数目
https://leetcode.cn/tag/dynamic-programming
字符串·动态规划·1
// 注意初始化
098. 路径的数目
https://leetcode.cn/tag/dynamic-programming
数学·动态规划·组合数学·1
// 2路转移
099. 最小路径之和
https://leetcode.cn/tag/combinatorics
数组·动态规划·矩阵·1
// 2路转移
100. 三角形中最小路径之和
https://leetcode.cn/tag/matrix
数组·动态规划·1
101. 分割等和子集
https://leetcode.cn/tag/dynamic-programming
数学·字符串·模拟·1
// 背包问题，注意 dp[i][j]表示什么
102. 加减的目标值
https://leetcode.cn/tag/simulation
数组·动态规划·回溯·1
103. 最少的硬币数目
https://leetcode.cn/tag/backtracking
广度优先搜索·数组·动态规划·1
// 三重循环 dp
104. 排列的数目
https://leetcode.cn/tag/dynamic-programming
数组·动态规划·1
// TODO：降维优化
105. 岛屿的最大面积
https://leetcode.cn/tag/dynamic-programming
深度优先搜索·广度优先搜索·并查集·数组·矩阵·1
106. 二分图
https://leetcode.cn/tag/matrix
深度优先搜索·广度优先搜索·并查集·图·1
2// 需要考虑每一个联通分量
// dfs染色107. 矩阵中的距离
https://leetcode.cn/tag/graph
广度优先搜索·数组·动态规划·矩阵·1
2// 队列 bfs
// 图搜索需要记录visited108. 单词演变
https://leetcode.cn/tag/matrix
广度优先搜索·哈希表·字符串·1
109. 开密码锁
https://leetcode.cn/tag/string
广度优先搜索·数组·哈希表·字符串·1
2// 字符串操作复杂度太高，转换为int
// 注意进位退位等问题110. 所有路径
https://leetcode.cn/tag/string
深度优先搜索·广度优先搜索·图·回溯·1
2
3
4// dfs 有向无环图
// 不需要 visited？
// dfs 用 stack 来记录路径111. 计算除法
https://leetcode.cn/tag/backtracking
深度优先搜索·广度优先搜索·并查集·图·数组·最短路·1
2
3
4
5
6// make_pair
vec.emplace_back(make_pair(v1,v2));
// 注意图遍历的 visited 记录
// 可以用 Floyd 算法优化112. 最长递增路径
https://leetcode.cn/tag/shortest-path
深度优先搜索·广度优先搜索·图·拓扑排序·记忆化搜索·数组·动态规划·矩阵·1
2
3
4
5
6
7// no official way of computing hash on pair
unordered_set<pair<int,int>>s; // error
set<pair<int,int>> s; // √
// 记忆化 dfs 复杂度高
// todo：动态规划方法113. 课程顺序
https://leetcode.cn/tag/matrix
深度优先搜索·广度优先搜索·图·拓扑排序·1
2
3
4
5
6
7// unordered_multimap
auto range = map.equal_range(1);
for (auto it = range.first; it != range.second; ++it) {
std::cout << it->first << ' ' << it->second << '\n';
}
// 这题我写的bfs拓扑排序114. 外星文字典
https://leetcode.cn/tag/topological-sort
深度优先搜索·广度优先搜索·图·拓扑排序·数组·字符串·1
// 这题我写的dfs拓扑排序
115. 重建序列
https://leetcode.cn/tag/string
图·拓扑排序·数组·1
2
3
4
5// 拓扑排序然后对比
// 邻接矩阵：vector<vector<int>>
// 序列 [1,2,3] 只需要考虑 1<2, 2<3，为什么？因为偏序关系116. 省份数量
https://leetcode.cn/tag/array
深度优先搜索·广度优先搜索·并查集·图·1
2
3// 并查集，可以优化
void Union(vector<int> &par, int x, int y);
void Find(vector<int> &par, int x);117. 相似的字符串
https://leetcode.cn/tag/graph
深度优先搜索·广度优先搜索·并查集·数组·字符串·1
2// 并查集
// TODO：路经压缩118. 多余的边
https://leetcode.cn/tag/string
深度优先搜索·广度优先搜索·并查集·图·1
119. 最长连续序列
https://leetcode.cn/tag/graph
并查集·数组·哈希表·1
2
3// nlogn: sort+dp
// n: unordered_map