保研随笔录
上一届的夏令营已经陆续结束。一年后的我，又会是怎样的状态？是拿到心仪的 offer，还是全然失败、准备九推？
与其焦虑地等待，不如从头开始提升自我。我将记录这一路的辛酸苦辣，尽管结果未必如意。
起点
从大二下学期期末开始，心里总是隐约不安。大一的全盘失败让我进退两难：科研没有什么成果，绩点甚至没上 90，只能排在专业 50%。在德育分和智育分都不太理想的情况下，我必须在保证绩点的同时做出科研成果。
大二的每一门课程都不是善茬，我的容错太低了，尽管知道很多内容一辈子也不会用上，但我必须强迫自己把这些内容缓存进自己有限的脑容量中。
这已经是我能做到的最大努力，有些老师不当人确实没办法
靓如姐保到了浙软，泽中保到了北大。熟悉的人奔向了不同的去向，我能否和他们一样有一个好的归宿？和他们相比，我欠缺了什么？还有哪些地方可以补足，又有哪些教训值得吸取？我必须认清自己。
不足与应对
| # | 不足 | 应对方案 |
|---|---|---|
| 1 | 代码能力薄弱：看得懂、有概念，但实操能力较差。平时过度依赖 AI 写代码，学院培养方案也不重视实践 | 9 月前学完基础知识；接下来的半年多坚持每天刷算法题，掌握套路与模板。一方面参加校内程序设计大赛、蓝桥杯等比赛，争取德育分；另一方面为夏令营和预推免机试做准备 |
| 2 | 项目经历几乎为 0，缺乏工程实践训练和实习经历 | 大三上学期末开始校外实习，最好是线下实习；注意维护人际关系，在 GitHub、牛客上多了解他人的实习经历 |
| 3 | 无法应对突发情况，比如申请港科，托福还没着落 | 提前准备好各种材料，尽早决定是否考雅思/托福、是否参加数竞、是否参加大英赛 |
| 4 | 课内成绩可能无法达到目标院校的门槛 | 在保证科研和其他学习任务进度的同时，尽可能提高课内成绩，同时把握好德育分 |
| 5 | 科研成果挂零 | 8 月整理思路、重新确定方向，全面推进科研进度 |
关键节点（时间线）
| 时间 | 节点 | 状态 |
|---|---|---|
| 2026.08 | 整理思路，重新确定方向，全面启动科研 | ⬜ 待办 |
| 2026.09 | 学完基础知识 | ✅ 已于 2026-08-04 完成 |
| 2026.09—2027.05 | 每天刷算法题（备战蓝桥杯、校内程序设计大赛） | ⬜ 待办 |
| 2027.01 | 大三上学期末，开始校外实习 | ⬜ 待办 |
| 2027.07 | 夏令营 | ⬜ 待办 |
| 2027.09 | 预推免 / 九推 | ⬜ 待办 |
知识索引
- 资源与规划
- 复杂度与计算机基础
- 数组
- 链表
- 哈希表
- 字符串
- 栈与队列
- 二叉树
- 基础：二叉树理论基础
- 递归遍历：二叉树的递归遍历
- 迭代遍历：二叉树的迭代遍历
- 深度：二叉树的最大深度、二叉树的最小深度
- 节点统计：完全二叉树的节点个数
- 平衡判断：平衡二叉树
- 路径与回溯：二叉树的所有路径
- 叶子节点：左叶子之和
- 层序定位：找树左下角的值
- 路径判断：路径总和
- 树的构造：从中序与后序遍历序列构造二叉树
- 递归构造：最大二叉树、合并二叉树
- 搜索：二叉搜索树中的搜索
- 合法性：验证二叉搜索树
- 相邻差值：二叉搜索树的最小绝对差
- 频率统计：二叉搜索树中的众数
- 最近公共祖先：二叉树、二叉搜索树
- 插入：二叉搜索树中的插入操作
- 删除与修剪：删除二叉搜索树中的节点、修剪二叉搜索树
- 平衡构造：将有序数组转换为二叉搜索树
- 累加树：把二叉搜索树转换为累加树
- 总结：二叉树总结
- 回溯算法
- Git
- 贪心算法
- 基础：贪心算法理论基础
- 资源分配：分发饼干
- 序列：摆动序列
- 股票：买卖股票的最佳时机 II
- 跳跃：跳跃游戏、跳跃游戏 II
- 数组变换：K 次取反后最大化的数组和
- 环形路线：加油站
- 双向约束：分发糖果
- 找零：柠檬水找零
- 多维排序：根据身高重建队列
- 区间覆盖：用最少数量的箭引爆气球
- 区间调度：无重叠区间
- 区间划分：划分字母区间
- 区间合并：合并区间
学习历程（持续更新）
2026-07-31（周五）
- 搜集算法学习与刷题网站：代码随想录、LeetCode 热题 100
- 信息与经验渠道：牛客（实习、面经、保研经验等）
2026-08-01（周六）
时间复杂度
- 理解大 O 表示法
- 了解不同数据规模对算法复杂度的要求
- 掌握复杂表达式的化简方法
- 理解
O(log n)中对数底数的影响 - 练习分析时间复杂度：从 个字符串中找出相同的两个字符串（假设仅有两个字符串相同）
程序为什么会超时
- 从硬件配置出发，大致了解 CPU 的执行速度
- 万赫兹
- 任何开发计算机程序的软件工程师都应该能够估计，这个程序的运行时间是一秒钟还是一年。
2026-08-04（周二）
空间复杂度
- 空间复杂度分析
- 递归算法的时间与空间复杂度分析：
- 斐波那契数列：对比
fibonacci(i - 1) + fibonacci(i - 2)与fibonacci(second, first + second, n - 1)两种递归写法 - 二分法（递归实现）的性能分析
- 递归算法的空间复杂度 ≈ 单层调用所需空间 × 最大递归深度
- 递归算法的时间复杂度 ≈ 递归调用总次数 × 单次调用的非递归工作量
- 斐波那契数列：对比
代码的内存消耗
- 固定部分：代码区、数据区
- 可变部分：栈区（自动分配与回收）、堆区（可通过
new动态分配，使用完成后应正确释放） - 内存泄漏：动态分配的内存在不再使用后未被释放
- 指针大小与寻址范围：
- 典型 32 位平台：指针大小为 4 Byte，理论寻址空间为 Byte，即 4 GB
- 典型 64 位平台：指针大小为 8 Byte，理论寻址空间为 Byte，实际可用范围受硬件和操作系统限制
- 内存对齐：
- 平台原因：并非所有硬件平台都能访问任意内存地址上的任意数据。某些平台只能在特定地址处读取特定类型的数据，否则会抛出硬件异常。为了让同一程序能够在多个平台上运行，需要进行内存对齐。
- 硬件原因：经过内存对齐后，CPU 访问内存的速度会显著提升。
- 阶段进度：基础知识学习至此结束。
2026-08-08（周六）
最近总是偷懒 😠，要克服这种心理。
数组（一）
一、数组理论
- 数组是存放在连续内存空间上的相同类型数据的集合。
- C++ 中的二维数组在地址空间上是连续的。
cpp
int array[2][3] = {
{0, 1, 2},
{3, 4, 5}
};int array[2][3] = {
{0, 1, 2},
{3, 4, 5}
};数组地址：
text
0x7ffee4065820 0x7ffee4065824 0x7ffee4065828
0x7ffee406582c 0x7ffee4065830 0x7ffee40658340x7ffee4065820 0x7ffee4065824 0x7ffee4065828
0x7ffee406582c 0x7ffee4065830 0x7ffee4065834二、二分查找
区间通常有两种定义：左闭右闭 [left, right]，或左闭右开 [left, right)。
- 版本一：左闭右闭
[left, right]
cpp
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
// target 位于左闭右闭区间 [left, right]
int right = nums.size() - 1;
// 当 left == right 时，[left, right] 仍然有效，因此使用 <=
while (left <= right) {
// 防止溢出，等同于 (left + right) / 2
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
// target 位于左区间 [left, middle - 1]
right = middle - 1;
} else if (nums[middle] < target) {
// target 位于右区间 [middle + 1, right]
left = middle + 1;
} else {
// 找到目标值，返回下标
return middle;
}
}
// 未找到目标值
return -1;
}
};class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
// target 位于左闭右闭区间 [left, right]
int right = nums.size() - 1;
// 当 left == right 时，[left, right] 仍然有效，因此使用 <=
while (left <= right) {
// 防止溢出，等同于 (left + right) / 2
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
// target 位于左区间 [left, middle - 1]
right = middle - 1;
} else if (nums[middle] < target) {
// target 位于右区间 [middle + 1, right]
left = middle + 1;
} else {
// 找到目标值，返回下标
return middle;
}
}
// 未找到目标值
return -1;
}
};- 版本二：左闭右开
[left, right)
cpp
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
// target 位于左闭右开区间 [left, right)
int right = nums.size();
// 当 left == right 时，[left, right) 无效，因此使用 <
while (left < right) {
int middle = left + ((right - left) >> 1);
if (nums[middle] > target) {
// target 位于左区间 [left, middle)
right = middle;
} else if (nums[middle] < target) {
// target 位于右区间 [middle + 1, right)
left = middle + 1;
} else {
// 找到目标值，返回下标
return middle;
}
}
// 未找到目标值
return -1;
}
};class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
// target 位于左闭右开区间 [left, right)
int right = nums.size();
// 当 left == right 时，[left, right) 无效，因此使用 <
while (left < right) {
int middle = left + ((right - left) >> 1);
if (nums[middle] > target) {
// target 位于左区间 [left, middle)
right = middle;
} else if (nums[middle] < target) {
// target 位于右区间 [middle + 1, right)
left = middle + 1;
} else {
// 找到目标值，返回下标
return middle;
}
}
// 未找到目标值
return -1;
}
};2026-08-10（周一）
数组（二）
三、移除元素
- 题目：27. 移除元素
- 暴力解法：使用两层
for循环。第一层遍历数组元素；发现需要移除的元素后，第二层将后续元素整体向前移动一位。- 时间复杂度：
- 空间复杂度：
- 双指针法（快慢指针法）：通过快、慢指针，在一层
for循环中完成两层循环的工作。- 快指针：寻找新数组的元素，即不等于目标值的元素
- 慢指针：指向新数组中待更新的下标
- 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (nums[fastIndex] != val) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (nums[fastIndex] != val) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};四、有序数组的平方
- 题目：977. 有序数组的平方
- 暴力排序：将每个数平方后排序，时间复杂度为 。
- 双指针法：原数组有序，平方后的最大值只可能出现在数组两端。新建与原数组等长的
result，令k指向其末尾：- 若
A[i] * A[i] < A[j] * A[j]，则执行result[k--] = A[j] * A[j] - 否则，执行
result[k--] = A[i] * A[i] - 时间复杂度：
- 空间复杂度：
- 若
cpp
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
int k = A.size() - 1;
vector<int> result(A.size(), 0);
// 最后仍需处理 i == j 时的元素，因此使用 <=
for (int i = 0, j = A.size() - 1; i <= j;) {
if (A[i] * A[i] < A[j] * A[j]) {
result[k--] = A[j] * A[j];
j--;
} else {
result[k--] = A[i] * A[i];
i++;
}
}
return result;
}
};class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
int k = A.size() - 1;
vector<int> result(A.size(), 0);
// 最后仍需处理 i == j 时的元素，因此使用 <=
for (int i = 0, j = A.size() - 1; i <= j;) {
if (A[i] * A[i] < A[j] * A[j]) {
result[k--] = A[j] * A[j];
j--;
} else {
result[k--] = A[i] * A[i];
i++;
}
}
return result;
}
};五、长度最小的子数组
- 题目：209. 长度最小的子数组
- 暴力解法：使用两层
for循环，不断寻找符合条件的子数组，时间复杂度为 。 - 滑动窗口：不断调整子数组的起始位置和终止位置，从而得到满足条件的最短子数组。
- 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0; // 滑动窗口内元素之和
int i = 0; // 滑动窗口起始位置
int subLength = 0; // 滑动窗口长度
for (int j = 0; j < nums.size(); j++) {
sum += nums[j];
// 使用 while 持续更新起始位置，并判断子数组是否符合条件
while (sum >= s) {
subLength = j - i + 1;
result = result < subLength ? result : subLength;
// 不断变更 i，缩小滑动窗口
sum -= nums[i++];
}
}
// result 未被更新，说明没有符合条件的子数组
return result == INT32_MAX ? 0 : result;
}
};class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0; // 滑动窗口内元素之和
int i = 0; // 滑动窗口起始位置
int subLength = 0; // 滑动窗口长度
for (int j = 0; j < nums.size(); j++) {
sum += nums[j];
// 使用 while 持续更新起始位置，并判断子数组是否符合条件
while (sum >= s) {
subLength = j - i + 1;
result = result < subLength ? result : subLength;
// 不断变更 i，缩小滑动窗口
sum -= nums[i++];
}
}
// result 未被更新，说明没有符合条件的子数组
return result == INT32_MAX ? 0 : result;
}
};六、螺旋矩阵 II
- 题目：59. 螺旋矩阵 II
- 核心原则：坚持循环不变量，四条边均采用左闭右开的处理方式。
cpp
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
int startx = 0, starty = 0; // 每一圈的起始位置
int loop = n / 2; // 需要循环的圈数
int mid = n / 2; // 矩阵中心位置
int count = 1; // 当前待填入的数值
int offset = 1; // 控制每条边遍历的长度
int i, j;
while (loop--) {
i = startx;
j = starty;
// 上边：从左到右（左闭右开）
for (; j < n - offset; j++) {
res[i][j] = count++;
}
// 右边：从上到下（左闭右开）
for (; i < n - offset; i++) {
res[i][j] = count++;
}
// 下边：从右到左（左闭右开）
for (; j > starty; j--) {
res[i][j] = count++;
}
// 左边：从下到上（左闭右开）
for (; i > startx; i--) {
res[i][j] = count++;
}
startx++;
starty++;
offset++;
}
// n 为奇数时，单独为矩阵中心赋值
if (n % 2) {
res[mid][mid] = count;
}
return res;
}
};class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
int startx = 0, starty = 0; // 每一圈的起始位置
int loop = n / 2; // 需要循环的圈数
int mid = n / 2; // 矩阵中心位置
int count = 1; // 当前待填入的数值
int offset = 1; // 控制每条边遍历的长度
int i, j;
while (loop--) {
i = startx;
j = starty;
// 上边：从左到右（左闭右开）
for (; j < n - offset; j++) {
res[i][j] = count++;
}
// 右边：从上到下（左闭右开）
for (; i < n - offset; i++) {
res[i][j] = count++;
}
// 下边：从右到左（左闭右开）
for (; j > starty; j--) {
res[i][j] = count++;
}
// 左边：从下到上（左闭右开）
for (; i > startx; i--) {
res[i][j] = count++;
}
startx++;
starty++;
offset++;
}
// n 为奇数时，单独为矩阵中心赋值
if (n % 2) {
res[mid][mid] = count;
}
return res;
}
};2026-08-11（周二）
数组（三）
七、区间和
- 题目：58. 区间和（第九期模拟笔试）
- 暴力解法：对于每个查询区间，重新遍历并累加区间内的所有元素。
- 前缀和：适用于需要频繁计算区间和的问题。
p[i]表示数组vec中下标0到i的元素之和- 当
a == 0时，区间和为p[b] - 当
a > 0时，区间和为p[b] - p[a - 1] - 预处理时间复杂度：
- 单次查询时间复杂度：
- 空间复杂度：
cpp
#include <cstdio>
#include <vector>
using namespace std;
int main() {
int n, a, b;
scanf("%d", &n);
vector<int> vec(n);
vector<int> prefix(n);
int prefixSum = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &vec[i]);
prefixSum += vec[i];
prefix[i] = prefixSum;
}
while (scanf("%d%d", &a, &b) == 2) {
int sum = (a == 0) ? prefix[b] : prefix[b] - prefix[a - 1];
printf("%d\n", sum);
}
return 0;
}#include <cstdio>
#include <vector>
using namespace std;
int main() {
int n, a, b;
scanf("%d", &n);
vector<int> vec(n);
vector<int> prefix(n);
int prefixSum = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &vec[i]);
prefixSum += vec[i];
prefix[i] = prefixSum;
}
while (scanf("%d%d", &a, &b) == 2) {
int sum = (a == 0) ? prefix[b] : prefix[b] - prefix[a - 1];
printf("%d\n", sum);
}
return 0;
}面对大量数据的输入与输出时，使用
scanf和printf通常比默认的cin和cout耗时更少。
八、开发商购买土地
- 题目：44. 开发商购买土地（第五期模拟笔试）
- 暴力解法：使用一层
for循环枚举分割线，再用两层for循环分别累加分割线两侧的土地价值。 - 前缀和思路：
- 统计矩阵的总价值。
- 分别计算每行与每列的价值之和。
- 累加分割线一侧的价值，并用
abs(sum - 2 * cut)计算两侧价值之差。 - 分别枚举横向和纵向分割线，取最小差值。
- 时间复杂度：
- 空间复杂度：
cpp
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int sum = 0;
vector<vector<int>> vec(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> vec[i][j];
sum += vec[i][j];
}
}
// 统计每行的价值之和
vector<int> horizontal(n, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
horizontal[i] += vec[i][j];
}
}
// 统计每列的价值之和
vector<int> vertical(m, 0);
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
vertical[j] += vec[i][j];
}
}
int result = INT_MAX;
int horizontalCut = 0;
// 分割线必须位于两行之间，因此不枚举最后一行之后的位置
for (int i = 0; i < n - 1; i++) {
horizontalCut += horizontal[i];
result = min(result, abs(sum - 2 * horizontalCut));
}
int verticalCut = 0;
// 分割线必须位于两列之间
for (int j = 0; j < m - 1; j++) {
verticalCut += vertical[j];
result = min(result, abs(sum - 2 * verticalCut));
}
cout << result << endl;
return 0;
}#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int sum = 0;
vector<vector<int>> vec(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> vec[i][j];
sum += vec[i][j];
}
}
// 统计每行的价值之和
vector<int> horizontal(n, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
horizontal[i] += vec[i][j];
}
}
// 统计每列的价值之和
vector<int> vertical(m, 0);
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
vertical[j] += vec[i][j];
}
}
int result = INT_MAX;
int horizontalCut = 0;
// 分割线必须位于两行之间，因此不枚举最后一行之后的位置
for (int i = 0; i < n - 1; i++) {
horizontalCut += horizontal[i];
result = min(result, abs(sum - 2 * horizontalCut));
}
int verticalCut = 0;
// 分割线必须位于两列之间
for (int j = 0; j < m - 1; j++) {
verticalCut += vertical[j];
result = min(result, abs(sum - 2 * verticalCut));
}
cout << result << endl;
return 0;
}九、数组总结
核心特性
- 数组是存放在连续内存空间上的相同类型数据的集合。
- 数组下标从 0 开始。
- 数组元素的内存地址连续，因此删除或添加元素时，通常需要移动其他元素。
经典方法
- 二分查找：坚持循环不变量，统一维护区间定义。
- 双指针：通过快、慢指针在一层
for循环中完成两层循环的工作。 - 滑动窗口：根据当前子数组的状态不断调整起始位置，将部分 的暴力解法优化至 。
- 模拟：坚持循环不变量，统一每一轮的处理规则。
- 前缀和：预处理累计和，使用
prefix[b] - prefix[a - 1]快速计算区间和。
知识图谱
2026-08-12（周三）
链表（一）
一、链表理论基础
定义
链表是一种通过指针串联起来的线性结构。每个节点由两部分组成：
- 数据域：存储节点中的数据
- 指针域：存储指向下一个节点的指针；最后一个节点的指针域指向
nullptr
常见类型
- 单链表：每个节点的指针域只能指向下一个节点
- 双链表：每个节点有两个指针域，分别指向前一个节点和后一个节点
- 循环链表：链表首尾相连，尾节点指向头节点
存储方式
数组元素在内存中连续分布，而链表节点通常不连续分布。链表通过节点指针，将分散在内存中的节点连接起来。
cpp
// 单链表节点
struct ListNode {
int val; // 节点中存储的元素
ListNode* next; // 指向下一个节点
ListNode(int x) : val(x), next(nullptr) {}
};// 单链表节点
struct ListNode {
int val; // 节点中存储的元素
ListNode* next; // 指向下一个节点
ListNode(int x) : val(x), next(nullptr) {}
};如果没有定义接受参数的构造函数，就不能使用
ListNode node(x)这种方式直接为节点值初始化。
基本操作
- 删除节点 D：将节点 C 的
next指向节点 E，再手动释放节点 D - 在 C 与 D 之间添加节点 F：先将 F 的
next指向 D，再将 C 的next指向 F
数组与链表的性能对比
| 数据结构 | 插入 / 删除 | 按下标查询 | 长度与适用场景 |
|---|---|---|---|
| 数组 | 长度通常预先确定，适合频繁查询 | ||
| 链表 | 已知目标位置时为 | 长度可动态变化，适合频繁增删、较少查询 |
二、移除链表元素
- 题目：203. 移除链表元素
- 直接操作原链表：头节点没有前驱节点，因此需要分别处理头节点和非头节点。
- 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 连续删除值等于 val 的头节点，注意这里使用 while 而非 if
while (head != nullptr && head->val == val) {
ListNode* tmp = head;
head = head->next;
delete tmp;
}
// 删除非头节点
ListNode* cur = head;
while (cur != nullptr && cur->next != nullptr) {
if (cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
return head;
}
};class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 连续删除值等于 val 的头节点，注意这里使用 while 而非 if
while (head != nullptr && head->val == val) {
ListNode* tmp = head;
head = head->next;
delete tmp;
}
// 删除非头节点
ListNode* cur = head;
while (cur != nullptr && cur->next != nullptr) {
if (cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
return head;
}
};虚拟头节点
设置虚拟头节点后，原头节点和其他节点可以使用同一套删除逻辑，避免单独处理头节点。
cpp
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;三、设计链表
- 题目：707. 设计链表
- 核心设计：使用虚拟头节点统一链表的插入与删除操作，并用
_size记录有效节点数量。
cpp
class MyLinkedList {
public:
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val) : val(val), next(nullptr) {}
};
MyLinkedList() {
_dummyHead = new LinkedNode(0);
_size = 0;
}
~MyLinkedList() {
while (_dummyHead != nullptr) {
LinkedNode* tmp = _dummyHead;
_dummyHead = _dummyHead->next;
delete tmp;
}
}
int get(int index) {
if (index < 0 || index >= _size) {
return -1;
}
LinkedNode* cur = _dummyHead->next;
while (index--) {
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val);
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;
_size++;
}
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while (cur->next != nullptr) {
cur = cur->next;
}
cur->next = newNode;
_size++;
}
void addAtIndex(int index, int val) {
if (index > _size) {
return;
}
if (index < 0) {
index = 0;
}
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while (index--) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
_size++;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= _size) {
return;
}
LinkedNode* cur = _dummyHead;
while (index--) {
cur = cur->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
_size--;
}
private:
LinkedNode* _dummyHead;
int _size;
};class MyLinkedList {
public:
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val) : val(val), next(nullptr) {}
};
MyLinkedList() {
_dummyHead = new LinkedNode(0);
_size = 0;
}
~MyLinkedList() {
while (_dummyHead != nullptr) {
LinkedNode* tmp = _dummyHead;
_dummyHead = _dummyHead->next;
delete tmp;
}
}
int get(int index) {
if (index < 0 || index >= _size) {
return -1;
}
LinkedNode* cur = _dummyHead->next;
while (index--) {
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val);
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;
_size++;
}
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while (cur->next != nullptr) {
cur = cur->next;
}
cur->next = newNode;
_size++;
}
void addAtIndex(int index, int val) {
if (index > _size) {
return;
}
if (index < 0) {
index = 0;
}
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while (index--) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
_size++;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= _size) {
return;
}
LinkedNode* cur = _dummyHead;
while (index--) {
cur = cur->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
_size--;
}
private:
LinkedNode* _dummyHead;
int _size;
};2026-08-13（周四）
链表（二）
四、反转链表
- 题目：206. 反转链表
- 双指针法：使用
cur遍历原链表，使用pre指向已完成反转的部分。改变cur->next前，必须先用temp保存下一个节点。 - 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while (cur != nullptr) {
// 保存下一个节点，避免改变 cur->next 后丢失后续链表
ListNode* temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
};class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while (cur != nullptr) {
// 保存下一个节点，避免改变 cur->next 后丢失后续链表
ListNode* temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
};五、删除链表的倒数第 N 个节点
- 题目：19. 删除链表的倒数第 N 个节点
- 快慢指针法：
- 创建虚拟头节点，使删除头节点与删除其他节点使用同一套逻辑。
fast先从虚拟头节点出发移动 步，使fast与slow之间保持 步的间隔。- 同时移动两个指针，直到
fast指向nullptr；此时slow恰好指向待删除节点的前一个节点。 - 调整指针并释放待删除节点。
- 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* fast = dummyHead;
ListNode* slow = dummyHead;
// 让 slow 最终停在待删除节点的前一个节点
for (int i = 0; i <= n; i++) {
fast = fast->next;
}
while (fast != nullptr) {
fast = fast->next;
slow = slow->next;
}
ListNode* tmp = slow->next;
slow->next = tmp->next;
delete tmp;
ListNode* newHead = dummyHead->next;
delete dummyHead;
return newHead;
}
};class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* fast = dummyHead;
ListNode* slow = dummyHead;
// 让 slow 最终停在待删除节点的前一个节点
for (int i = 0; i <= n; i++) {
fast = fast->next;
}
while (fast != nullptr) {
fast = fast->next;
slow = slow->next;
}
ListNode* tmp = slow->next;
slow->next = tmp->next;
delete tmp;
ListNode* newHead = dummyHead->next;
delete dummyHead;
return newHead;
}
};七、链表相交
- 题目：面试题 02.07. 链表相交
- 长度对齐法：
- 分别计算链表 A 与链表 B 的长度。
- 让较长链表的指针先移动长度差，使两个指针到链表末尾的距离相同。
- 同时向后移动两个指针；首次指向同一节点时，该节点就是相交节点。
- 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0;
int lenB = 0;
while (curA != nullptr) {
lenA++;
curA = curA->next;
}
while (curB != nullptr) {
lenB++;
curB = curB->next;
}
curA = headA;
curB = headB;
// 保证 curA 指向较长链表，lenA 为较大长度
if (lenB > lenA) {
swap(lenA, lenB);
swap(curA, curB);
}
// 将两个链表按末尾对齐
int gap = lenA - lenB;
while (gap--) {
curA = curA->next;
}
while (curA != nullptr) {
if (curA == curB) {
return curA;
}
curA = curA->next;
curB = curB->next;
}
return nullptr;
}
};class Solution {
public:
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0;
int lenB = 0;
while (curA != nullptr) {
lenA++;
curA = curA->next;
}
while (curB != nullptr) {
lenB++;
curB = curB->next;
}
curA = headA;
curB = headB;
// 保证 curA 指向较长链表，lenA 为较大长度
if (lenB > lenA) {
swap(lenA, lenB);
swap(curA, curB);
}
// 将两个链表按末尾对齐
int gap = lenA - lenB;
while (gap--) {
curA = curA->next;
}
while (curA != nullptr) {
if (curA == curB) {
return curA;
}
curA = curA->next;
curB = curB->next;
}
return nullptr;
}
};2026-08-14（周五）
链表（三）
八、环形链表 II
- 题目：142. 环形链表 II
- 需要解决两个问题：
- 判断链表中是否存在环。
- 如果存在环，找到环的入口节点。
判断是否存在环
使用快慢指针：fast 每次移动两个节点，slow 每次移动一个节点。如果两个指针在途中相遇，说明链表中存在环；如果 fast 或 fast->next 指向 nullptr，说明链表中不存在环。
寻找环的入口
假设：
- 从头节点到环入口的距离为
- 从环入口到快慢指针相遇点的距离为
- 从相遇点回到环入口的距离为
fast在环内绕了 圈
相遇时，slow 与 fast 经过的距离分别为：
由于 fast 的速度是 slow 的两倍：
整理可得：
因此，分别从头节点与快慢指针相遇点出发两个指针，并让它们每次各移动一个节点；二者再次相遇的位置就是环的入口。
- 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
// 快慢指针相遇，说明链表中存在环
if (slow == fast) {
ListNode* index1 = fast;
ListNode* index2 = head;
// 从相遇点和头节点同时出发，再次相遇处就是环入口
while (index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index2;
}
}
return nullptr;
}
};class Solution {
public:
ListNode* detectCycle(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
// 快慢指针相遇，说明链表中存在环
if (slow == fast) {
ListNode* index1 = fast;
ListNode* index2 = head;
// 从相遇点和头节点同时出发，再次相遇处就是环入口
while (index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index2;
}
}
return nullptr;
}
};九、链表总结
理论基础
- 常见类型：单链表、双链表、循环链表
- 存储方式：节点通常分散在内存中，通过指针连接
- 基本操作：链表的增加、删除、修改与查询
- 性能分析：理解数组和链表在不同使用场景中的优劣
经典方法与题目
- 虚拟头节点：统一头节点与其他节点的处理逻辑，避免单独分类讨论
- 链表基本操作：设计链表
- 迭代双指针：反转链表
- 快慢指针与虚拟头节点：删除链表的倒数第 N 个节点
- 长度对齐：链表相交
- 快慢指针：判断链表是否有环并寻找环入口
2026-08-15（周六）
哈希表（一）
哈希表用于快速判断元素是否出现、统计元素频率以及建立键值映射，是数组与字符串题目中的高频工具。
一、哈希表理论基础
基本概念
- 哈希表：根据关键码的值直接访问数据的数据结构。
- 哈希函数：通过
hashCode将键转换为数值，再映射到哈希表的索引位置。 - 哈希碰撞：不同的键经过哈希函数计算后，被映射到同一个索引位置。
哈希碰撞的解决方法
- 拉链法：将发生冲突的元素存储在同一个链表中。需要选择合适的表大小，避免空槽过多浪费内存，也避免链表过长降低查询效率。
- 线性探测法：依靠哈希表中的空槽解决冲突。发生碰撞时，按顺序继续寻找下一个空槽；因此需要保证
tableSize > dataSize。
常用哈希结构
- 数组
set（集合）map（映射）
C++ 集合容器对比
| 容器 | 底层实现 | 是否有序 | 元素能否重复 | 元素能否直接修改 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
std::set | 红黑树 | 有序 | 否 | 否 | ||
std::multiset | 红黑树 | 有序 | 是 | 否 | ||
std::unordered_set | 哈希表 | 无序 | 否 | 否 | 平均 | 平均 |
C++ 映射容器对比
| 容器 | 底层实现 | 键是否有序 | 键能否重复 | 键能否修改 | 映射值能否修改 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|---|
std::map | 红黑树 | 有序 | 否 | 否 | 是 | ||
std::multimap | 红黑树 | 有序 | 是 | 否 | 是 | ||
std::unordered_map | 哈希表 | 无序 | 否 | 否 | 是 | 平均 | 平均 |
红黑树是一种平衡二叉搜索树。为了维持内部顺序，
set中的元素以及map中的键不能直接修改；需要先删除，再插入新值。
二、有效的字母异位词
- 题目：242. 有效的字母异位词
- 暴力解法：使用两层
for循环逐一匹配字符，时间复杂度为 。 - 数组哈希：题目限定字符为小写英文字母，因此可以使用长度为 26 的
record数组记录各字母出现的次数。- 遍历字符串
s，对record[s[i] - 'a']执行加一操作。 - 遍历字符串
t，对record[t[i] - 'a']执行减一操作。 - 如果最终所有元素均为 0，则两个字符串互为字母异位词。
- 遍历字符串
- 时间复杂度：
- 空间复杂度：，因为数组长度固定为 26
cpp
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
for (char ch : s) {
// 只需计算字符相对 'a' 的偏移量
record[ch - 'a']++;
}
for (char ch : t) {
record[ch - 'a']--;
}
for (int count : record) {
if (count != 0) {
return false;
}
}
return true;
}
};class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
for (char ch : s) {
// 只需计算字符相对 'a' 的偏移量
record[ch - 'a']++;
}
for (char ch : t) {
record[ch - 'a']--;
}
for (int count : record) {
if (count != 0) {
return false;
}
}
return true;
}
};三、两个数组的交集
- 题目：349. 两个数组的交集
- 选择哈希结构：当数值范围较小时，可以使用数组作为哈希表；当数值范围不固定时，使用
unordered_set更合适。 - 解题思路：
- 使用
numsSet保存nums1中出现过的元素。 - 遍历
nums2，将同时出现在numsSet中的元素加入resultSet。 - 使用集合自动去重，最后转换为
vector返回。
- 使用
- 平均时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> numsSet(nums1.begin(), nums1.end());
unordered_set<int> resultSet;
for (int num : nums2) {
if (numsSet.find(num) != numsSet.end()) {
resultSet.insert(num);
}
}
return vector<int>(resultSet.begin(), resultSet.end());
}
};class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> numsSet(nums1.begin(), nums1.end());
unordered_set<int> resultSet;
for (int num : nums2) {
if (numsSet.find(num) != numsSet.end()) {
resultSet.insert(num);
}
}
return vector<int>(resultSet.begin(), resultSet.end());
}
};unordered_set 可以通过迭代器区间直接初始化：
cpp
unordered_set<int> numsSet(nums.begin(), nums.end());unordered_set<int> numsSet(nums.begin(), nums.end());2026-08-17（周一）
哈希表（二）
四、快乐数
- 题目：202. 快乐数
- 核心问题：计算各位数字的平方和时，结果可能进入循环。
- 集合判重：使用
unordered_set保存已经出现过的平方和。- 如果平方和变为 1，则原数是快乐数。
- 如果某个平方和再次出现，则计算进入无限循环，原数不是快乐数。
- 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
// 计算各位数字的平方和
int getSum(int n) {
int sum = 0;
while (n != 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> seen;
while (true) {
int sum = getSum(n);
if (sum == 1) {
return true;
}
// 平方和再次出现，说明已经进入循环
if (seen.find(sum) != seen.end()) {
return false;
}
seen.insert(sum);
n = sum;
}
}
};class Solution {
public:
// 计算各位数字的平方和
int getSum(int n) {
int sum = 0;
while (n != 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> seen;
while (true) {
int sum = getSum(n);
if (sum == 1) {
return true;
}
// 平方和再次出现，说明已经进入循环
if (seen.find(sum) != seen.end()) {
return false;
}
seen.insert(sum);
n = sum;
}
}
};五、两数之和
- 题目：1. 两数之和
- 为什么不使用数组：数值范围可能很大而元素数量较少，直接建立数组会浪费内存。
- 为什么不使用
set：不仅需要判断目标元素是否存在，还需要保存该元素对应的下标。 - 映射哈希：使用
unordered_map存储“元素值 → 下标”。遍历当前元素nums[i]时，在哈希表中查找补数target - nums[i]。 - 平均时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> numToIndex;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
auto iter = numToIndex.find(complement);
if (iter != numToIndex.end()) {
return {iter->second, i};
}
// 未找到匹配项，记录当前元素及其下标
numToIndex.emplace(nums[i], i);
}
return {};
}
};class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> numToIndex;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
auto iter = numToIndex.find(complement);
if (iter != numToIndex.end()) {
return {iter->second, i};
}
// 未找到匹配项，记录当前元素及其下标
numToIndex.emplace(nums[i], i);
}
return {};
}
};六、四数相加 II
- 题目：454. 四数相加 II
- 分组哈希：将四个数组分为两组，把四层枚举降为两次两层枚举。
- 解题步骤：
- 使用
unordered_map统计所有a + b出现的次数，其中键为两数之和，值为出现次数。 - 遍历数组 C 与 D，计算
c + d。 - 如果
-(c + d)存在于哈希表中，将其出现次数累加到结果。
- 使用
- 平均时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
int fourSumCount(
vector<int>& A,
vector<int>& B,
vector<int>& C,
vector<int>& D
) {
// key：a + b；value：该和出现的次数
unordered_map<int, int> sumCount;
for (int a : A) {
for (int b : B) {
sumCount[a + b]++;
}
}
int count = 0;
for (int c : C) {
for (int d : D) {
auto iter = sumCount.find(-(c + d));
if (iter != sumCount.end()) {
count += iter->second;
}
}
}
return count;
}
};class Solution {
public:
int fourSumCount(
vector<int>& A,
vector<int>& B,
vector<int>& C,
vector<int>& D
) {
// key：a + b；value：该和出现的次数
unordered_map<int, int> sumCount;
for (int a : A) {
for (int b : B) {
sumCount[a + b]++;
}
}
int count = 0;
for (int c : C) {
for (int d : D) {
auto iter = sumCount.find(-(c + d));
if (iter != sumCount.end()) {
count += iter->second;
}
}
}
return count;
}
};2026-08-18（周二）
哈希表（三）
七、赎金信
- 题目：383. 赎金信
- 暴力解法：使用两层
for循环逐一匹配字符，时间复杂度为 。 - 数组哈希：使用长度为 26 的数组记录
magazine中每个字母的出现次数，再遍历ransomNote逐个消耗。- 如果
ransomNote比magazine更长，可以直接返回false。 - 如果某个字符的剩余次数小于 0，说明
magazine无法提供足够的字符。
- 如果
- 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
if (ransomNote.size() > magazine.size()) {
return false;
}
int record[26] = {0};
for (char ch : magazine) {
record[ch - 'a']++;
}
for (char ch : ransomNote) {
record[ch - 'a']--;
if (record[ch - 'a'] < 0) {
return false;
}
}
return true;
}
};class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
if (ransomNote.size() > magazine.size()) {
return false;
}
int record[26] = {0};
for (char ch : magazine) {
record[ch - 'a']++;
}
for (char ch : ransomNote) {
record[ch - 'a']--;
if (record[ch - 'a'] < 0) {
return false;
}
}
return true;
}
};八、三数之和
- 题目：15. 三数之和
- 参考：三数之和（代码随想录）
- 排序与双指针：
- 将数组排序。
- 使用一层
for循环固定a = nums[i]。 - 令
left = i + 1、right = nums.size() - 1，分别表示b与c。 - 当三数之和大于 0 时左移
right；小于 0 时右移left；等于 0 时记录答案并跳过重复元素。
- 去重原则：
- 对
a去重时，应与前一个元素比较；如果与后一个元素比较，会漏掉[-1, -1, 2]。 - 对
b与c去重应在找到有效三元组后进行，否则可能漏掉[0, 0, 0]。
- 对
- 时间复杂度：
- 额外空间复杂度：，不计返回结果，主要来自排序
cpp
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
// 最小元素已经大于 0，不可能再得到和为 0 的三元组
if (nums[i] > 0) {
break;
}
// 对固定元素 a 去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
} else {
result.push_back({nums[i], nums[left], nums[right]});
// 对 b 与 c 去重
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
}
}
}
return result;
}
};class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
// 最小元素已经大于 0，不可能再得到和为 0 的三元组
if (nums[i] > 0) {
break;
}
// 对固定元素 a 去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
} else {
result.push_back({nums[i], nums[left], nums[right]});
// 对 b 与 c 去重
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
}
}
}
return result;
}
};这道题的代码较长，重点记住“排序—固定一个数—双指针收缩—命中后去重”这一固定框架。
九、四数之和
- 题目：18. 四数之和
- 核心思路：三数之和使用一层循环固定一个数；四数之和使用两层循环固定两个数，再在剩余区间内使用双指针。
- 固定
nums[k]与nums[i] - 令
left = i + 1、right = nums.size() - 1 - 寻找满足
nums[k] + nums[i] + nums[left] + nums[right] == target的四元组
- 固定
- 通用扩展：五数之和、六数之和等问题，也可以继续增加固定元素的循环层数。
- 注意溢出：计算四数之和时使用
long long。 - 时间复杂度：
- 额外空间复杂度：，不计返回结果，主要来自排序
cpp
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); k++) {
// 一级剪枝
if (nums[k] > target && nums[k] >= 0) {
break;
}
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.size(); i++) {
// 二级剪枝
long long fixedSum = static_cast<long long>(nums[k]) + nums[i];
if (fixedSum > target && fixedSum >= 0) {
break;
}
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
long long sum = static_cast<long long>(nums[k])
+ nums[i]
+ nums[left]
+ nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
result.push_back({
nums[k], nums[i], nums[left], nums[right]
});
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
}
}
}
}
return result;
}
};class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); k++) {
// 一级剪枝
if (nums[k] > target && nums[k] >= 0) {
break;
}
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.size(); i++) {
// 二级剪枝
long long fixedSum = static_cast<long long>(nums[k]) + nums[i];
if (fixedSum > target && fixedSum >= 0) {
break;
}
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
long long sum = static_cast<long long>(nums[k])
+ nums[i]
+ nums[left]
+ nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
result.push_back({
nums[k], nums[i], nums[left], nums[right]
});
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
}
}
}
}
return result;
}
};十、哈希表总结
核心作用
- 快速判断元素是否出现
- 统计元素出现频率
- 建立元素与下标、计数等信息之间的映射
常用结构选择
- 数组：数值或字符范围较小且固定，例如字母异位词、赎金信
set/unordered_set：只需要判断元素是否存在或进行去重，例如两个数组的交集、快乐数map/unordered_map：需要保存<key, value>映射，例如元素到下标、两数之和到出现次数
相关解题模式
- 当哈希法的去重逻辑较复杂时，可以考虑“排序 + 双指针”，例如三数之和与四数之和。
2026-08-19（周三）
字符串（一）
一、反转字符串
- 题目：344. 反转字符串
- 双指针法：分别在字符串首尾设置
left和right，交换两个指针指向的字符，然后同时向中间移动，直到二者相遇。 - 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0;
int right = static_cast<int>(s.size()) - 1;
while (left < right) {
swap(s[left], s[right]);
left++;
right--;
}
}
};class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0;
int right = static_cast<int>(s.size()) - 1;
while (left < right) {
swap(s[left], s[right]);
left++;
right--;
}
}
};二、反转字符串 II
- 题目：541. 反转字符串 II
- 分段处理：每次令
i += 2 * k，处理当前 个字符中的前 个字符。- 剩余字符不少于 个：反转前 个字符。
- 剩余字符少于 个：反转全部剩余字符。
- 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
void reverseRange(string& s, int start, int end) {
while (start < end) {
swap(s[start], s[end]);
start++;
end--;
}
}
string reverseStr(string s, int k) {
int n = s.size();
for (int i = 0; i < n; i += 2 * k) {
// 取前 k 个字符；不足 k 个时，反转全部剩余字符
int end = min(i + k - 1, n - 1);
reverseRange(s, i, end);
}
return s;
}
};class Solution {
public:
void reverseRange(string& s, int start, int end) {
while (start < end) {
swap(s[start], s[end]);
start++;
end--;
}
}
string reverseStr(string s, int k) {
int n = s.size();
for (int i = 0; i < n; i += 2 * k) {
// 取前 k 个字符；不足 k 个时，反转全部剩余字符
int end = min(i + k - 1, n - 1);
reverseRange(s, i, end);
}
return s;
}
};三、替换数字
- 题目：54. 替换数字
- 核心思路：先统计数字字符的数量，将字符串扩充到替换后的长度，再使用双指针从后向前填充。
oldIndex指向原字符串末尾。newIndex指向扩容后字符串末尾。- 普通字符直接复制；数字字符倒序写入
"number"。
- 为什么从后向前填充：
- 可以直接在原字符串上操作，无需额外申请一个结果字符串。
- 避免从前向后插入字符时，反复移动后续所有元素。
- 时间复杂度：
- 额外空间复杂度：，不计字符串扩容后的必要空间
cpp
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
while (cin >> s) {
int digitCount = 0;
for (char ch : s) {
if (ch >= '0' && ch <= '9') {
digitCount++;
}
}
int oldIndex = static_cast<int>(s.size()) - 1;
// 一个数字替换为 6 个字符，字符串长度因此额外增加 5
s.resize(s.size() + digitCount * 5);
int newIndex = static_cast<int>(s.size()) - 1;
while (oldIndex >= 0) {
if (s[oldIndex] >= '0' && s[oldIndex] <= '9') {
s[newIndex--] = 'r';
s[newIndex--] = 'e';
s[newIndex--] = 'b';
s[newIndex--] = 'm';
s[newIndex--] = 'u';
s[newIndex--] = 'n';
} else {
s[newIndex--] = s[oldIndex];
}
oldIndex--;
}
cout << s << endl;
}
return 0;
}#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
while (cin >> s) {
int digitCount = 0;
for (char ch : s) {
if (ch >= '0' && ch <= '9') {
digitCount++;
}
}
int oldIndex = static_cast<int>(s.size()) - 1;
// 一个数字替换为 6 个字符，字符串长度因此额外增加 5
s.resize(s.size() + digitCount * 5);
int newIndex = static_cast<int>(s.size()) - 1;
while (oldIndex >= 0) {
if (s[oldIndex] >= '0' && s[oldIndex] <= '9') {
s[newIndex--] = 'r';
s[newIndex--] = 'e';
s[newIndex--] = 'b';
s[newIndex--] = 'm';
s[newIndex--] = 'u';
s[newIndex--] = 'n';
} else {
s[newIndex--] = s[oldIndex];
}
oldIndex--;
}
cout << s << endl;
}
return 0;
}2026-08-29（周六）
字符串（三）
六、实现 strStr
- 题目：28. 找出字符串中第一个匹配项的下标
- KMP 的核心作用：当字符失配时，利用已经匹配的前后缀信息移动模式串，避免文本串回退并从头匹配。
- 前缀表：对于模式串的每个位置
i，记录子串[0, i]中最长相等真前缀与真后缀的信息。 - 本实现的
next定义：next[i] = j，其中j是最长相等前后缀的最后一个下标。- 对应的最长相等前后缀长度为
j + 1。 - 当失配发生时，令
j = next[j]，继续尝试更短的相等前后缀。
- 时间复杂度：
- 空间复杂度：，其中 为模式串长度
cpp
class Solution {
public:
void getNext(vector<int>& next, const string& pattern) {
int j = -1;
next[0] = -1;
// i 从 1 开始，j 表示最长相等前后缀的最后一个下标
for (int i = 1; i < pattern.size(); i++) {
while (j >= 0 && pattern[i] != pattern[j + 1]) {
j = next[j];
}
if (pattern[i] == pattern[j + 1]) {
j++;
}
next[i] = j;
}
}
int strStr(string haystack, string needle) {
if (needle.empty()) {
return 0;
}
vector<int> next(needle.size());
getNext(next, needle);
int j = -1;
for (int i = 0; i < haystack.size(); i++) {
while (j >= 0 && haystack[i] != needle[j + 1]) {
j = next[j];
}
if (haystack[i] == needle[j + 1]) {
j++;
}
// 模式串全部匹配完成
if (j == static_cast<int>(needle.size()) - 1) {
return i - static_cast<int>(needle.size()) + 1;
}
}
return -1;
}
};class Solution {
public:
void getNext(vector<int>& next, const string& pattern) {
int j = -1;
next[0] = -1;
// i 从 1 开始，j 表示最长相等前后缀的最后一个下标
for (int i = 1; i < pattern.size(); i++) {
while (j >= 0 && pattern[i] != pattern[j + 1]) {
j = next[j];
}
if (pattern[i] == pattern[j + 1]) {
j++;
}
next[i] = j;
}
}
int strStr(string haystack, string needle) {
if (needle.empty()) {
return 0;
}
vector<int> next(needle.size());
getNext(next, needle);
int j = -1;
for (int i = 0; i < haystack.size(); i++) {
while (j >= 0 && haystack[i] != needle[j + 1]) {
j = next[j];
}
if (haystack[i] == needle[j + 1]) {
j++;
}
// 模式串全部匹配完成
if (j == static_cast<int>(needle.size()) - 1) {
return i - static_cast<int>(needle.size()) + 1;
}
}
return -1;
}
};核心记忆：文本串不回退；模式串根据前缀表回退到可复用的匹配位置。
七、重复的子字符串
- 题目：459. 重复的子字符串
- KMP 判断方法：
- 计算字符串末尾位置对应的最长相等前后缀长度
longestPrefixSuffix。 - 候选最小重复单元长度为
period = n - longestPrefixSuffix。 - 如果最长相等前后缀存在，且
n % period == 0，则字符串可由该重复单元构成。
- 计算字符串末尾位置对应的最长相等前后缀长度
- 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
void getNext(vector<int>& next, const string& s) {
int j = -1;
next[0] = -1;
for (int i = 1; i < s.size(); i++) {
while (j >= 0 && s[i] != s[j + 1]) {
j = next[j];
}
if (s[i] == s[j + 1]) {
j++;
}
next[i] = j;
}
}
bool repeatedSubstringPattern(string s) {
if (s.empty()) {
return false;
}
vector<int> next(s.size());
getNext(next, s);
int n = s.size();
int longestPrefixSuffix = next[n - 1] + 1;
int period = n - longestPrefixSuffix;
return longestPrefixSuffix > 0 && n % period == 0;
}
};class Solution {
public:
void getNext(vector<int>& next, const string& s) {
int j = -1;
next[0] = -1;
for (int i = 1; i < s.size(); i++) {
while (j >= 0 && s[i] != s[j + 1]) {
j = next[j];
}
if (s[i] == s[j + 1]) {
j++;
}
next[i] = j;
}
}
bool repeatedSubstringPattern(string s) {
if (s.empty()) {
return false;
}
vector<int> next(s.size());
getNext(next, s);
int n = s.size();
int longestPrefixSuffix = next[n - 1] + 1;
int period = n - longestPrefixSuffix;
return longestPrefixSuffix > 0 && n % period == 0;
}
};八、字符串总结
基本概念
- 字符串是由若干字符组成的有限序列，也可以理解为字符数组。
常见解题方法
- 双指针：从首尾向中间移动，完成字符串反转。
- 扩容与倒序填充：在原字符串中替换长度增加的内容，避免反复移动元素。
- 整体反转与局部反转：处理单词顺序反转、字符串旋转等问题。
- 快慢指针：移除多余空格并压缩字符串。
- KMP：利用最长相等前后缀信息，高效完成字符串匹配与周期判断。
2026-08-31（周一）
栈与队列（一）
一、栈与队列理论基础
基本特性
- 队列（Queue）：先进先出，简称 FIFO（First In, First Out）。
- 栈（Stack）：先进后出，简称 LIFO（Last In, First Out）。
容器适配器
std::stack 和 std::queue 本身不直接负责存储数据，而是调用底层容器完成操作，并向外提供统一且受限的接口。因此，它们在 STL 中被归类为 container adapter（容器适配器），而不是独立容器。
std::stack默认使用deque作为底层容器，也可以使用满足操作要求的vector或list。std::queue默认使用deque作为底层容器，也可以使用支持首尾操作的list。- 底层既可能采用连续存储结构，也可能采用链式存储结构，具体取决于选用的容器。
二、用栈实现队列
- 题目：232. 用栈实现队列
- 核心设计：使用两个栈模拟队列。
stackIn：负责接收新元素。stackOut：负责弹出队首元素。
- 数据转移规则：只有当
stackOut为空时，才将stackIn中的全部元素依次转移到stackOut；转移后元素顺序被反转，最早进入的元素位于栈顶。 - 判空规则：只有输入栈与输出栈均为空时，模拟队列才为空。
push：pop/peek：均摊- 空间复杂度：
cpp
class MyQueue {
public:
MyQueue() = default;
void push(int x) {
stackIn.push(x);
}
int pop() {
transferIfNeeded();
int result = stackOut.top();
stackOut.pop();
return result;
}
int peek() {
transferIfNeeded();
return stackOut.top();
}
bool empty() {
return stackIn.empty() && stackOut.empty();
}
private:
stack<int> stackIn;
stack<int> stackOut;
void transferIfNeeded() {
if (!stackOut.empty()) {
return;
}
while (!stackIn.empty()) {
stackOut.push(stackIn.top());
stackIn.pop();
}
}
};class MyQueue {
public:
MyQueue() = default;
void push(int x) {
stackIn.push(x);
}
int pop() {
transferIfNeeded();
int result = stackOut.top();
stackOut.pop();
return result;
}
int peek() {
transferIfNeeded();
return stackOut.top();
}
bool empty() {
return stackIn.empty() && stackOut.empty();
}
private:
stack<int> stackIn;
stack<int> stackOut;
void transferIfNeeded() {
if (!stackOut.empty()) {
return;
}
while (!stackIn.empty()) {
stackOut.push(stackIn.top());
stackIn.pop();
}
}
};每个元素最多经历一次进入
stackIn、一次转移到stackOut和一次弹出，因此pop与peek的均摊复杂度为 。
三、用队列实现栈
- 题目：225. 用队列实现栈
- 核心问题：队列是先进先出，直接在两个队列之间转移元素不会改变顺序，因此需要将主队列中除最后一个元素外的所有元素移入辅助队列。
- 双队列实现：
queue1保存栈中的有效元素。- 执行
pop或top时，将queue1中除最后一个元素外的所有元素转移到queue2。 queue1中最后留下的元素就是栈顶。- 操作完成后交换两个队列，使
queue1重新成为主队列。
push：pop/top：- 空间复杂度：
cpp
class MyStack {
public:
MyStack() = default;
void push(int x) {
queue1.push(x);
}
int pop() {
moveExceptLast();
int result = queue1.front();
queue1.pop();
queue1.swap(queue2);
return result;
}
int top() {
moveExceptLast();
int result = queue1.front();
queue2.push(result);
queue1.pop();
queue1.swap(queue2);
return result;
}
bool empty() {
return queue1.empty();
}
private:
queue<int> queue1;
queue<int> queue2;
// 将除最后一个元素外的其他元素转移到辅助队列
void moveExceptLast() {
while (queue1.size() > 1) {
queue2.push(queue1.front());
queue1.pop();
}
}
};class MyStack {
public:
MyStack() = default;
void push(int x) {
queue1.push(x);
}
int pop() {
moveExceptLast();
int result = queue1.front();
queue1.pop();
queue1.swap(queue2);
return result;
}
int top() {
moveExceptLast();
int result = queue1.front();
queue2.push(result);
queue1.pop();
queue1.swap(queue2);
return result;
}
bool empty() {
return queue1.empty();
}
private:
queue<int> queue1;
queue<int> queue2;
// 将除最后一个元素外的其他元素转移到辅助队列
void moveExceptLast() {
while (queue1.size() > 1) {
queue2.push(queue1.front());
queue1.pop();
}
}
};2026-09-01（周二）
栈与队列（二）
四、有效的括号
- 题目：20. 有效的括号
- 核心方法：遇到左括号时，将其对应的右括号压入栈；遇到右括号时，检查它是否与栈顶的预期字符一致。
- 三种不匹配情况：
- 字符串遍历结束后栈仍不为空：存在没有右括号与之匹配的左括号。
- 遇到右括号时栈顶字符不同：括号类型不匹配。
- 遇到右括号时栈已经为空：该右括号没有对应的左括号。
- 如果字符串长度为奇数，可以直接判定为无效。
- 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
bool isValid(string s) {
if (s.size() % 2 != 0) {
return false;
}
stack<char> expected;
for (char ch : s) {
if (ch == '(') {
expected.push(')');
} else if (ch == '{') {
expected.push('}');
} else if (ch == '[') {
expected.push(']');
} else {
if (expected.empty() || expected.top() != ch) {
return false;
}
expected.pop();
}
}
return expected.empty();
}
};class Solution {
public:
bool isValid(string s) {
if (s.size() % 2 != 0) {
return false;
}
stack<char> expected;
for (char ch : s) {
if (ch == '(') {
expected.push(')');
} else if (ch == '{') {
expected.push('}');
} else if (ch == '[') {
expected.push(']');
} else {
if (expected.empty() || expected.top() != ch) {
return false;
}
expected.pop();
}
}
return expected.empty();
}
};五、删除字符串中的所有相邻重复项
- 题目：1047. 删除字符串中的所有相邻重复项
- 栈模拟消除：
- 如果栈为空或当前字符与栈顶不同，将当前字符压入栈。
- 如果当前字符与栈顶相同，弹出栈顶，使这一对相邻重复字符相互抵消。
- 遍历结束后，栈中保留的字符就是最终结果的逆序。
- 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
string removeDuplicates(string s) {
stack<char> remaining;
for (char ch : s) {
if (remaining.empty() || remaining.top() != ch) {
remaining.push(ch);
} else {
remaining.pop();
}
}
string result;
result.reserve(remaining.size());
while (!remaining.empty()) {
result.push_back(remaining.top());
remaining.pop();
}
reverse(result.begin(), result.end());
return result;
}
};class Solution {
public:
string removeDuplicates(string s) {
stack<char> remaining;
for (char ch : s) {
if (remaining.empty() || remaining.top() != ch) {
remaining.push(ch);
} else {
remaining.pop();
}
}
string result;
result.reserve(remaining.size());
while (!remaining.empty()) {
result.push_back(remaining.top());
remaining.pop();
}
reverse(result.begin(), result.end());
return result;
}
};六、逆波兰表达式求值
- 题目：150. 逆波兰表达式求值
- 栈求值：
- 遇到数字时，将其压入栈。
- 遇到运算符时，依次弹出右操作数与左操作数，计算后将结果重新压入栈。
- 遍历结束后，栈顶元素就是表达式结果。
- 操作数顺序：第一次弹出的是右操作数，第二次弹出的是左操作数；减法与除法不能颠倒。
- 这一过程与删除相邻重复项类似：都根据当前元素与栈顶状态进行“消除”或合并。
- 时间复杂度：
- 空间复杂度：
cpp
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<long long> operands;
for (const string& token : tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
long long right = operands.top();
operands.pop();
long long left = operands.top();
operands.pop();
if (token == "+") {
operands.push(left + right);
} else if (token == "-") {
operands.push(left - right);
} else if (token == "*") {
operands.push(left * right);
} else {
operands.push(left / right);
}
} else {
operands.push(stoll(token));
}
}
return static_cast<int>(operands.top());
}
};class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<long long> operands;
for (const string& token : tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
long long right = operands.top();
operands.pop();
long long left = operands.top();
operands.pop();
if (token == "+") {
operands.push(left + right);
} else if (token == "-") {
operands.push(left - right);
} else if (token == "*") {
operands.push(left * right);
} else {
operands.push(left / right);
}
} else {
operands.push(stoll(token));
}
}
return static_cast<int>(operands.top());
}
};2026-09-02（周三）
栈与队列（三）
七、滑动窗口最大值
- 题目：239. 滑动窗口最大值
- 单调队列：只维护仍有可能成为窗口最大值的元素，并让队列从队首到队尾保持单调不增。
- 入队规则：新元素入队前，将队尾所有小于新元素的值弹出；这些较小元素不可能再成为后续窗口的最大值。
- 出队规则：窗口左侧元素离开时，只有当它等于队首元素时才弹出队首。
- 查询最大值：队首始终是当前窗口最大值。
- 时间复杂度：，每个元素至多入队和出队一次
- 空间复杂度：
cpp
class Solution {
private:
class MonotonicQueue {
public:
void pop(int value) {
if (!values.empty() && values.front() == value) {
values.pop_front();
}
}
void push(int value) {
while (!values.empty() && values.back() < value) {
values.pop_back();
}
values.push_back(value);
}
int max() const {
return values.front();
}
private:
deque<int> values;
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MonotonicQueue window;
vector<int> result;
result.reserve(nums.size() - k + 1);
for (int i = 0; i < k; i++) {
window.push(nums[i]);
}
result.push_back(window.max());
for (int i = k; i < nums.size(); i++) {
window.pop(nums[i - k]);
window.push(nums[i]);
result.push_back(window.max());
}
return result;
}
};class Solution {
private:
class MonotonicQueue {
public:
void pop(int value) {
if (!values.empty() && values.front() == value) {
values.pop_front();
}
}
void push(int value) {
while (!values.empty() && values.back() < value) {
values.pop_back();
}
values.push_back(value);
}
int max() const {
return values.front();
}
private:
deque<int> values;
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MonotonicQueue window;
vector<int> result;
result.reserve(nums.size() - k + 1);
for (int i = 0; i < k; i++) {
window.push(nums[i]);
}
result.push_back(window.max());
for (int i = k; i < nums.size(); i++) {
window.pop(nums[i - k]);
window.push(nums[i]);
result.push_back(window.max());
}
return result;
}
};八、前 K 个高频元素
- 题目：347. 前 K 个高频元素
- 频率统计：使用
unordered_map记录每个元素的出现次数。 - 小顶堆：维护一个大小不超过 的小顶堆，堆顶始终是当前候选项中频率最低的元素。
- 将“频率—元素”对压入堆中。
- 当堆大小超过 时，弹出频率最低的元素。
- 遍历结束后，堆中保留的就是频率最高的 个元素。
- 时间复杂度：，其中 为不同元素的数量
- 空间复杂度：
cpp
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> frequency;
for (int num : nums) {
frequency[num]++;
}
// pair.first 为频率，pair.second 为元素；使用小顶堆
priority_queue<
pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>
> minHeap;
for (const auto& [num, freq] : frequency) {
minHeap.push({freq, num});
if (minHeap.size() > k) {
minHeap.pop();
}
}
vector<int> result;
result.reserve(k);
while (!minHeap.empty()) {
result.push_back(minHeap.top().second);
minHeap.pop();
}
return result;
}
};class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> frequency;
for (int num : nums) {
frequency[num]++;
}
// pair.first 为频率，pair.second 为元素；使用小顶堆
priority_queue<
pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>
> minHeap;
for (const auto& [num, freq] : frequency) {
minHeap.push({freq, num});
if (minHeap.size() > k) {
minHeap.pop();
}
}
vector<int> result;
result.reserve(k);
while (!minHeap.empty()) {
result.push_back(minHeap.top().second);
minHeap.pop();
}
return result;
}
};若题目不要求按频率降序返回，直接依次弹出小顶堆即可；此时结果中的顺序不固定。
九、栈与队列总结
常见问题
stack和queue是容器吗？- 不是。它们是容器适配器，通过限制底层容器的接口来表现栈或队列的行为。
- 它们属于哪个版本的 STL？
- C++ 标准只规定接口与行为，具体实现取决于所用的标准库，例如 GCC 的 libstdc++、Clang 的 libc++ 或 MSVC STL；课程中常以 SGI STL 为实现参考。
- 它们通常如何实现？
stack与queue默认均以deque作为底层容器，也可以按接口要求替换其他容器。
- 它们提供迭代器吗？
- 不提供。容器适配器只暴露栈顶、队首、队尾等受限接口，不能直接遍历内部元素。
面试问题：栈中元素在内存里连续吗？
- 不一定。
stack是容器适配器，元素的内存布局取决于底层容器。 - 默认底层容器是
deque；deque采用分段连续存储，整体内存并不连续。 - 如果显式使用
vector作为底层容器，元素才是连续存储的。
经典题型
- 栈：结构模拟、括号匹配、相邻元素消除、逆波兰表达式求值
- 队列：滑动窗口最大值
- 优先队列：前 K 个高频元素
堆的定义
- 堆是一棵完全二叉树。
- 大顶堆：每个节点的值都不小于其子节点。
- 小顶堆：每个节点的值都不大于其子节点。
2026-09-03（周四）
二叉树（一）
二叉树专题主要覆盖递归、迭代、层序遍历、属性计算、树的构造、二叉搜索树以及最近公共祖先等内容。
一、二叉树理论基础
常见类型
- 满二叉树：只有度为 0 和度为 2 的节点，并且所有叶子节点都在同一层。若共有 层，则节点总数为 。
- 完全二叉树：除最底层外，其余各层节点数均达到最大值；最底层的节点从左到右连续排列。若最底层是第 层，则该层节点数介于 1 与 之间。
- 二叉搜索树（BST）：一种有序二叉树。
- 左子树中所有节点的值均小于根节点的值。
- 右子树中所有节点的值均大于根节点的值。
- 左右子树也分别是二叉搜索树。
- 平衡二叉搜索树（AVL 树）：空树，或任意节点左右子树高度差的绝对值不超过 1，并且左右子树也都是平衡二叉树。
C++ 标准规定
map、set、multimap和multiset的主要操作复杂度为 ，常见实现采用红黑树；unordered_map和unordered_set通常使用哈希表，平均查询与增删复杂度为 。
存储方式
- 链式存储：每个节点通过指针连接左右孩子。
- 顺序存储：使用数组保存节点。采用从 0 开始的下标时，若父节点下标为 ：
- 左孩子下标为
- 右孩子下标为
遍历方式
- 深度优先遍历（DFS）：沿一条路径向深处访问，遇到叶子节点后回退。
- 前序遍历：中 → 左 → 右
- 中序遍历：左 → 中 → 右
- 后序遍历：左 → 右 → 中
- 广度优先遍历（BFS）：按层从上到下遍历，也称层序遍历。
前序、中序和后序中的“前、中、后”，指的是根节点相对于左右子树的处理顺序。DFS 通常使用递归或栈实现，BFS 通常使用队列实现。
节点定义
cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};二、二叉树的递归遍历
- 题目：144. 二叉树的前序遍历
- 题目：94. 二叉树的中序遍历
- 题目：145. 二叉树的后序遍历
递归算法的三个要素
- 确定参数和返回值：明确递归过程中需要传递和处理的数据，以及函数应返回什么。
- 确定终止条件：避免递归无限进行并导致调用栈溢出；遍历二叉树时，通常在当前节点为
nullptr时返回。 - 确定单层递归逻辑：明确当前层应处理什么，以及左右子树的递归调用顺序。
cpp
// 前序遍历：中 → 左 → 右
void preorder(TreeNode* node, vector<int>& result) {
if (node == nullptr) {
return;
}
result.push_back(node->val);
preorder(node->left, result);
preorder(node->right, result);
}
// 中序遍历：左 → 中 → 右
void inorder(TreeNode* node, vector<int>& result) {
if (node == nullptr) {
return;
}
inorder(node->left, result);
result.push_back(node->val);
inorder(node->right, result);
}
// 后序遍历：左 → 右 → 中
void postorder(TreeNode* node, vector<int>& result) {
if (node == nullptr) {
return;
}
postorder(node->left, result);
postorder(node->right, result);
result.push_back(node->val);
}// 前序遍历：中 → 左 → 右
void preorder(TreeNode* node, vector<int>& result) {
if (node == nullptr) {
return;
}
result.push_back(node->val);
preorder(node->left, result);
preorder(node->right, result);
}
// 中序遍历：左 → 中 → 右
void inorder(TreeNode* node, vector<int>& result) {
if (node == nullptr) {
return;
}
inorder(node->left, result);
result.push_back(node->val);
inorder(node->right, result);
}
// 后序遍历：左 → 右 → 中
void postorder(TreeNode* node, vector<int>& result) {
if (node == nullptr) {
return;
}
postorder(node->left, result);
postorder(node->right, result);
result.push_back(node->val);
}- 时间复杂度：
- 空间复杂度：，来自递归调用栈；最坏情况下为
三、二叉树的迭代遍历
使用栈可以迭代实现二叉树的前序、中序和后序遍历。
前序遍历
前序顺序是“中 → 左 → 右”。由于栈是先进后出，因此处理当前节点后，应先压入右孩子，再压入左孩子。
cpp
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
if (root == nullptr) {
return result;
}
stack<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty()) {
TreeNode* node = nodes.top();
nodes.pop();
result.push_back(node->val);
if (node->right != nullptr) {
nodes.push(node->right);
}
if (node->left != nullptr) {
nodes.push(node->left);
}
}
return result;
}
};class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
if (root == nullptr) {
return result;
}
stack<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty()) {
TreeNode* node = nodes.top();
nodes.pop();
result.push_back(node->val);
if (node->right != nullptr) {
nodes.push(node->right);
}
if (node->left != nullptr) {
nodes.push(node->left);
}
}
return result;
}
};中序遍历
中序顺序是“左 → 中 → 右”，访问节点的顺序与处理节点值的顺序不一致。因此，使用指针负责沿左侧访问节点，使用栈保存尚未处理的节点。
cpp
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> nodes;
TreeNode* current = root;
while (current != nullptr || !nodes.empty()) {
if (current != nullptr) {
nodes.push(current);
current = current->left;
} else {
current = nodes.top();
nodes.pop();
result.push_back(current->val);
current = current->right;
}
}
return result;
}
};class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> nodes;
TreeNode* current = root;
while (current != nullptr || !nodes.empty()) {
if (current != nullptr) {
nodes.push(current);
current = current->left;
} else {
current = nodes.top();
nodes.pop();
result.push_back(current->val);
current = current->right;
}
}
return result;
}
};后序遍历
将前序遍历的入栈顺序调整为先压入左孩子、再压入右孩子，可以得到“中 → 右 → 左”；最后反转结果，即可得到“左 → 右 → 中”。
cpp
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if (root == nullptr) {
return result;
}
stack<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty()) {
TreeNode* node = nodes.top();
nodes.pop();
result.push_back(node->val);
if (node->left != nullptr) {
nodes.push(node->left);
}
if (node->right != nullptr) {
nodes.push(node->right);
}
}
reverse(result.begin(), result.end());
return result;
}
};class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if (root == nullptr) {
return result;
}
stack<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty()) {
TreeNode* node = nodes.top();
nodes.pop();
result.push_back(node->val);
if (node->left != nullptr) {
nodes.push(node->left);
}
if (node->right != nullptr) {
nodes.push(node->right);
}
}
reverse(result.begin(), result.end());
return result;
}
};- 时间复杂度：
- 额外空间复杂度：，最坏情况下为
2026-09-05（周六）
二叉树（三）
九、二叉树的最大深度
本题中的最大深度，是从根节点到最远叶子节点的最长路径上的节点数。
- 节点深度：从根节点到该节点的路径所经过的节点数。
- 节点高度：从该节点到最远叶子节点的路径所经过的节点数。
对整棵树而言，根节点的高度就是树的最大深度。可以使用后序遍历计算高度，也可以使用前序遍历记录深度，或使用层序遍历统计层数。
方法一：后序遍历——计算高度
先得到左右子树的高度，再取较大值并加上当前节点这一层。
cpp
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
};class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
};- 时间复杂度：
- 空间复杂度：，来自递归调用栈；最坏情况下为
方法二：前序遍历——记录深度
前序遍历在到达节点时更新最大深度。这里将 depth + 1 按值传入下一层，相当于完成了隐式回溯，不需要手动执行 depth++ 和 depth--。
cpp
class Solution {
private:
int result = 0;
void getDepth(TreeNode* node, int depth) {
if (node == nullptr) {
return;
}
result = max(result, depth);
getDepth(node->left, depth + 1);
getDepth(node->right, depth + 1);
}
public:
int maxDepth(TreeNode* root) {
getDepth(root, 1);
return result;
}
};class Solution {
private:
int result = 0;
void getDepth(TreeNode* node, int depth) {
if (node == nullptr) {
return;
}
result = max(result, depth);
getDepth(node->left, depth + 1);
getDepth(node->right, depth + 1);
}
public:
int maxDepth(TreeNode* root) {
getDepth(root, 1);
return result;
}
};方法三：层序遍历——统计层数
每处理完一层，深度加一。
cpp
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int depth = 0;
queue<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty()) {
int levelSize = nodes.size();
++depth;
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = nodes.front();
nodes.pop();
if (node->left != nullptr) {
nodes.push(node->left);
}
if (node->right != nullptr) {
nodes.push(node->right);
}
}
}
return depth;
}
};class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int depth = 0;
queue<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty()) {
int levelSize = nodes.size();
++depth;
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = nodes.front();
nodes.pop();
if (node->left != nullptr) {
nodes.push(node->left);
}
if (node->right != nullptr) {
nodes.push(node->right);
}
}
}
return depth;
}
};- 时间复杂度：
- 空间复杂度：，其中 为二叉树的最大宽度
十、二叉树的最小深度
最小深度是从根节点到最近叶子节点的最短路径上的节点数。叶子节点必须同时满足左右孩子均为空。
易错点
如果某个节点只有一棵子树，不能直接使用
min(leftDepth, rightDepth) + 1，因为空子树并没有通向叶子节点。此时必须沿非空子树继续计算。
方法一：后序递归
cpp
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftDepth = minDepth(root->left);
int rightDepth = minDepth(root->right);
if (root->left == nullptr) {
return rightDepth + 1;
}
if (root->right == nullptr) {
return leftDepth + 1;
}
return min(leftDepth, rightDepth) + 1;
}
};class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftDepth = minDepth(root->left);
int rightDepth = minDepth(root->right);
if (root->left == nullptr) {
return rightDepth + 1;
}
if (root->right == nullptr) {
return leftDepth + 1;
}
return min(leftDepth, rightDepth) + 1;
}
};- 时间复杂度：
- 空间复杂度：，最坏情况下为
方法二：前序递归
到达叶子节点时更新当前最小深度。
cpp
class Solution {
private:
int result = INT_MAX;
void getDepth(TreeNode* node, int depth) {
if (node == nullptr) {
return;
}
if (node->left == nullptr && node->right == nullptr) {
result = min(result, depth);
return;
}
getDepth(node->left, depth + 1);
getDepth(node->right, depth + 1);
}
public:
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
getDepth(root, 1);
return result;
}
};class Solution {
private:
int result = INT_MAX;
void getDepth(TreeNode* node, int depth) {
if (node == nullptr) {
return;
}
if (node->left == nullptr && node->right == nullptr) {
result = min(result, depth);
return;
}
getDepth(node->left, depth + 1);
getDepth(node->right, depth + 1);
}
public:
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
getDepth(root, 1);
return result;
}
};方法三：层序遍历
BFS 按层搜索，遇到的第一个叶子节点一定处于最浅的一层，可以立即返回当前深度。
cpp
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int depth = 0;
queue<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty()) {
int levelSize = nodes.size();
++depth;
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = nodes.front();
nodes.pop();
if (node->left == nullptr && node->right == nullptr) {
return depth;
}
if (node->left != nullptr) {
nodes.push(node->left);
}
if (node->right != nullptr) {
nodes.push(node->right);
}
}
}
return depth;
}
};class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int depth = 0;
queue<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty()) {
int levelSize = nodes.size();
++depth;
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = nodes.front();
nodes.pop();
if (node->left == nullptr && node->right == nullptr) {
return depth;
}
if (node->left != nullptr) {
nodes.push(node->left);
}
if (node->right != nullptr) {
nodes.push(node->right);
}
}
}
return depth;
}
};- 时间复杂度：最坏为
- 空间复杂度：，其中 为二叉树的最大宽度
十一、完全二叉树的节点个数
方法一：按照普通二叉树递归统计
遍历所有节点即可得到答案。该方法正确且直观，但没有利用完全二叉树的结构性质。
cpp
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftCount = countNodes(root->left);
int rightCount = countNodes(root->right);
return leftCount + rightCount + 1;
}
};class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftCount = countNodes(root->left);
int rightCount = countNodes(root->right);
return leftCount + rightCount + 1;
}
};- 时间复杂度：
- 空间复杂度：
方法二：利用完全二叉树性质
对于完全二叉树中的任意子树：
- 分别沿最左路径和最右路径计算深度。
- 如果两者相等，说明当前子树是满二叉树，可直接用 计算节点数。
- 如果两者不等，则继续递归统计左右子树。
cpp
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftDepth = 0;
int rightDepth = 0;
TreeNode* left = root->left;
while (left != nullptr) {
left = left->left;
++leftDepth;
}
TreeNode* right = root->right;
while (right != nullptr) {
right = right->right;
++rightDepth;
}
if (leftDepth == rightDepth) {
return static_cast<int>((1LL << (leftDepth + 1)) - 1);
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
};class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftDepth = 0;
int rightDepth = 0;
TreeNode* left = root->left;
while (left != nullptr) {
left = left->left;
++leftDepth;
}
TreeNode* right = root->right;
while (right != nullptr) {
right = right->right;
++rightDepth;
}
if (leftDepth == rightDepth) {
return static_cast<int>((1LL << (leftDepth + 1)) - 1);
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
};- 时间复杂度：
- 空间复杂度：，来自递归调用栈
2026-09-07（周一）
二叉树（四）
十二、平衡二叉树
题目：110. 平衡二叉树
平衡二叉树要求每个节点的左右子树高度差不超过 1。判断时需要先得到左右子树的高度，因此适合使用“左 → 右 → 中”的后序遍历。
递归函数有两种返回含义：
- 返回非负数：当前子树平衡，该值表示子树高度。
- 返回
-1：当前子树已经不平衡，可以立即向上返回，无须继续计算。
cpp
class Solution {
private:
int getHeight(TreeNode* node) {
if (node == nullptr) {
return 0;
}
int leftHeight = getHeight(node->left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = getHeight(node->right);
if (rightHeight == -1) {
return -1;
}
if (abs(leftHeight - rightHeight) > 1) {
return -1;
}
return max(leftHeight, rightHeight) + 1;
}
public:
bool isBalanced(TreeNode* root) {
return getHeight(root) != -1;
}
};class Solution {
private:
int getHeight(TreeNode* node) {
if (node == nullptr) {
return 0;
}
int leftHeight = getHeight(node->left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = getHeight(node->right);
if (rightHeight == -1) {
return -1;
}
if (abs(leftHeight - rightHeight) > 1) {
return -1;
}
return max(leftHeight, rightHeight) + 1;
}
public:
bool isBalanced(TreeNode* root) {
return getHeight(root) != -1;
}
};- 时间复杂度：，每个节点最多访问一次
- 空间复杂度：，来自递归调用栈；最坏情况下为
十三、二叉树的所有路径
题目要求记录从根节点到每个叶子节点的路径。使用前序遍历可以按“父节点 → 子节点”的方向构造路径；完成一条路径后，需要通过回溯撤销当前节点，再进入其他分支。
回溯过程可以概括为：
- 将当前节点加入
path。 - 如果到达叶子节点，生成路径字符串并保存。
- 递归遍历左右子树。
- 执行
path.pop_back()，撤销当前节点的选择。
cpp
class Solution {
private:
void traversal(
TreeNode* node,
vector<int>& path,
vector<string>& result
) {
path.push_back(node->val);
if (node->left == nullptr && node->right == nullptr) {
string currentPath = to_string(path[0]);
for (size_t i = 1; i < path.size(); ++i) {
currentPath += "->" + to_string(path[i]);
}
result.push_back(currentPath);
} else {
if (node->left != nullptr) {
traversal(node->left, path, result);
}
if (node->right != nullptr) {
traversal(node->right, path, result);
}
}
path.pop_back();
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
if (root == nullptr) {
return result;
}
vector<int> path;
traversal(root, path, result);
return result;
}
};class Solution {
private:
void traversal(
TreeNode* node,
vector<int>& path,
vector<string>& result
) {
path.push_back(node->val);
if (node->left == nullptr && node->right == nullptr) {
string currentPath = to_string(path[0]);
for (size_t i = 1; i < path.size(); ++i) {
currentPath += "->" + to_string(path[i]);
}
result.push_back(currentPath);
} else {
if (node->left != nullptr) {
traversal(node->left, path, result);
}
if (node->right != nullptr) {
traversal(node->right, path, result);
}
}
path.pop_back();
}
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
if (root == nullptr) {
return result;
}
vector<int> path;
traversal(root, path, result);
return result;
}
};- 时间复杂度：，其中 为所有输出路径的总长度；最坏情况下可达
- 空间复杂度：不计输出结果为 ，用于递归调用栈和当前路径
十四、左叶子之和
题目：404. 左叶子之和
左叶子不是“二叉树左侧的节点”，而是某个父节点的左孩子，并且该左孩子没有任何孩子。当前节点无法独立判断自己是不是左叶子，通常需要由父节点检查其左孩子：
text
node->left != nullptr
&& node->left->left == nullptr
&& node->left->right == nullptrnode->left != nullptr
&& node->left->left == nullptr
&& node->left->right == nullptr易错点
根节点即使没有孩子，也不是左叶子，因为它不是任何节点的左孩子。
方法一：递归遍历
cpp
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int result = 0;
if (root->left != nullptr
&& root->left->left == nullptr
&& root->left->right == nullptr) {
result += root->left->val;
} else {
result += sumOfLeftLeaves(root->left);
}
result += sumOfLeftLeaves(root->right);
return result;
}
};class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int result = 0;
if (root->left != nullptr
&& root->left->left == nullptr
&& root->left->right == nullptr) {
result += root->left->val;
} else {
result += sumOfLeftLeaves(root->left);
}
result += sumOfLeftLeaves(root->right);
return result;
}
};- 时间复杂度：
- 空间复杂度：，来自递归调用栈
方法二：迭代遍历
cpp
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int result = 0;
stack<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty()) {
TreeNode* node = nodes.top();
nodes.pop();
if (node->left != nullptr
&& node->left->left == nullptr
&& node->left->right == nullptr) {
result += node->left->val;
}
if (node->right != nullptr) {
nodes.push(node->right);
}
if (node->left != nullptr) {
nodes.push(node->left);
}
}
return result;
}
};class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int result = 0;
stack<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty()) {
TreeNode* node = nodes.top();
nodes.pop();
if (node->left != nullptr
&& node->left->left == nullptr
&& node->left->right == nullptr) {
result += node->left->val;
}
if (node->right != nullptr) {
nodes.push(node->right);
}
if (node->left != nullptr) {
nodes.push(node->left);
}
}
return result;
}
};- 时间复杂度：
- 空间复杂度：，最坏情况下为
2026-09-08（周二）
二叉树（五）
十五、找树左下角的值
题目：513. 找树左下角的值
目标是找到二叉树最底层最左边节点的值。使用层序遍历时，每层第一个出队的节点就是该层最左侧节点；不断更新结果，遍历结束后保留的就是最后一层最左侧节点的值。
cpp
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
int result = root->val;
queue<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty()) {
int levelSize = nodes.size();
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = nodes.front();
nodes.pop();
if (i == 0) {
result = node->val;
}
if (node->left != nullptr) {
nodes.push(node->left);
}
if (node->right != nullptr) {
nodes.push(node->right);
}
}
}
return result;
}
};class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
int result = root->val;
queue<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty()) {
int levelSize = nodes.size();
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = nodes.front();
nodes.pop();
if (i == 0) {
result = node->val;
}
if (node->left != nullptr) {
nodes.push(node->left);
}
if (node->right != nullptr) {
nodes.push(node->right);
}
}
}
return result;
}
};- 时间复杂度：
- 空间复杂度：，其中 为二叉树的最大宽度
十六、路径总和
题目：112. 路径总和
判断是否存在一条从根节点到叶子节点的路径，使路径上的节点值之和等于 targetSum。遍历过程中维护剩余目标值：访问当前节点时减去节点值，到达叶子节点时判断剩余值是否为 0。
易错点
路径必须终止于叶子节点，不能在中间节点处仅因为剩余值为 0 就返回
true。
cpp
class Solution {
private:
bool traversal(TreeNode* node, int remaining) {
remaining -= node->val;
if (node->left == nullptr && node->right == nullptr) {
return remaining == 0;
}
if (node->left != nullptr && traversal(node->left, remaining)) {
return true;
}
if (node->right != nullptr && traversal(node->right, remaining)) {
return true;
}
return false;
}
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (root == nullptr) {
return false;
}
return traversal(root, targetSum);
}
};class Solution {
private:
bool traversal(TreeNode* node, int remaining) {
remaining -= node->val;
if (node->left == nullptr && node->right == nullptr) {
return remaining == 0;
}
if (node->left != nullptr && traversal(node->left, remaining)) {
return true;
}
if (node->right != nullptr && traversal(node->right, remaining)) {
return true;
}
return false;
}
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (root == nullptr) {
return false;
}
return traversal(root, targetSum);
}
};remaining 按值传递，因此返回上一层时会自动恢复，无须手动执行加法回溯。
- 时间复杂度：
- 空间复杂度：，来自递归调用栈；最坏情况下为
十七、从中序与后序遍历序列构造二叉树
两种遍历序列分别具有以下结构：
- 中序遍历：
左子树 → 根节点 → 右子树 - 后序遍历：
左子树 → 右子树 → 根节点
因此，后序序列的最后一个元素就是当前子树的根节点。用它在中序序列中定位切割点，即可确定左右子树的范围，再递归构造。
递归步骤
- 从后序序列末尾取得当前根节点。
- 在中序序列中找到根节点的位置。
- 根节点左侧属于左子树，右侧属于右子树。
- 逆序读取后序序列时，顺序是“根 → 右 → 左”，因此必须先构造右子树，再构造左子树。
直接切割并复制数组容易理解，但最坏情况下会产生 的查找和复制开销。下面使用哈希表记录中序下标，并使用区间边界避免复制数组。
cpp
class Solution {
private:
unordered_map<int, int> inorderIndex;
int postorderIndex = 0;
TreeNode* build(
const vector<int>& postorder,
int inorderLeft,
int inorderRight
) {
if (inorderLeft > inorderRight) {
return nullptr;
}
int rootValue = postorder[postorderIndex--];
TreeNode* root = new TreeNode(rootValue);
int rootIndex = inorderIndex[rootValue];
root->right = build(postorder, rootIndex + 1, inorderRight);
root->left = build(postorder, inorderLeft, rootIndex - 1);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.empty()) {
return nullptr;
}
for (int i = 0; i < static_cast<int>(inorder.size()); ++i) {
inorderIndex[inorder[i]] = i;
}
postorderIndex = static_cast<int>(postorder.size()) - 1;
return build(postorder, 0, static_cast<int>(inorder.size()) - 1);
}
};class Solution {
private:
unordered_map<int, int> inorderIndex;
int postorderIndex = 0;
TreeNode* build(
const vector<int>& postorder,
int inorderLeft,
int inorderRight
) {
if (inorderLeft > inorderRight) {
return nullptr;
}
int rootValue = postorder[postorderIndex--];
TreeNode* root = new TreeNode(rootValue);
int rootIndex = inorderIndex[rootValue];
root->right = build(postorder, rootIndex + 1, inorderRight);
root->left = build(postorder, inorderLeft, rootIndex - 1);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.empty()) {
return nullptr;
}
for (int i = 0; i < static_cast<int>(inorder.size()); ++i) {
inorderIndex[inorder[i]] = i;
}
postorderIndex = static_cast<int>(postorder.size()) - 1;
return build(postorder, 0, static_cast<int>(inorder.size()) - 1);
}
};- 时间复杂度：
- 空间复杂度：，用于哈希表；递归调用栈额外占用
2026-09-09（周三）
二叉树（六）
十八、最大二叉树
题目：654. 最大二叉树
最大二叉树的构造规则如下：
- 找到当前区间中的最大值，将其作为根节点。
- 使用最大值左侧的区间递归构造左子树。
- 使用最大值右侧的区间递归构造右子树。
与从中序与后序遍历序列构造二叉树相同，可以通过区间下标切分数组，避免在每层递归中创建新的 vector。下面统一使用左闭右开区间 [left, right)：
cpp
class Solution {
private:
TreeNode* build(const vector<int>& nums, int left, int right) {
if (left >= right) {
return nullptr;
}
int maxIndex = left;
for (int i = left + 1; i < right; ++i) {
if (nums[i] > nums[maxIndex]) {
maxIndex = i;
}
}
TreeNode* root = new TreeNode(nums[maxIndex]);
root->left = build(nums, left, maxIndex);
root->right = build(nums, maxIndex + 1, right);
return root;
}
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return build(nums, 0, static_cast<int>(nums.size()));
}
};class Solution {
private:
TreeNode* build(const vector<int>& nums, int left, int right) {
if (left >= right) {
return nullptr;
}
int maxIndex = left;
for (int i = left + 1; i < right; ++i) {
if (nums[i] > nums[maxIndex]) {
maxIndex = i;
}
}
TreeNode* root = new TreeNode(nums[maxIndex]);
root->left = build(nums, left, maxIndex);
root->right = build(nums, maxIndex + 1, right);
return root;
}
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return build(nums, 0, static_cast<int>(nums.size()));
}
};使用下标避免了数组复制，但每层仍需扫描区间寻找最大值：
- 时间复杂度：平均为 ，最坏情况下为
- 空间复杂度：，来自递归调用栈；最坏情况下为
进一步优化
如果需要将时间复杂度优化到 ，可以使用单调递减栈构造最大二叉树。
十九、合并二叉树
题目：617. 合并二叉树
同时遍历两棵树中位置相同的节点：
- 如果一棵树的当前节点为空，直接返回另一棵树的节点。
- 如果两个节点均存在，将它们的值相加。
- 递归合并左右子树，并将结果连接到第一棵树上。
cpp
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (root1 == nullptr) {
return root2;
}
if (root2 == nullptr) {
return root1;
}
root1->val += root2->val;
root1->left = mergeTrees(root1->left, root2->left);
root1->right = mergeTrees(root1->right, root2->right);
return root1;
}
};class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (root1 == nullptr) {
return root2;
}
if (root2 == nullptr) {
return root1;
}
root1->val += root2->val;
root1->left = mergeTrees(root1->left, root2->left);
root1->right = mergeTrees(root1->right, root2->right);
return root1;
}
};原地修改
该写法会直接修改
root1，并可能复用root2中未重叠的子树。如果需要保留两棵原树，应为结果树创建新节点。
- 时间复杂度：，其中 为两棵树重叠部分的节点数
- 空间复杂度：，其中 为重叠部分的最大递归深度
二十、二叉搜索树中的搜索
二叉搜索树（BST）具有有序性：
- 左子树中的所有节点值均小于根节点值。
- 右子树中的所有节点值均大于根节点值。
- 左右子树也分别是二叉搜索树。
因此无须遍历整棵树：目标值较小时只搜索左子树，较大时只搜索右子树。节点的有序性已经确定了唯一的搜索方向，所以不需要遍历其他分支，也不需要回溯。
方法一：递归搜索
cpp
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int value) {
if (root == nullptr || root->val == value) {
return root;
}
if (value < root->val) {
return searchBST(root->left, value);
}
return searchBST(root->right, value);
}
};class Solution {
public:
TreeNode* searchBST(TreeNode* root, int value) {
if (root == nullptr || root->val == value) {
return root;
}
if (value < root->val) {
return searchBST(root->left, value);
}
return searchBST(root->right, value);
}
};方法二：迭代搜索
每次比较后直接移动到左孩子或右孩子，直到找到目标节点或走到空节点。
cpp
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int value) {
while (root != nullptr) {
if (value < root->val) {
root = root->left;
} else if (value > root->val) {
root = root->right;
} else {
return root;
}
}
return nullptr;
}
};class Solution {
public:
TreeNode* searchBST(TreeNode* root, int value) {
while (root != nullptr) {
if (value < root->val) {
root = root->left;
} else if (value > root->val) {
root = root->right;
} else {
return root;
}
}
return nullptr;
}
};- 时间复杂度：；平衡时为 ，最坏情况下为
- 空间复杂度：递归法为 ，迭代法为
2026-09-10（周四）
祝所有认真负责的教师节日快乐！
二叉树（七）
二十一、验证二叉搜索树
题目：98. 验证二叉搜索树
二叉搜索树的中序遍历结果应当是一个严格递增的序列。因此，验证二叉搜索树可以转化为判断中序序列是否严格递增。
易错点
有效二叉搜索树中不能出现相同值，所以只要发现
values[i] <= values[i - 1]，就应返回false。
cpp
class Solution {
private:
void inorder(TreeNode* node, vector<int>& values) {
if (node == nullptr) {
return;
}
inorder(node->left, values);
values.push_back(node->val);
inorder(node->right, values);
}
public:
bool isValidBST(TreeNode* root) {
vector<int> values;
inorder(root, values);
for (size_t i = 1; i < values.size(); ++i) {
if (values[i] <= values[i - 1]) {
return false;
}
}
return true;
}
};class Solution {
private:
void inorder(TreeNode* node, vector<int>& values) {
if (node == nullptr) {
return;
}
inorder(node->left, values);
values.push_back(node->val);
inorder(node->right, values);
}
public:
bool isValidBST(TreeNode* root) {
vector<int> values;
inorder(root, values);
for (size_t i = 1; i < values.size(); ++i) {
if (values[i] <= values[i - 1]) {
return false;
}
}
return true;
}
};- 时间复杂度：
- 空间复杂度：，用于中序序列；递归调用栈额外占用
二十二、二叉搜索树的最小绝对差
二叉搜索树的中序序列严格递增，任意两节点之间的最小差值一定出现在序列中相邻的两个元素之间。因此，只需在中序遍历中比较相邻节点。
方法一：转换为有序数组
cpp
class Solution {
private:
void inorder(TreeNode* node, vector<int>& values) {
if (node == nullptr) {
return;
}
inorder(node->left, values);
values.push_back(node->val);
inorder(node->right, values);
}
public:
int getMinimumDifference(TreeNode* root) {
vector<int> values;
inorder(root, values);
int result = INT_MAX;
for (size_t i = 1; i < values.size(); ++i) {
result = min(result, values[i] - values[i - 1]);
}
return result;
}
};class Solution {
private:
void inorder(TreeNode* node, vector<int>& values) {
if (node == nullptr) {
return;
}
inorder(node->left, values);
values.push_back(node->val);
inorder(node->right, values);
}
public:
int getMinimumDifference(TreeNode* root) {
vector<int> values;
inorder(root, values);
int result = INT_MAX;
for (size_t i = 1; i < values.size(); ++i) {
result = min(result, values[i] - values[i - 1]);
}
return result;
}
};- 时间复杂度：
- 空间复杂度：，用于保存中序序列
方法二：记录前驱节点
无须保存完整序列，只需使用 previous 记录中序遍历中的前一个节点。
cpp
class Solution {
private:
int result = INT_MAX;
TreeNode* previous = nullptr;
void inorder(TreeNode* node) {
if (node == nullptr) {
return;
}
inorder(node->left);
if (previous != nullptr) {
result = min(result, node->val - previous->val);
}
previous = node;
inorder(node->right);
}
public:
int getMinimumDifference(TreeNode* root) {
result = INT_MAX;
previous = nullptr;
inorder(root);
return result;
}
};class Solution {
private:
int result = INT_MAX;
TreeNode* previous = nullptr;
void inorder(TreeNode* node) {
if (node == nullptr) {
return;
}
inorder(node->left);
if (previous != nullptr) {
result = min(result, node->val - previous->val);
}
previous = node;
inorder(node->right);
}
public:
int getMinimumDifference(TreeNode* root) {
result = INT_MAX;
previous = nullptr;
inorder(root);
return result;
}
};- 时间复杂度：
- 空间复杂度：，仅计算递归调用栈；最坏情况下为
二十三、二叉搜索树中的众数
众数是出现频率最高的元素。如果是普通二叉树，可以使用哈希表统计频率；对于二叉搜索树，中序遍历会使相同值连续出现，因此可以直接统计连续元素的出现次数。
需要维护四个状态：
previous：中序遍历中的前一个节点。currentCount：当前值连续出现的次数。maxCount：已经发现的最大出现次数。result：所有出现次数等于maxCount的节点值。
cpp
class Solution {
private:
int currentCount = 0;
int maxCount = 0;
TreeNode* previous = nullptr;
vector<int> result;
void inorder(TreeNode* node) {
if (node == nullptr) {
return;
}
inorder(node->left);
if (previous != nullptr && previous->val == node->val) {
++currentCount;
} else {
currentCount = 1;
}
previous = node;
if (currentCount > maxCount) {
maxCount = currentCount;
result.clear();
result.push_back(node->val);
} else if (currentCount == maxCount) {
result.push_back(node->val);
}
inorder(node->right);
}
public:
vector<int> findMode(TreeNode* root) {
currentCount = 0;
maxCount = 0;
previous = nullptr;
result.clear();
inorder(root);
return result;
}
};class Solution {
private:
int currentCount = 0;
int maxCount = 0;
TreeNode* previous = nullptr;
vector<int> result;
void inorder(TreeNode* node) {
if (node == nullptr) {
return;
}
inorder(node->left);
if (previous != nullptr && previous->val == node->val) {
++currentCount;
} else {
currentCount = 1;
}
previous = node;
if (currentCount > maxCount) {
maxCount = currentCount;
result.clear();
result.push_back(node->val);
} else if (currentCount == maxCount) {
result.push_back(node->val);
}
inorder(node->right);
}
public:
vector<int> findMode(TreeNode* root) {
currentCount = 0;
maxCount = 0;
previous = nullptr;
result.clear();
inorder(root);
return result;
}
};- 时间复杂度：
- 空间复杂度：不计结果数组为 ，来自递归调用栈
2026-09-11（周五）
二叉树（八）
二十四、二叉树的最近公共祖先
最近公共祖先是同时包含节点 p 和 q 的祖先中深度最大的节点；节点本身也可以是自己的祖先。
普通二叉树没有有序性，因此需要使用后序遍历自底向上收集结果：
- 当前节点为空，或等于
p、q时，直接返回当前节点。 - 左右子树均返回非空节点时，说明
p和q分布在当前节点两侧，当前节点就是最近公共祖先。 - 只有一侧返回非空节点时，将该结果继续向上传递。
- 两侧均为空时，返回
nullptr。
cpp
class Solution {
public:
TreeNode* lowestCommonAncestor(
TreeNode* root,
TreeNode* p,
TreeNode* q
) {
if (root == nullptr || root == p || root == q) {
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != nullptr && right != nullptr) {
return root;
}
return left != nullptr ? left : right;
}
};class Solution {
public:
TreeNode* lowestCommonAncestor(
TreeNode* root,
TreeNode* p,
TreeNode* q
) {
if (root == nullptr || root == p || root == q) {
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != nullptr && right != nullptr) {
return root;
}
return left != nullptr ? left : right;
}
};示例
查找节点 6 和 5 时，左右子树分别向节点 7 返回结果，因此节点 7 是最近公共祖先。
- 时间复杂度：
- 空间复杂度：，来自递归调用栈；最坏情况下为
二十五、二叉搜索树的最近公共祖先
二叉搜索树具有有序性，可以从根节点向下直接确定搜索方向：
- 当前值同时大于
p和q的值：最近公共祖先位于左子树。 - 当前值同时小于
p和q的值：最近公共祖先位于右子树。 - 当前值位于二者值域之间，或等于其中一个节点：当前节点就是最近公共祖先。
这里的“值域之间”与 p、q 的大小顺序无关，判断两者是否位于当前节点同一侧即可。
cpp
class Solution {
public:
TreeNode* lowestCommonAncestor(
TreeNode* root,
TreeNode* p,
TreeNode* q
) {
if (root == nullptr) {
return nullptr;
}
if (root->val > p->val && root->val > q->val) {
return lowestCommonAncestor(root->left, p, q);
}
if (root->val < p->val && root->val < q->val) {
return lowestCommonAncestor(root->right, p, q);
}
return root;
}
};class Solution {
public:
TreeNode* lowestCommonAncestor(
TreeNode* root,
TreeNode* p,
TreeNode* q
) {
if (root == nullptr) {
return nullptr;
}
if (root->val > p->val && root->val > q->val) {
return lowestCommonAncestor(root->left, p, q);
}
if (root->val < p->val && root->val < q->val) {
return lowestCommonAncestor(root->right, p, q);
}
return root;
}
};- 时间复杂度：；平衡时为 ，最坏情况下为
- 空间复杂度：，来自递归调用栈
二十六、二叉搜索树中的插入操作
利用二叉搜索树的有序性向下查找：插入值较小时进入左子树，较大时进入右子树；遇到空位置后创建新节点并连接到父节点即可。
方法一：递归插入
递归函数返回当前子树的根节点，使新节点能够通过返回值连接到原树中。
cpp
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int value) {
if (root == nullptr) {
return new TreeNode(value);
}
if (value < root->val) {
root->left = insertIntoBST(root->left, value);
} else {
root->right = insertIntoBST(root->right, value);
}
return root;
}
};class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int value) {
if (root == nullptr) {
return new TreeNode(value);
}
if (value < root->val) {
root->left = insertIntoBST(root->left, value);
} else {
root->right = insertIntoBST(root->right, value);
}
return root;
}
};方法二：迭代插入
迭代时必须保存 parent。当 current 走到空位置后，需要通过父节点完成新节点的连接。
cpp
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int value) {
if (root == nullptr) {
return new TreeNode(value);
}
TreeNode* current = root;
TreeNode* parent = nullptr;
while (current != nullptr) {
parent = current;
if (value < current->val) {
current = current->left;
} else {
current = current->right;
}
}
if (value < parent->val) {
parent->left = new TreeNode(value);
} else {
parent->right = new TreeNode(value);
}
return root;
}
};class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int value) {
if (root == nullptr) {
return new TreeNode(value);
}
TreeNode* current = root;
TreeNode* parent = nullptr;
while (current != nullptr) {
parent = current;
if (value < current->val) {
current = current->left;
} else {
current = current->right;
}
}
if (value < parent->val) {
parent->left = new TreeNode(value);
} else {
parent->right = new TreeNode(value);
}
return root;
}
};- 时间复杂度：；平衡时为 ，最坏情况下为
- 空间复杂度：递归法为 ，迭代法为
2026-09-12（周六）
二叉树（九）
二十七、删除二叉搜索树中的节点
先利用二叉搜索树的有序性定位目标节点，再根据孩子数量调整结构：
- 没有找到目标：遍历到空节点，直接返回
nullptr。 - 目标是叶子节点：删除后返回
nullptr。 - 目标只有右孩子：删除目标，让右孩子补位。
- 目标只有左孩子：删除目标，让左孩子补位。
- 目标有两个孩子：找到右子树最左侧节点，将原左子树连接到它的左侧，再让原右孩子补位。
代码中“叶子节点”可以合并到“左孩子为空”的分支，因为此时右孩子也可能是 nullptr。
cpp
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) {
return nullptr;
}
if (key < root->val) {
root->left = deleteNode(root->left, key);
return root;
}
if (key > root->val) {
root->right = deleteNode(root->right, key);
return root;
}
if (root->left == nullptr) {
TreeNode* newRoot = root->right;
delete root;
return newRoot;
}
if (root->right == nullptr) {
TreeNode* newRoot = root->left;
delete root;
return newRoot;
}
TreeNode* successor = root->right;
while (successor->left != nullptr) {
successor = successor->left;
}
successor->left = root->left;
TreeNode* newRoot = root->right;
delete root;
return newRoot;
}
};class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) {
return nullptr;
}
if (key < root->val) {
root->left = deleteNode(root->left, key);
return root;
}
if (key > root->val) {
root->right = deleteNode(root->right, key);
return root;
}
if (root->left == nullptr) {
TreeNode* newRoot = root->right;
delete root;
return newRoot;
}
if (root->right == nullptr) {
TreeNode* newRoot = root->left;
delete root;
return newRoot;
}
TreeNode* successor = root->right;
while (successor->left != nullptr) {
successor = successor->left;
}
successor->left = root->left;
TreeNode* newRoot = root->right;
delete root;
return newRoot;
}
};返回值的作用
递归函数返回删除后子树的新根节点，父节点必须重新接收该指针，否则删除根节点或孩子补位后，树的连接关系会丢失。
- 时间复杂度：；平衡时为 ，最坏情况下为
- 空间复杂度：，来自递归调用栈
二十八、修剪二叉搜索树
题目：669. 修剪二叉搜索树
目标是只保留值位于闭区间 [low, high] 内的节点。利用二叉搜索树的有序性，可以直接舍弃整侧子树：
root->val < low：左子树中的值全部更小，只需继续修剪右子树。root->val > high：右子树中的值全部更大，只需继续修剪左子树。- 当前值在区间内：分别修剪左右子树，并重新连接返回结果。
cpp
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) {
return nullptr;
}
if (root->val < low) {
return trimBST(root->right, low, high);
}
if (root->val > high) {
return trimBST(root->left, low, high);
}
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}
};class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) {
return nullptr;
}
if (root->val < low) {
return trimBST(root->right, low, high);
}
if (root->val > high) {
return trimBST(root->left, low, high);
}
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}
};- 时间复杂度：最坏为
- 空间复杂度：，来自递归调用栈；最坏情况下为
二十九、将有序数组转换为二叉搜索树
有序数组的中间元素可以作为当前根节点：左侧区间递归构造左子树，右侧区间递归构造右子树。持续选择中点能够使左右子树规模尽量接近，从而得到高度平衡的二叉搜索树。
下面统一使用左闭右开区间 [left, right)：
cpp
class Solution {
private:
TreeNode* build(const vector<int>& nums, int left, int right) {
if (left >= right) {
return nullptr;
}
int middle = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[middle]);
root->left = build(nums, left, middle);
root->right = build(nums, middle + 1, right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, static_cast<int>(nums.size()));
}
};class Solution {
private:
TreeNode* build(const vector<int>& nums, int left, int right) {
if (left >= right) {
return nullptr;
}
int middle = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[middle]);
root->left = build(nums, left, middle);
root->right = build(nums, middle + 1, right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, static_cast<int>(nums.size()));
}
};- 时间复杂度：
- 空间复杂度：，来自平衡树的递归调用栈；不计结果树本身
三十、把二叉搜索树转换为累加树
普通中序遍历“左 → 中 → 右”会得到升序序列。为了从大到小累加节点值，应使用反中序遍历“右 → 中 → 左”：
- 先处理值更大的右子树。
- 将当前节点值加入累计和，并用累计和更新当前节点。
- 最后处理值更小的左子树。
cpp
class Solution {
private:
int runningSum = 0;
void convert(TreeNode* node) {
if (node == nullptr) {
return;
}
convert(node->right);
runningSum += node->val;
node->val = runningSum;
convert(node->left);
}
public:
TreeNode* convertBST(TreeNode* root) {
runningSum = 0;
convert(root);
return root;
}
};class Solution {
private:
int runningSum = 0;
void convert(TreeNode* node) {
if (node == nullptr) {
return;
}
convert(node->right);
runningSum += node->val;
node->val = runningSum;
convert(node->left);
}
public:
TreeNode* convertBST(TreeNode* root) {
runningSum = 0;
convert(root);
return root;
}
};- 时间复杂度：
- 空间复杂度：，来自递归调用栈；最坏情况下为
三十一、二叉树总结
二叉树题目的关键，是先判断信息应该自顶向下传递，还是自底向上汇总，以及能否利用二叉搜索树的有序性剪枝。
| 问题类型 | 常用方法 | 核心原因 |
|---|---|---|
| 构造或先处理当前节点 | 前序遍历、分治 | 先确定根节点，再构造或处理左右子树 |
| 高度、平衡、公共祖先等子树属性 | 后序遍历 | 先获得左右子树结果，再计算当前节点 |
| 根到叶路径、深度记录 | 前序遍历与回溯 | 自顶向下维护路径或状态 |
| 按层处理节点 | 层序遍历（BFS） | 队列能够划分不同层级 |
| BST 的排序、差值、频率问题 | 中序或反中序遍历 | 充分利用有序序列性质 |
| BST 的搜索、插入、删除和修剪 | 比较节点值并剪枝 | 每次只需进入可能包含答案的一侧 |
选择遍历方式
- 构造类问题：通常先创建当前根节点，再递归构造子树。
- 普通二叉树属性问题：若依赖左右子树返回值，优先考虑后序遍历。
- 路径类问题：优先考虑前序遍历，并判断是否需要回溯。
- 二叉搜索树问题：先思考能否利用中序有序性或大小关系剪枝。
2026-09-15（周二）
回溯算法（一）
一、回溯算法理论基础
回溯通常与递归相伴：递归进入下一层负责继续尝试，递归返回上一层则完成状态撤销。回溯法本质上是穷举，因此通常不是高效算法，但可以通过剪枝减少无效搜索。
回溯算法常用于解决以下问题：
- 组合问题：从 个数中按规则选出 个数的集合。
- 切割问题：按照一定规则切割字符串。
- 子集问题：找出集合中满足条件的所有子集。
- 排列问题：按照一定规则生成全排列。
- 棋盘问题：例如 N 皇后、解数独等。
回溯问题通常可以抽象成一棵树：
- 集合的大小决定搜索树的宽度。
- 递归的深度决定搜索树的深度。
for循环负责横向遍历当前层的候选项。backtracking递归负责纵向进入下一层。
二、组合
题目：77. 组合
每次从集合中选择一个元素后，下一层可选择的范围都要相应收缩。对于 中选取 个数的问题， 决定搜索树的宽度， 决定搜索树的深度；当路径长度达到 时，就找到了一组答案。
使用 startIndex 记录下一层搜索的起始位置，可以避免重复选择以及产生不同顺序的相同组合。
cpp
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= n; i++) {
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
result.clear();
path.clear();
backtracking(n, k, 1);
return result;
}
};class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex; i <= n; i++) {
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
result.clear();
path.clear();
backtracking(n, k, 1);
return result;
}
};- 时间复杂度：，复制每个组合需要 时间
- 空间复杂度：，不计结果数组
三、组合剪枝优化
回溯虽然属于暴力搜索，但可以调整每层 for 循环的结束位置进行剪枝：如果从当前位置开始，剩余元素数量已经不足以补齐组合，就没有必要继续搜索。
设当前准备选择元素 i：
- 已选择的元素个数为
path.size()。 - 还需要选择
k - path.size()个元素。 - 从
i到n共有n - i + 1个元素。
要保证剩余元素足够，需要满足：
整理后得到循环上界：
其中 +1 是因为区间包含起始位置 i。例如 、，且当前尚未选择元素时，第一层最多从 开始；如果从 开始，剩余元素已经不足三个。
cpp
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex;
i <= n - (k - static_cast<int>(path.size())) + 1;
i++) {
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
result.clear();
path.clear();
backtracking(n, k, 1);
return result;
}
};class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(int n, int k, int startIndex) {
if (path.size() == k) {
result.push_back(path);
return;
}
for (int i = startIndex;
i <= n - (k - static_cast<int>(path.size())) + 1;
i++) {
path.push_back(i);
backtracking(n, k, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
result.clear();
path.clear();
backtracking(n, k, 1);
return result;
}
};- 时间复杂度：，剪枝减少了无效分支，但渐进上界不变
- 空间复杂度：，不计结果数组
2026-09-16（周三）
回溯算法（二）
四、组合总和 III
从数字 1 到 9 中选择 k 个互不重复的数字，使其总和等于 n。本题在普通组合的基础上增加了目标和限制。
可以同时进行两类剪枝：
- 数量剪枝：剩余数字不足以填满
k个位置时停止枚举。 - 总和剪枝：候选数字已经大于剩余目标值时，后续更大的数字也不可能满足条件。
cpp
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(int k, int remaining, int startIndex) {
if (static_cast<int>(path.size()) == k) {
if (remaining == 0) {
result.push_back(path);
}
return;
}
int needed = k - static_cast<int>(path.size());
int maxStart = 9 - needed + 1;
for (int number = startIndex; number <= maxStart; ++number) {
if (number > remaining) {
break;
}
path.push_back(number);
backtracking(k, remaining - number, number + 1);
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
result.clear();
path.clear();
backtracking(k, n, 1);
return result;
}
};class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(int k, int remaining, int startIndex) {
if (static_cast<int>(path.size()) == k) {
if (remaining == 0) {
result.push_back(path);
}
return;
}
int needed = k - static_cast<int>(path.size());
int maxStart = 9 - needed + 1;
for (int number = startIndex; number <= maxStart; ++number) {
if (number > remaining) {
break;
}
path.push_back(number);
backtracking(k, remaining - number, number + 1);
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
result.clear();
path.clear();
backtracking(k, n, 1);
return result;
}
};- 时间复杂度：上界为 ；实际搜索分支会因剪枝而减少
- 空间复杂度：不计结果集为
五、电话号码的字母组合
每一层递归处理一个数字，当前数字对应的字母就是该层的所有选择。递归深度等于数字字符串长度，因此不需要根据输入长度手写多层 for 循环。
题目输入只包含 2 到 9；映射表中仍为 0 和 1 保留空字符串，便于通过下标直接访问。
cpp
class Solution {
private:
const vector<string> letterMap = {
"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"
};
vector<string> result;
string path;
void backtracking(const string& digits, int index) {
if (index == static_cast<int>(digits.size())) {
result.push_back(path);
return;
}
int digit = digits[index] - '0';
for (char letter : letterMap[digit]) {
path.push_back(letter);
backtracking(digits, index + 1);
path.pop_back();
}
}
public:
vector<string> letterCombinations(string digits) {
result.clear();
path.clear();
if (digits.empty()) {
return result;
}
backtracking(digits, 0);
return result;
}
};class Solution {
private:
const vector<string> letterMap = {
"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"
};
vector<string> result;
string path;
void backtracking(const string& digits, int index) {
if (index == static_cast<int>(digits.size())) {
result.push_back(path);
return;
}
int digit = digits[index] - '0';
for (char letter : letterMap[digit]) {
path.push_back(letter);
backtracking(digits, index + 1);
path.pop_back();
}
}
public:
vector<string> letterCombinations(string digits) {
result.clear();
path.clear();
if (digits.empty()) {
return result;
}
backtracking(digits, 0);
return result;
}
};- 时间复杂度：，其中 为数字个数，、 分别是映射 3 个和 4 个字母的数字数量
- 空间复杂度：不计结果集为
六、组合总和
题目：39. 组合总和
候选数组中的每个数字可以被重复选择。与前面的组合题不同，递归进入下一层时仍传入当前下标 index，而不是 index + 1。
先对数组排序后，如果当前候选值已经大于剩余目标值，后续数字只会更大，因此可以直接结束当前层循环。
cpp
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(
const vector<int>& candidates,
int remaining,
int startIndex
) {
if (remaining == 0) {
result.push_back(path);
return;
}
for (int index = startIndex;
index < static_cast<int>(candidates.size());
++index) {
int number = candidates[index];
if (number > remaining) {
break;
}
path.push_back(number);
backtracking(candidates, remaining - number, index);
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(
vector<int>& candidates,
int target
) {
result.clear();
path.clear();
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0);
return result;
}
};class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(
const vector<int>& candidates,
int remaining,
int startIndex
) {
if (remaining == 0) {
result.push_back(path);
return;
}
for (int index = startIndex;
index < static_cast<int>(candidates.size());
++index) {
int number = candidates[index];
if (number > remaining) {
break;
}
path.push_back(number);
backtracking(candidates, remaining - number, index);
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(
vector<int>& candidates,
int target
) {
result.clear();
path.clear();
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0);
return result;
}
};
startIndex的区别
- 元素只能使用一次：递归传入
index + 1。- 元素可以重复使用：递归传入
index。- 组合问题始终从
startIndex向后搜索，以避免出现顺序不同但内容相同的重复组合。
- 时间复杂度：与候选值和目标值有关，最坏情况下呈指数级
- 空间复杂度：不计结果集，递归深度最多约为
2026-09-17（周四）
回溯算法（三）
七、组合总和 II
题目：40. 组合总和 II
本题与组合总和的关键区别如下：
| 对比项 | 组合总和 | 组合总和 II |
|---|---|---|
| 候选数组 | 元素互不相同 | 可能包含重复元素 |
| 单个位置的使用次数 | 可以重复使用 | 最多使用一次 |
| 下一层起点 | index | index + 1 |
| 是否需要树层去重 | 不需要 | 需要 |
难点在于：候选数组可以包含相同数值，但结果集中不能出现重复组合。应当区分两种情况：
- 同一树层：相同数值会生成相同组合，需要跳过。
- 同一树枝：不同位置上的相同数值可以同时进入一个组合，例如
[1, 1, 6]，不能跳过。
数组排序后，相同元素会彼此相邻。条件 index > startIndex 表示当前元素不是本层的第一个选择，因此可以用下面的判断完成树层去重：
cpp
if (index > startIndex
&& candidates[index] == candidates[index - 1]) {
continue;
}if (index > startIndex
&& candidates[index] == candidates[index - 1]) {
continue;
}这与 used[index - 1] == false 判断同一树层的思路等价，但使用 startIndex 更简洁。
cpp
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(
const vector<int>& candidates,
int remaining,
int startIndex
) {
if (remaining == 0) {
result.push_back(path);
return;
}
for (int index = startIndex;
index < static_cast<int>(candidates.size());
++index) {
if (index > startIndex
&& candidates[index] == candidates[index - 1]) {
continue;
}
int number = candidates[index];
if (number > remaining) {
break;
}
path.push_back(number);
backtracking(candidates, remaining - number, index + 1);
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(
vector<int>& candidates,
int target
) {
result.clear();
path.clear();
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0);
return result;
}
};class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(
const vector<int>& candidates,
int remaining,
int startIndex
) {
if (remaining == 0) {
result.push_back(path);
return;
}
for (int index = startIndex;
index < static_cast<int>(candidates.size());
++index) {
if (index > startIndex
&& candidates[index] == candidates[index - 1]) {
continue;
}
int number = candidates[index];
if (number > remaining) {
break;
}
path.push_back(number);
backtracking(candidates, remaining - number, index + 1);
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(
vector<int>& candidates,
int target
) {
result.clear();
path.clear();
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0);
return result;
}
};- 时间复杂度：最坏约为 ，另有排序开销
- 空间复杂度：不计结果集为 ，用于递归调用栈和当前路径
Git 学习
Git 核心模型
将 Git 理解成“提交组成的链表”有助于入门，但更准确地说，Git 的提交历史是一张有向无环图（DAG）：普通提交通常有一个父提交，合并提交可以有多个父提交。
text
A ── B ── C ← main
└── D ── E ← featureA ── B ── C ← main
└── D ── E ← featureGit 的关键对象与指针：
- Blob：保存文件内容。
- Tree：保存目录结构，并指向 Blob 或其他 Tree。
- Commit：指向项目快照对应的 Tree，同时记录父提交、作者、时间和提交信息。
- Branch：指向某个提交的可移动引用；新提交产生后，当前分支会向前移动。
- Tag：通常作为指向特定提交的固定标记。
- HEAD：表示当前检出的分支或提交。
- Index / Staging Area：暂存区，即下一次提交快照的候选内容。
由于提交内容包含父提交的哈希，修改历史中的旧提交并不是“原地修改”，而是创建新的提交；其后代提交也需要重新创建，因此 rebase 等操作会改变提交 ID。
Git 常用命令
仓库、暂存与提交
| 命令 | 作用 |
|---|---|
git init | 在当前目录初始化仓库，并创建 .git 目录 |
git status | 查看工作区、暂存区和当前分支状态 |
git add <file> | 将指定文件的当前内容加入暂存区 |
git restore --staged <file> | 取消暂存，但保留工作区修改 |
git reset <file> | 传统的取消暂存写法；默认不会删除工作区修改 |
git commit -m "message" | 使用暂存区内容创建新提交 |
git log --oneline --graph --decorate --all | 以图形化精简形式查看全部分支历史 |
分支、合并与并行工作区
| 命令 | 作用 |
|---|---|
git branch | 列出本地分支 |
git branch <name> | 创建分支，但不切换 |
git switch <name> | 切换到已有分支 |
git switch -c <name> | 创建并切换分支；旧式等价写法为 git checkout -b <name> |
git checkout <revision> | 检出指定提交；检出提交哈希时通常进入 detached HEAD 状态 |
git merge <branch> | 将指定分支合并进当前分支 |
git rebase <base> | 将当前分支上的提交重新应用到新的基点上 |
git worktree add <path> <branch> | 在另一个目录同时检出并处理指定分支 |
撤销与忽略
| 命令 | 作用 |
|---|---|
git restore <file> | 丢弃指定文件尚未暂存的修改 |
git revert <commit> | 创建一个新提交，反向抵消指定提交的修改 |
.gitignore | 声明不希望 Git 跟踪的文件匹配规则 |
使用提醒
.gitignore只影响尚未被跟踪的文件；已跟踪文件需先使用git rm --cached <file>从暂存索引移除。git reset --hard和git restore <file>可能永久丢弃本地修改，执行前应先确认或备份。git rebase会重写提交历史，避免随意对已经共享的公共分支执行。
2026-09-18（周五）
九一八事变纪念日
默哀。
回溯算法（四）
八、分割回文串
题目：131. 分割回文串
切割问题可以转换为组合问题：每一层递归决定当前子串的结束位置，切下合法子串后，再从剩余字符串的起点继续切割。
以字符串 abcdef 为例：先切出 a，再到 bcdef 中寻找第二段；如果第二段切出 b，则继续到 cdef 中寻找第三段。由此形成一棵回溯搜索树。
关键点：
startIndex表示本轮待切割子串的起始位置。end枚举当前子串的结束位置，区间为[startIndex, end]。- 只有当前子串是回文串时，才能加入路径并递归处理剩余部分。
- 当
startIndex == s.size()时，切割线已经到达字符串末尾，得到一种完整方案。
cpp
class Solution {
private:
vector<vector<string>> result;
vector<string> path;
bool isPalindrome(const string& s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) {
return false;
}
++start;
--end;
}
return true;
}
void backtracking(const string& s, int startIndex) {
if (startIndex == static_cast<int>(s.size())) {
result.push_back(path);
return;
}
for (int end = startIndex;
end < static_cast<int>(s.size());
++end) {
if (!isPalindrome(s, startIndex, end)) {
continue;
}
path.push_back(s.substr(startIndex, end - startIndex + 1));
backtracking(s, end + 1);
path.pop_back();
}
}
public:
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
backtracking(s, 0);
return result;
}
};class Solution {
private:
vector<vector<string>> result;
vector<string> path;
bool isPalindrome(const string& s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) {
return false;
}
++start;
--end;
}
return true;
}
void backtracking(const string& s, int startIndex) {
if (startIndex == static_cast<int>(s.size())) {
result.push_back(path);
return;
}
for (int end = startIndex;
end < static_cast<int>(s.size());
++end) {
if (!isPalindrome(s, startIndex, end)) {
continue;
}
path.push_back(s.substr(startIndex, end - startIndex + 1));
backtracking(s, end + 1);
path.pop_back();
}
}
public:
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
backtracking(s, 0);
return result;
}
};- 时间复杂度：最坏约为 ，需要枚举切割方案并判断、复制子串
- 空间复杂度：不计结果集为 ，用于递归调用栈和当前切割路径
九、复原 IP 地址
题目：93. 复原 IP 地址
这也是切割问题：在字符串中放置三个点号，将其划分成四段，并通过回溯枚举所有可能的切割位置。
IPv4 每一段必须满足：
- 内容只能包含数字，且不能为空。
- 数值范围为 。
- 除数字
0本身外，不能以0开头。
搜索过程仍符合回溯算法通用模板：确定当前段的结束位置，验证该段，递归切割下一段，最后撤销点号。
cpp
class Solution {
private:
vector<string> result;
bool isValid(const string& s, int start, int end) {
if (start > end) {
return false;
}
if (s[start] == '0' && start != end) {
return false;
}
int number = 0;
for (int index = start; index <= end; ++index) {
if (s[index] < '0' || s[index] > '9') {
return false;
}
number = number * 10 + (s[index] - '0');
if (number > 255) {
return false;
}
}
return true;
}
void backtracking(string& s, int startIndex, int pointCount) {
// 已放置三个点号，只需检查最后一段。
if (pointCount == 3) {
if (isValid(
s,
startIndex,
static_cast<int>(s.size()) - 1
)) {
result.push_back(s);
}
return;
}
for (int end = startIndex;
end < static_cast<int>(s.size());
++end) {
if (!isValid(s, startIndex, end)) {
// 当前段继续变长也不会重新合法，可以直接剪枝。
break;
}
s.insert(s.begin() + end + 1, '.');
backtracking(s, end + 2, pointCount + 1);
s.erase(s.begin() + end + 1);
}
}
public:
vector<string> restoreIpAddresses(string s) {
result.clear();
// 四段地址，每段至少一位、至多三位。
if (s.size() < 4 || s.size() > 12) {
return result;
}
backtracking(s, 0, 0);
return result;
}
};class Solution {
private:
vector<string> result;
bool isValid(const string& s, int start, int end) {
if (start > end) {
return false;
}
if (s[start] == '0' && start != end) {
return false;
}
int number = 0;
for (int index = start; index <= end; ++index) {
if (s[index] < '0' || s[index] > '9') {
return false;
}
number = number * 10 + (s[index] - '0');
if (number > 255) {
return false;
}
}
return true;
}
void backtracking(string& s, int startIndex, int pointCount) {
// 已放置三个点号，只需检查最后一段。
if (pointCount == 3) {
if (isValid(
s,
startIndex,
static_cast<int>(s.size()) - 1
)) {
result.push_back(s);
}
return;
}
for (int end = startIndex;
end < static_cast<int>(s.size());
++end) {
if (!isValid(s, startIndex, end)) {
// 当前段继续变长也不会重新合法，可以直接剪枝。
break;
}
s.insert(s.begin() + end + 1, '.');
backtracking(s, end + 2, pointCount + 1);
s.erase(s.begin() + end + 1);
}
}
public:
vector<string> restoreIpAddresses(string s) {
result.clear();
// 四段地址，每段至少一位、至多三位。
if (s.size() < 4 || s.size() > 12) {
return result;
}
backtracking(s, 0, 0);
return result;
}
};剪枝思路
- 输入长度小于
4或大于12时，不可能组成合法 IPv4 地址。- 每段最多三位；出现前导零或数值超过
255后，无须继续扩大当前区间。- 放置三个点号后立即验证最后一段，不再继续递归。
- 搜索规模：前三段各自最多尝试三种长度，切割位置的组合数量有限
- 空间复杂度：递归深度最多为 ；代码直接在原字符串中插入和删除点号
2026-09-20（周日）
回溯算法（五）
三类问题的结果收集位置不同：
| 问题类型 | 收集位置 | 原因 |
|---|---|---|
| 组合、切割 | 通常收集满足终止条件的节点 | 只有完整路径才是合法答案 |
| 子集 | 收集搜索树上的每个节点 | 每条路径本身都是一个子集 |
| 递增子序列 | 收集长度至少为 2 的节点 | 合法路径是答案，但还要继续向下搜索 |
十、子集
题目：78. 子集
组合问题和切割问题通常收集搜索树的叶子节点，而子集问题需要收集搜索树的所有节点。因此，每次进入递归函数时都要先保存当前路径，其中也包括空集。
循环自然会在 startIndex == nums.size() 时结束，所以可以省略单独的终止条件。
cpp
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(const vector<int>& nums, int startIndex) {
// 搜索树上的每个节点都对应一个子集。
result.push_back(path);
for (int index = startIndex;
index < static_cast<int>(nums.size());
++index) {
path.push_back(nums[index]);
backtracking(nums, index + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
};class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(const vector<int>& nums, int startIndex) {
// 搜索树上的每个节点都对应一个子集。
result.push_back(path);
for (int index = startIndex;
index < static_cast<int>(nums.size());
++index) {
path.push_back(nums[index]);
backtracking(nums, index + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
};- 时间复杂度：，共有 个子集，复制每个子集最多需要
- 空间复杂度：不计结果集为 ，用于递归调用栈和当前路径
十一、子集 II
题目：90. 子集 II
输入数组可能包含重复元素，但结果集中不能出现重复子集。处理方法与组合总和 II相同：
- 先排序，使相同元素相邻。
- 同一树枝可以选择不同位置上的相同元素。
- 同一树层中，相同数值只能作为一次起点。
因为 startIndex 已经标记了当前树层，所以可以直接使用 index > startIndex 判断同层重复，不必额外维护 used 数组。
cpp
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(const vector<int>& nums, int startIndex) {
result.push_back(path);
for (int index = startIndex;
index < static_cast<int>(nums.size());
++index) {
if (index > startIndex && nums[index] == nums[index - 1]) {
continue;
}
path.push_back(nums[index]);
backtracking(nums, index + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end());
backtracking(nums, 0);
return result;
}
};class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(const vector<int>& nums, int startIndex) {
result.push_back(path);
for (int index = startIndex;
index < static_cast<int>(nums.size());
++index) {
if (index > startIndex && nums[index] == nums[index - 1]) {
continue;
}
path.push_back(nums[index]);
backtracking(nums, index + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end());
backtracking(nums, 0);
return result;
}
};- 时间复杂度：排序需要 ，搜索与结果复制最坏为
- 空间复杂度：不计结果集为
十二、递增子序列
题目：491. 非递减子序列
目标是找出所有长度至少为 2 的非递减子序列。当前路径满足长度要求时就要加入结果，但不能立即返回，因为继续向下搜索可能得到更长的合法子序列。
本题同样需要对同一树层去重，但不能先对原数组排序，否则会破坏子序列的原始顺序。因此，要在每一层使用一个局部哈希集合，记录该父节点下已经选择过的数值。
cpp
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(const vector<int>& nums, int startIndex) {
if (path.size() >= 2) {
result.push_back(path);
// 仍需继续搜索更长的非递减子序列。
}
unordered_set<int> usedOnLevel;
for (int index = startIndex;
index < static_cast<int>(nums.size());
++index) {
int number = nums[index];
bool decreases = !path.empty() && number < path.back();
bool duplicated = usedOnLevel.find(number) != usedOnLevel.end();
if (decreases || duplicated) {
continue;
}
usedOnLevel.insert(number);
path.push_back(number);
backtracking(nums, index + 1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
};class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(const vector<int>& nums, int startIndex) {
if (path.size() >= 2) {
result.push_back(path);
// 仍需继续搜索更长的非递减子序列。
}
unordered_set<int> usedOnLevel;
for (int index = startIndex;
index < static_cast<int>(nums.size());
++index) {
int number = nums[index];
bool decreases = !path.empty() && number < path.back();
bool duplicated = usedOnLevel.find(number) != usedOnLevel.end();
if (decreases || duplicated) {
continue;
}
usedOnLevel.insert(number);
path.push_back(number);
backtracking(nums, index + 1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
};两种树层去重方式
- 允许排序：排序后使用
index > startIndex && nums[index] == nums[index - 1]。- 不能排序：为每一层建立局部集合，记录该层已经使用过的数值。
- 时间复杂度：最坏约为 ，结果数量本身可能达到指数级
- 空间复杂度：不计结果集，递归路径为 ；各层局部集合同时存在时最坏可达
2026-09-21（周一）
回溯算法（六）
十三、全排列
题目：46. 全排列
排列是有顺序的，[1, 2] 和 [2, 1] 是两个不同结果。这与组合、子集问题的主要区别是：
| 对比项 | 组合、子集 | 排列 |
|---|---|---|
| 是否考虑顺序 | 否 | 是 |
| 每层搜索起点 | 从 startIndex 开始 | 每次都从下标 0 开始 |
| 防止元素重复使用 | 依靠下标向后推进 | 使用 used 数组记录当前路径 |
当路径长度等于数组长度时，说明所有元素都已经使用，得到一个完整排列。
cpp
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(
const vector<int>& nums,
vector<bool>& used
) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int index = 0;
index < static_cast<int>(nums.size());
++index) {
if (used[index]) {
continue;
}
used[index] = true;
path.push_back(nums[index]);
backtracking(nums, used);
path.pop_back();
used[index] = false;
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
result.clear();
path.clear();
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(
const vector<int>& nums,
vector<bool>& used
) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int index = 0;
index < static_cast<int>(nums.size());
++index) {
if (used[index]) {
continue;
}
used[index] = true;
path.push_back(nums[index]);
backtracking(nums, used);
path.pop_back();
used[index] = false;
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
result.clear();
path.clear();
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};- 时间复杂度：，共有 个排列，复制每个结果需要
- 空间复杂度：不计结果集为 ，用于递归调用栈、路径和
used数组
十四、全排列 II
题目：47. 全排列 II
输入数组可能包含重复元素，但结果中不能出现重复排列。需要先排序，使相同元素相邻，再同时处理两种情况：
used[index] == true：当前元素已经出现在本条路径中，不能再次使用。nums[index] == nums[index - 1] && used[index - 1] == false：前一个相同元素没有出现在当前路径中，说明它已经在同一树层被使用，需要跳过当前元素。
cpp
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(
const vector<int>& nums,
vector<bool>& used
) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int index = 0;
index < static_cast<int>(nums.size());
++index) {
if (used[index]) {
continue;
}
// 同一树层中，相同数值只能作为一次选择。
if (index > 0 &&
nums[index] == nums[index - 1] &&
!used[index - 1]) {
continue;
}
used[index] = true;
path.push_back(nums[index]);
backtracking(nums, used);
path.pop_back();
used[index] = false;
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end());
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(
const vector<int>& nums,
vector<bool>& used
) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int index = 0;
index < static_cast<int>(nums.size());
++index) {
if (used[index]) {
continue;
}
// 同一树层中，相同数值只能作为一次选择。
if (index > 0 &&
nums[index] == nums[index - 1] &&
!used[index - 1]) {
continue;
}
used[index] = true;
path.push_back(nums[index]);
backtracking(nums, used);
path.pop_back();
used[index] = false;
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end());
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};排列问题中的树层去重
排列每层都从下标
0开始，不能像组合问题一样使用index > startIndex。此时要结合排序后的相邻元素和used[index - 1]，区分“同一树层”与“同一树枝”。
- 时间复杂度：排序为 ，搜索最坏为
- 空间复杂度：不计结果集为
十五、N 皇后
题目：51. N 皇后
皇后之间必须满足：
- 不能位于同一行。
- 不能位于同一列。
- 不能位于同一条斜线上。
递归的每一层只处理棋盘的一行，因此天然保证不会同行。随后枚举当前行的所有列，并检查正上方、左上方和右上方是否已有皇后。因为下方各行还未处理，无须向下检查。
cpp
class Solution {
private:
vector<vector<string>> result;
bool isValid(
int row,
int col,
const vector<string>& chessboard,
int boardSize
) {
// 检查同一列。
for (int currentRow = 0; currentRow < row; ++currentRow) {
if (chessboard[currentRow][col] == 'Q') {
return false;
}
}
// 检查左上方斜线。
for (int currentRow = row - 1, currentCol = col - 1;
currentRow >= 0 && currentCol >= 0;
--currentRow, --currentCol) {
if (chessboard[currentRow][currentCol] == 'Q') {
return false;
}
}
// 检查右上方斜线。
for (int currentRow = row - 1, currentCol = col + 1;
currentRow >= 0 && currentCol < boardSize;
--currentRow, ++currentCol) {
if (chessboard[currentRow][currentCol] == 'Q') {
return false;
}
}
return true;
}
void backtracking(
int boardSize,
int row,
vector<string>& chessboard
) {
if (row == boardSize) {
result.push_back(chessboard);
return;
}
for (int col = 0; col < boardSize; ++col) {
if (!isValid(row, col, chessboard, boardSize)) {
continue;
}
chessboard[row][col] = 'Q';
backtracking(boardSize, row + 1, chessboard);
chessboard[row][col] = '.';
}
}
public:
vector<vector<string>> solveNQueens(int n) {
result.clear();
vector<string> chessboard(n, string(n, '.'));
backtracking(n, 0, chessboard);
return result;
}
};class Solution {
private:
vector<vector<string>> result;
bool isValid(
int row,
int col,
const vector<string>& chessboard,
int boardSize
) {
// 检查同一列。
for (int currentRow = 0; currentRow < row; ++currentRow) {
if (chessboard[currentRow][col] == 'Q') {
return false;
}
}
// 检查左上方斜线。
for (int currentRow = row - 1, currentCol = col - 1;
currentRow >= 0 && currentCol >= 0;
--currentRow, --currentCol) {
if (chessboard[currentRow][currentCol] == 'Q') {
return false;
}
}
// 检查右上方斜线。
for (int currentRow = row - 1, currentCol = col + 1;
currentRow >= 0 && currentCol < boardSize;
--currentRow, ++currentCol) {
if (chessboard[currentRow][currentCol] == 'Q') {
return false;
}
}
return true;
}
void backtracking(
int boardSize,
int row,
vector<string>& chessboard
) {
if (row == boardSize) {
result.push_back(chessboard);
return;
}
for (int col = 0; col < boardSize; ++col) {
if (!isValid(row, col, chessboard, boardSize)) {
continue;
}
chessboard[row][col] = 'Q';
backtracking(boardSize, row + 1, chessboard);
chessboard[row][col] = '.';
}
}
public:
vector<vector<string>> solveNQueens(int n) {
result.clear();
vector<string> chessboard(n, string(n, '.'));
backtracking(n, 0, chessboard);
return result;
}
};搜索与剪枝
每一层表示一行，每个分支表示在该行选择一列。只有位置满足列与两条斜线约束时才继续递归，这相当于在搜索过程中提前剪去不可能产生答案的分支。
- 时间复杂度：搜索树规模通常估计为 ；当前实现每次合法性检查还需要 ，因此可估计为 ，不计结果复制
- 空间复杂度：不计结果集，棋盘占用 ，递归调用栈占用
2026-09-22（周二）
回溯算法（七）
十六、解数独
题目：37. 解数独
解数独与N 皇后都属于棋盘搜索问题，但二者的搜索结构不同：
| 对比项 | N 皇后 | 解数独 |
|---|---|---|
| 每层处理对象 | 一整行 | 一个空格 |
| 当前节点的选择 | 在某一列放置皇后 | 尝试数字 1 到 9 |
| 约束 | 列与两条斜线 | 行、列与九宫格 |
| 搜索目标 | 收集全部合法棋盘 | 找到一个解后立即结束 |
数独的每个空格都必须填入数字，因此搜索树通常比 N 皇后更宽、更深。递归时找到第一个空格，依次尝试 1 到 9；若某个数字满足约束，就继续填写下一个空格。
这里让回溯函数返回 bool：找到完整解时逐层返回 true，从而立即停止搜索。
cpp
class Solution {
private:
bool isValid(
int row,
int col,
char value,
const vector<vector<char>>& board
) {
// 检查同一行和同一列。
for (int index = 0; index < 9; ++index) {
if (board[row][index] == value ||
board[index][col] == value) {
return false;
}
}
// 检查当前 3 × 3 九宫格。
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int currentRow = startRow;
currentRow < startRow + 3;
++currentRow) {
for (int currentCol = startCol;
currentCol < startCol + 3;
++currentCol) {
if (board[currentRow][currentCol] == value) {
return false;
}
}
}
return true;
}
bool backtracking(vector<vector<char>>& board) {
for (int row = 0; row < 9; ++row) {
for (int col = 0; col < 9; ++col) {
if (board[row][col] != '.') {
continue;
}
for (char value = '1'; value <= '9'; ++value) {
if (!isValid(row, col, value, board)) {
continue;
}
board[row][col] = value;
if (backtracking(board)) {
return true;
}
board[row][col] = '.';
}
// 当前空格尝试所有数字后仍无解，说明本条路径失败。
return false;
}
}
// 没有剩余空格，说明棋盘已经填写完成。
return true;
}
public:
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}
};class Solution {
private:
bool isValid(
int row,
int col,
char value,
const vector<vector<char>>& board
) {
// 检查同一行和同一列。
for (int index = 0; index < 9; ++index) {
if (board[row][index] == value ||
board[index][col] == value) {
return false;
}
}
// 检查当前 3 × 3 九宫格。
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int currentRow = startRow;
currentRow < startRow + 3;
++currentRow) {
for (int currentCol = startCol;
currentCol < startCol + 3;
++currentCol) {
if (board[currentRow][currentCol] == value) {
return false;
}
}
}
return true;
}
bool backtracking(vector<vector<char>>& board) {
for (int row = 0; row < 9; ++row) {
for (int col = 0; col < 9; ++col) {
if (board[row][col] != '.') {
continue;
}
for (char value = '1'; value <= '9'; ++value) {
if (!isValid(row, col, value, board)) {
continue;
}
board[row][col] = value;
if (backtracking(board)) {
return true;
}
board[row][col] = '.';
}
// 当前空格尝试所有数字后仍无解，说明本条路径失败。
return false;
}
}
// 没有剩余空格，说明棋盘已经填写完成。
return true;
}
public:
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}
};
return false的位置只有当前空格的
1到9全部尝试失败后，才能返回false。如果把它放进数字循环内部，就会在第一个候选数字失败时过早终止。
- 时间复杂度：设空格数量为 ，粗略上界为 ；行、列和九宫格约束会剪去大量分支
- 空间复杂度：棋盘原地修改，不计棋盘本身时，递归调用栈最坏为
十七、回溯算法总结
回溯可以理解为在搜索树上进行深度优先遍历：做出选择、进入下一层、撤销选择，再尝试其他分支。
常见问题类型：
| 类型 | 目标 | 典型状态或技巧 | 示例 |
|---|---|---|---|
| 组合 | 从若干元素中按规则选择一组 | startIndex、剪枝、树层去重 | 组合 |
| 切割 | 枚举字符串的分割位置 | 起止下标、子串合法性判断 | 分割回文串 |
| 子集 | 收集满足条件的所有子集 | 收集搜索树上的节点 | 子集 |
| 排列 | 枚举考虑顺序的所有方案 | used 数组、树层去重 | 全排列 |
| 棋盘 | 在二维空间中逐步放置元素 | 位置合法性检查、提前剪枝 | N 皇后、解数独 |
通用模板：
text
void backtracking(路径, 选择范围) {
if (满足终止条件) {
保存结果;
return;
}
for (选择 : 当前层的可选集合) {
if (选择不合法) {
continue;
}
做出选择;
backtracking(更新后的路径, 更新后的选择范围);
撤销选择;
}
}void backtracking(路径, 选择范围) {
if (满足终止条件) {
保存结果;
return;
}
for (选择 : 当前层的可选集合) {
if (选择不合法) {
continue;
}
做出选择;
backtracking(更新后的路径, 更新后的选择范围);
撤销选择;
}
}分析回溯问题时，依次确认：
- 路径是什么：已经做出的选择如何保存？
- 每层有哪些选择：循环范围是什么，是否需要
startIndex或used？ - 何时收集结果：收集叶子节点、所有节点，还是部分合法节点？
- 终止条件是什么：路径长度、剩余目标值、字符串末尾或棋盘填满？
- 如何剪枝与去重：哪些分支一定无解，重复发生在树层还是树枝？
- 如何撤销选择：递归返回后，需要恢复哪些路径、标记或棋盘状态？
核心
回溯的本质不是记忆不同题目的代码，而是明确搜索树的节点状态、选择集合、终止条件、结果收集位置、剪枝规则和撤销操作。
2026-09-25（周五）
近况
这几天去云南比赛啦，偷个小懒；趁今天下午没事，抓紧学一会儿。
贪心算法（一）
一、贪心算法理论基础
贪心算法的核心是：在每个阶段选择当前看来最优的方案，并证明这些局部最优选择最终能够构成全局最优解。
真正的难点不在代码，而在于回答两个问题：
- 当前阶段的“局部最优”是什么？
- 为什么采用这个局部最优后，不会错过全局最优解？
常见分析步骤：
- 明确问题的全局目标。
- 找出每个阶段可执行的选择。
- 提出局部最优的贪心策略。
- 证明该选择具有安全性，不会排除全局最优解。
- 重复选择并组合得到最终答案。
常见证明思路包括：
- 交换论证：证明任意最优解都可以替换为当前贪心选择，而不会变差。
- 归纳法：证明完成一次贪心选择后，剩余问题仍具有相同结构。
- 领先法 / 不变式：证明贪心方案在每一步都不会落后于其他可行方案。
举不出反例不等于证明正确
尝试构造反例可以快速否定错误的贪心策略，但“暂时找不到反例”不能证明策略一定正确。最终仍需要交换论证、归纳或不变式等理由说明局部最优能够推出全局最优。若当前决策会影响后续状态，通常还要考虑动态规划。
二、分发饼干
题目：455. 分发饼干
先将孩子胃口和饼干尺寸分别排序，可以从两个方向理解贪心策略：
| 方向 | 局部最优 | 实现方式 |
|---|---|---|
| 从大到小 | 用最大的饼干优先满足胃口最大的孩子 | 遍历孩子，维护最大饼干下标 |
| 从小到大 | 用能满足当前孩子的最小饼干，保留大饼干 | 遍历饼干，维护最小胃口下标 |
两种策略都能避免资源浪费，从而使被满足的孩子数量最大。
写法一：大饼干优先满足大胃口
cpp
class Solution {
public:
int findContentChildren(
vector<int>& greed,
vector<int>& cookies
) {
sort(greed.begin(), greed.end());
sort(cookies.begin(), cookies.end());
int cookieIndex = static_cast<int>(cookies.size()) - 1;
int result = 0;
for (int childIndex = static_cast<int>(greed.size()) - 1;
childIndex >= 0;
--childIndex) {
if (cookieIndex >= 0 &&
cookies[cookieIndex] >= greed[childIndex]) {
++result;
--cookieIndex;
}
}
return result;
}
};class Solution {
public:
int findContentChildren(
vector<int>& greed,
vector<int>& cookies
) {
sort(greed.begin(), greed.end());
sort(cookies.begin(), cookies.end());
int cookieIndex = static_cast<int>(cookies.size()) - 1;
int result = 0;
for (int childIndex = static_cast<int>(greed.size()) - 1;
childIndex >= 0;
--childIndex) {
if (cookieIndex >= 0 &&
cookies[cookieIndex] >= greed[childIndex]) {
++result;
--cookieIndex;
}
}
return result;
}
};写法二：小饼干优先满足小胃口
cpp
class Solution {
public:
int findContentChildren(
vector<int>& greed,
vector<int>& cookies
) {
sort(greed.begin(), greed.end());
sort(cookies.begin(), cookies.end());
int childIndex = 0;
for (int cookie : cookies) {
if (childIndex < static_cast<int>(greed.size()) &&
cookie >= greed[childIndex]) {
++childIndex;
}
}
return childIndex;
}
};class Solution {
public:
int findContentChildren(
vector<int>& greed,
vector<int>& cookies
) {
sort(greed.begin(), greed.end());
sort(cookies.begin(), cookies.end());
int childIndex = 0;
for (int cookie : cookies) {
if (childIndex < static_cast<int>(greed.size()) &&
cookie >= greed[childIndex]) {
++childIndex;
}
}
return childIndex;
}
};- 时间复杂度：，主要开销来自两次排序
- 空间复杂度：除排序所需空间外为
三、摆动序列
题目：376. 摆动序列
在一段连续上升或连续下降的坡度中，中间节点不会增加摆动次数，可以只保留坡度两端的极值点。
- 局部最优：删除单调坡度中的中间节点，只保留峰值和谷值。
- 全局最优：保留尽可能多的局部极值，得到最长摆动子序列。
实现时记录前一个有效坡度 previousDifference。只有当前坡度与前一个有效坡度方向相反时，才出现新的峰值或谷值，并更新前一个坡度。
cpp
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.empty()) {
return 0;
}
int previousDifference = 0;
int result = 1;
for (int index = 0;
index + 1 < static_cast<int>(nums.size());
++index) {
int currentDifference = nums[index + 1] - nums[index];
bool changesToUp =
previousDifference <= 0 && currentDifference > 0;
bool changesToDown =
previousDifference >= 0 && currentDifference < 0;
if (changesToUp || changesToDown) {
++result;
// 只在出现有效摆动时更新，忽略平坡和同向坡度。
previousDifference = currentDifference;
}
}
return result;
}
};class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.empty()) {
return 0;
}
int previousDifference = 0;
int result = 1;
for (int index = 0;
index + 1 < static_cast<int>(nums.size());
++index) {
int currentDifference = nums[index + 1] - nums[index];
bool changesToUp =
previousDifference <= 0 && currentDifference > 0;
bool changesToDown =
previousDifference >= 0 && currentDifference < 0;
if (changesToUp || changesToDown) {
++result;
// 只在出现有效摆动时更新，忽略平坡和同向坡度。
previousDifference = currentDifference;
}
}
return result;
}
};为什么只在摆动时更新
previousDifference连续同向坡度中只需要保留最远端的极值。如果每一步都更新前一个有效坡度，遇到相等元素或平台时容易破坏对峰值、谷值的判断。
- 时间复杂度：
- 空间复杂度：
2026-10-01（周四）
贪心算法（二）
四、买卖股票的最佳时机 II
本题允许完成多笔交易，关键是把一段交易利润拆成相邻两天的价格差。
例如，第 0 天买入、第 3 天卖出的利润为：
因此，无须真正记录买入和卖出的区间，只需累加所有正的相邻日利润：
- 局部最优：只收集
prices[i] - prices[i - 1] > 0的利润。 - 全局最优：所有正利润相加，得到可实现的最大总利润。
cpp
class Solution {
public:
int maxProfit(vector<int>& prices) {
int totalProfit = 0;
for (int day = 1;
day < static_cast<int>(prices.size());
++day) {
int dailyProfit = prices[day] - prices[day - 1];
if (dailyProfit > 0) {
totalProfit += dailyProfit;
}
}
return totalProfit;
}
};class Solution {
public:
int maxProfit(vector<int>& prices) {
int totalProfit = 0;
for (int day = 1;
day < static_cast<int>(prices.size());
++day) {
int dailyProfit = prices[day] - prices[day - 1];
if (dailyProfit > 0) {
totalProfit += dailyProfit;
}
}
return totalProfit;
}
};适用前提
这种“累加所有正差值”的方法依赖于本题允许多次交易。若交易次数、手续费或冷冻期受到限制，就不能直接套用该结论。
- 时间复杂度：
- 空间复杂度：
2026-10-02（周五）
贪心算法（三）
五、跳跃游戏
题目：55. 跳跃游戏
本题无须确定每一步具体跳到哪里，只需维护从已知可达位置出发，能够覆盖到的最远下标 farthest。
遍历过程中，当前位置必须满足 index <= farthest，否则当前位置本身不可达，也就无法继续扩展覆盖范围。对于每个可达位置，使用以下公式更新覆盖范围：
cpp
farthest = max(farthest, index + nums[index]);farthest = max(farthest, index + nums[index]);- 局部最优：不断扩大当前能够到达的最远位置。
- 全局目标：判断最大覆盖范围能否到达数组末尾。
cpp
class Solution {
public:
bool canJump(vector<int>& nums) {
if (nums.empty()) {
return false;
}
int farthest = 0;
int lastIndex = static_cast<int>(nums.size()) - 1;
for (int index = 0;
index <= farthest && index <= lastIndex;
++index) {
farthest = max(farthest, index + nums[index]);
if (farthest >= lastIndex) {
return true;
}
}
return false;
}
};class Solution {
public:
bool canJump(vector<int>& nums) {
if (nums.empty()) {
return false;
}
int farthest = 0;
int lastIndex = static_cast<int>(nums.size()) - 1;
for (int index = 0;
index <= farthest && index <= lastIndex;
++index) {
farthest = max(farthest, index + nums[index]);
if (farthest >= lastIndex) {
return true;
}
}
return false;
}
};不是“每次都跳最远”
算法并没有真的决定某一步落在哪里，而是合并所有已知可达位置能够产生的覆盖范围。只要终点进入覆盖范围，就一定存在一条可达路径。
- 时间复杂度：
- 空间复杂度：
六、跳跃游戏 II
题目：45. 跳跃游戏 II
在保证一定能够到达终点的前提下，需要求最少跳跃次数。遍历时维护两个边界：
| 状态 | 含义 |
|---|---|
currentEnd | 使用当前跳跃次数能够覆盖的最远位置 |
nextEnd | 在当前覆盖区间内再跳一步，能够到达的最远位置 |
在到达 currentEnd 之前，持续更新 nextEnd。当遍历到当前边界时，说明必须再跳一步，并将当前边界更新为 nextEnd。这相当于按层遍历隐式图：每扩展一层，跳跃次数增加一次。
cpp
class Solution {
public:
int jump(vector<int>& nums) {
int jumps = 0;
int currentEnd = 0;
int nextEnd = 0;
// 到达最后一个下标后无需继续起跳。
for (int index = 0;
index + 1 < static_cast<int>(nums.size());
++index) {
nextEnd = max(nextEnd, index + nums[index]);
if (index == currentEnd) {
++jumps;
currentEnd = nextEnd;
}
}
return jumps;
}
};class Solution {
public:
int jump(vector<int>& nums) {
int jumps = 0;
int currentEnd = 0;
int nextEnd = 0;
// 到达最后一个下标后无需继续起跳。
for (int index = 0;
index + 1 < static_cast<int>(nums.size());
++index) {
nextEnd = max(nextEnd, index + nums[index]);
if (index == currentEnd) {
++jumps;
currentEnd = nextEnd;
}
}
return jumps;
}
};为什么循环不遍历最后一个位置
跳跃次数表示“从当前位置起跳”的次数。到达终点后不需要再跳，所以循环只遍历到倒数第二个下标，避免多统计一步。
- 时间复杂度：
- 空间复杂度：
2026-10-04（周日）
贪心算法（四）
七、K 次取反后最大化的数组和
为了让数组和尽可能大，需要分两阶段进行贪心选择：
- 优先反转绝对值大的负数：负数
-x变成x后，数组和增加2x，因此绝对值越大，收益越大。 - 处理剩余次数：所有负数都变为非负数后，如果
k仍为奇数，就反转绝对值最小的数，使损失最小；若k为偶数，重复反转同一个数即可相互抵消。
因此，可以先按绝对值从大到小排序。完成负数反转后，数组末尾自然是绝对值最小的元素。
cpp
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(
nums.begin(),
nums.end(),
[](int left, int right) {
return abs(left) > abs(right);
}
);
for (int& number : nums) {
if (number < 0 && k > 0) {
number = -number;
--k;
}
}
// 剩余奇数次操作时，反转绝对值最小的元素。
if (k % 2 == 1) {
nums.back() = -nums.back();
}
int result = 0;
for (int number : nums) {
result += number;
}
return result;
}
};class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(
nums.begin(),
nums.end(),
[](int left, int right) {
return abs(left) > abs(right);
}
);
for (int& number : nums) {
if (number < 0 && k > 0) {
number = -number;
--k;
}
}
// 剩余奇数次操作时，反转绝对值最小的元素。
if (k % 2 == 1) {
nums.back() = -nums.back();
}
int result = 0;
for (int number : nums) {
result += number;
}
return result;
}
};看绝对值，不是只看最小正整数
处理完负数后，剩余操作应落在绝对值最小的元素上。该元素可能是正数，也可能是
0；如果存在0，无论反转多少次都不会改变数组和。
- 时间复杂度：，主要开销来自排序
- 空间复杂度：除排序所需空间外为
八、加油站
题目：134. 加油站
令每个加油站的油量盈余为：
需要同时维护两个量：
| 状态 | 含义 | 用途 |
|---|---|---|
totalBalance | 整个环路的总油量盈余 | 判断是否存在可行起点 |
currentBalance | 从当前候选起点到当前位置的油量盈余 | 判断当前候选起点是否失败 |
贪心策略：
- 如果
totalBalance < 0，总油量小于总消耗，从任何位置出发都无法绕行一周。 - 如果从候选起点到位置
i时currentBalance < 0，说明该区间内的任意位置都不能作为起点，可以直接把候选起点移动到i + 1。 - 如果最终
totalBalance >= 0，最后保留下来的候选起点一定可行。
cpp
class Solution {
public:
int canCompleteCircuit(
vector<int>& gas,
vector<int>& cost
) {
int totalBalance = 0;
int currentBalance = 0;
int startIndex = 0;
for (int index = 0;
index < static_cast<int>(gas.size());
++index) {
int balance = gas[index] - cost[index];
totalBalance += balance;
currentBalance += balance;
if (currentBalance < 0) {
startIndex = index + 1;
currentBalance = 0;
}
}
return totalBalance >= 0 ? startIndex : -1;
}
};class Solution {
public:
int canCompleteCircuit(
vector<int>& gas,
vector<int>& cost
) {
int totalBalance = 0;
int currentBalance = 0;
int startIndex = 0;
for (int index = 0;
index < static_cast<int>(gas.size());
++index) {
int balance = gas[index] - cost[index];
totalBalance += balance;
currentBalance += balance;
if (currentBalance < 0) {
startIndex = index + 1;
currentBalance = 0;
}
}
return totalBalance >= 0 ? startIndex : -1;
}
};前缀和视角
若从下标
0开始计算前缀油量，途中从未为负，则0可以作为起点。若最低前缀为负，就需要跳过造成亏空的前缀区间；上面的“一旦区间和为负，就把起点移动到下一站”正是在一次遍历中完成这一过程。
- 时间复杂度：
- 空间复杂度：
2026-10-05（周一）
贪心算法（五）
九、分发糖果
题目：135. 分发糖果
每个孩子至少得到一颗糖果；若某个孩子的评分高于相邻孩子，那么他获得的糖果也必须更多。
左右两个方向的约束不能在一次遍历中同时确定，否则修改一侧时可能破坏另一侧已经满足的关系。可以把问题拆成两次单向贪心：
| 遍历方向 | 处理的约束 | 更新方式 |
|---|---|---|
| 从左到右 | 当前评分高于左侧 | candies[i] = candies[i - 1] + 1 |
| 从右到左 | 当前评分高于右侧 | candies[i] = max(candies[i], candies[i + 1] + 1) |
第二次遍历必须取最大值：既要满足右侧约束，也不能破坏第一次遍历已经满足的左侧约束。
cpp
class Solution {
public:
int candy(vector<int>& ratings) {
int childCount = static_cast<int>(ratings.size());
vector<int> candies(childCount, 1);
// 满足“右侧评分更高”时的左邻居约束。
for (int index = 1; index < childCount; ++index) {
if (ratings[index] > ratings[index - 1]) {
candies[index] = candies[index - 1] + 1;
}
}
// 满足“左侧评分更高”时的右邻居约束。
for (int index = childCount - 2; index >= 0; --index) {
if (ratings[index] > ratings[index + 1]) {
candies[index] = max(
candies[index],
candies[index + 1] + 1
);
}
}
int totalCandies = 0;
for (int count : candies) {
totalCandies += count;
}
return totalCandies;
}
};class Solution {
public:
int candy(vector<int>& ratings) {
int childCount = static_cast<int>(ratings.size());
vector<int> candies(childCount, 1);
// 满足“右侧评分更高”时的左邻居约束。
for (int index = 1; index < childCount; ++index) {
if (ratings[index] > ratings[index - 1]) {
candies[index] = candies[index - 1] + 1;
}
}
// 满足“左侧评分更高”时的右邻居约束。
for (int index = childCount - 2; index >= 0; --index) {
if (ratings[index] > ratings[index + 1]) {
candies[index] = max(
candies[index],
candies[index + 1] + 1
);
}
}
int totalCandies = 0;
for (int count : candies) {
totalCandies += count;
}
return totalCandies;
}
};相同评分无须额外处理
题目只要求评分更高的孩子获得更多糖果。相邻孩子评分相同时，二者的糖果数量没有大小约束。
- 时间复杂度：
- 空间复杂度：，用于保存每个孩子的糖果数量
十、柠檬水找零
题目：860. 柠檬水找零
每杯柠檬水售价为 5 美元，顾客只会支付 5、10 或 20 美元：
- 收到
5美元：无须找零，增加一张5美元。 - 收到
10美元：必须使用一张5美元找零。 - 收到
20美元：优先使用一张10美元和一张5美元；若无法这样找零，再尝试使用三张5美元。
5 美元既能为 10 美元账单找零，也能为 20 美元账单找零；10 美元只能用于 20 美元账单。因此，处理 20 美元时优先消耗一张 10 美元，可以尽量保留用途更广的 5 美元。
cpp
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int fiveDollarCount = 0;
int tenDollarCount = 0;
for (int bill : bills) {
if (bill == 5) {
++fiveDollarCount;
} else if (bill == 10) {
if (fiveDollarCount == 0) {
return false;
}
--fiveDollarCount;
++tenDollarCount;
} else {
if (tenDollarCount > 0 && fiveDollarCount > 0) {
--tenDollarCount;
--fiveDollarCount;
} else if (fiveDollarCount >= 3) {
fiveDollarCount -= 3;
} else {
return false;
}
}
}
return true;
}
};class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int fiveDollarCount = 0;
int tenDollarCount = 0;
for (int bill : bills) {
if (bill == 5) {
++fiveDollarCount;
} else if (bill == 10) {
if (fiveDollarCount == 0) {
return false;
}
--fiveDollarCount;
++tenDollarCount;
} else {
if (tenDollarCount > 0 && fiveDollarCount > 0) {
--tenDollarCount;
--fiveDollarCount;
} else if (fiveDollarCount >= 3) {
fiveDollarCount -= 3;
} else {
return false;
}
}
}
return true;
}
};无须记录
20美元后续找零只会用到
5美元和10美元，收到的20美元无法参与任何一种找零方案，因此不需要维护其数量。
- 时间复杂度：
- 空间复杂度：
2026-10-06（周二）
贪心算法（六）
十一、根据身高重建队列
每个人用 [height, k] 表示，其中 k 是排在他前面且身高大于等于 height 的人数。题目同时包含“身高”和“人数”两个维度，处理原则是：先确定一个维度，再利用已经确定的顺序处理另一个维度。
具体策略：
- 按身高从高到低排序。
- 身高相同时，按
k从小到大排序。 - 按排序后的顺序，将每个人插入结果队列的下标
k处。
处理当前人物时，队列中已经存在的人都不比他矮。因此，插入到下标 k 后，前面恰好有 k 个身高大于等于他的人；后续插入的更矮人物不会影响这一条件。
cpp
class Solution {
public:
vector<vector<int>> reconstructQueue(
vector<vector<int>>& people
) {
sort(
people.begin(),
people.end(),
[](const vector<int>& left, const vector<int>& right) {
if (left[0] == right[0]) {
return left[1] < right[1];
}
return left[0] > right[0];
}
);
vector<vector<int>> queue;
for (const vector<int>& person : people) {
queue.insert(queue.begin() + person[1], person);
}
return queue;
}
};class Solution {
public:
vector<vector<int>> reconstructQueue(
vector<vector<int>>& people
) {
sort(
people.begin(),
people.end(),
[](const vector<int>& left, const vector<int>& right) {
if (left[0] == right[0]) {
return left[1] < right[1];
}
return left[0] > right[0];
}
);
vector<vector<int>> queue;
for (const vector<int>& person : people) {
queue.insert(queue.begin() + person[1], person);
}
return queue;
}
};同身高时为什么按
k升序身高相同的人彼此都满足“大于等于当前身高”。先插入
k较小的人，才能保证后续人物可以插入到自己的合法位置，并维持已经建立的相对关系。
- 时间复杂度：排序为 ，
vector中间插入最坏为 ，整体为 - 空间复杂度：，用于保存重建后的队列
十二、用最少数量的箭引爆气球
将每个气球视为一个闭区间。若多个气球存在公共重叠区间，就可以在公共区间内射出一支箭，同时引爆这些气球。
- 局部最优：尽量让当前箭覆盖所有仍有公共交集的气球。
- 全局最优：把气球划分为尽可能少的重叠组，每组只使用一支箭。
先按左边界升序排序，再维护当前重叠组的最小右边界 overlapEnd：
- 若下一个气球的左边界大于
overlapEnd，说明与当前组没有交集，需要新增一支箭。 - 否则仍属于当前重叠组，并收紧公共区间的右边界。
cpp
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) {
return 0;
}
sort(
points.begin(),
points.end(),
[](const vector<int>& left, const vector<int>& right) {
return left[0] < right[0];
}
);
int arrowCount = 1;
int overlapEnd = points[0][1];
for (int index = 1;
index < static_cast<int>(points.size());
++index) {
if (points[index][0] > overlapEnd) {
++arrowCount;
overlapEnd = points[index][1];
} else {
overlapEnd = min(overlapEnd, points[index][1]);
}
}
return arrowCount;
}
};class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) {
return 0;
}
sort(
points.begin(),
points.end(),
[](const vector<int>& left, const vector<int>& right) {
return left[0] < right[0];
}
);
int arrowCount = 1;
int overlapEnd = points[0][1];
for (int index = 1;
index < static_cast<int>(points.size());
++index) {
if (points[index][0] > overlapEnd) {
++arrowCount;
overlapEnd = points[index][1];
} else {
overlapEnd = min(overlapEnd, points[index][1]);
}
}
return arrowCount;
}
};判断条件是
>，不是>=气球区间包含端点。当下一个气球的左边界等于当前重叠区间的右边界时，仍可以在该端点射出一支箭，同时引爆两个气球。
- 时间复杂度：，主要开销来自排序
- 空间复杂度：除排序所需空间外为
2026-10-08（周四）
贪心算法（七）
十三、无重叠区间
题目：435. 无重叠区间
问题要求移除最少数量的区间，使剩余区间互不重叠。可以转换为：保留尽可能多的非重叠区间，再用区间总数减去保留数量。
按右边界从小到大排序，每次优先保留结束最早的区间，可以为后面的区间留下更大的可选空间：
- 默认保留第一个区间，并记录其右边界
previousEnd。 - 若下一个区间的左边界大于等于
previousEnd，两者不重叠，可以保留该区间。 - 最终用区间总数减去保留数量，得到最少移除数量。
cpp
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return 0;
}
sort(
intervals.begin(),
intervals.end(),
[](const vector<int>& left, const vector<int>& right) {
return left[1] < right[1];
}
);
int keptCount = 1;
int previousEnd = intervals[0][1];
for (int index = 1;
index < static_cast<int>(intervals.size());
++index) {
if (intervals[index][0] >= previousEnd) {
++keptCount;
previousEnd = intervals[index][1];
}
}
return static_cast<int>(intervals.size()) - keptCount;
}
};class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return 0;
}
sort(
intervals.begin(),
intervals.end(),
[](const vector<int>& left, const vector<int>& right) {
return left[1] < right[1];
}
);
int keptCount = 1;
int previousEnd = intervals[0][1];
for (int index = 1;
index < static_cast<int>(intervals.size());
++index) {
if (intervals[index][0] >= previousEnd) {
++keptCount;
previousEnd = intervals[index][1];
}
}
return static_cast<int>(intervals.size()) - keptCount;
}
};为什么选择最早结束的区间
在已经按右边界排序的情况下，选择当前最早结束的区间不会减少后续可容纳的区间数量，反而为后续选择保留了最大的空间。
- 时间复杂度：，主要开销来自排序
- 空间复杂度：除排序所需空间外为
十四、划分字母区间
题目：763. 划分字母区间
目标是让同一个字母最多出现在一个片段中。分割点必须位于当前片段内所有字符最后出现位置的最远边界之后。
处理步骤：
- 统计每个字符最后出现的下标。
- 从左向右扫描字符串，不断更新当前片段的最远右边界。
- 当当前下标等于最远右边界时，说明片段中出现过的所有字符都不会在后面再次出现，可以安全分割。
cpp
class Solution {
public:
vector<int> partitionLabels(string s) {
array<int, 26> lastPosition{};
for (int index = 0;
index < static_cast<int>(s.size());
++index) {
lastPosition[s[index] - 'a'] = index;
}
vector<int> result;
int segmentStart = 0;
int segmentEnd = 0;
for (int index = 0;
index < static_cast<int>(s.size());
++index) {
segmentEnd = max(
segmentEnd,
lastPosition[s[index] - 'a']
);
if (index == segmentEnd) {
result.push_back(segmentEnd - segmentStart + 1);
segmentStart = index + 1;
}
}
return result;
}
};class Solution {
public:
vector<int> partitionLabels(string s) {
array<int, 26> lastPosition{};
for (int index = 0;
index < static_cast<int>(s.size());
++index) {
lastPosition[s[index] - 'a'] = index;
}
vector<int> result;
int segmentStart = 0;
int segmentEnd = 0;
for (int index = 0;
index < static_cast<int>(s.size());
++index) {
segmentEnd = max(
segmentEnd,
lastPosition[s[index] - 'a']
);
if (index == segmentEnd) {
result.push_back(segmentEnd - segmentStart + 1);
segmentStart = index + 1;
}
}
return result;
}
};分割点的含义
index == segmentEnd表示当前片段内所有字符的最后出现位置都没有越过此处。若提前切割，就会让某个字符同时出现在两个片段中。
- 时间复杂度：
- 空间复杂度：，字符集大小固定为
26
十五、合并区间
题目：56. 合并区间
先按左边界从小到大排序，使可能重叠的区间相邻。将第一个区间放入结果集后，依次处理后续区间：
- 若新区间的左边界小于等于结果集中最后一个区间的右边界，说明二者重叠，只需扩大右边界。
- 否则二者不重叠，将新区间直接加入结果集。
cpp
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return {};
}
sort(
intervals.begin(),
intervals.end(),
[](const vector<int>& left, const vector<int>& right) {
return left[0] < right[0];
}
);
vector<vector<int>> result;
result.push_back(intervals[0]);
for (int index = 1;
index < static_cast<int>(intervals.size());
++index) {
if (intervals[index][0] <= result.back()[1]) {
result.back()[1] = max(
result.back()[1],
intervals[index][1]
);
} else {
result.push_back(intervals[index]);
}
}
return result;
}
};class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return {};
}
sort(
intervals.begin(),
intervals.end(),
[](const vector<int>& left, const vector<int>& right) {
return left[0] < right[0];
}
);
vector<vector<int>> result;
result.push_back(intervals[0]);
for (int index = 1;
index < static_cast<int>(intervals.size());
++index) {
if (intervals[index][0] <= result.back()[1]) {
result.back()[1] = max(
result.back()[1],
intervals[index][1]
);
} else {
result.push_back(intervals[index]);
}
}
return result;
}
};三道区间题的边界判断
- 引爆气球：
nextStart > overlapEnd时才需要新箭，端点相接仍可共用一支箭。- 无重叠区间：
nextStart >= previousEnd时可以同时保留，端点相接不算重叠。- 合并区间：
nextStart <= mergedEnd时需要合并，端点相接也会合并。
- 时间复杂度：，主要开销来自排序
- 空间复杂度：不计结果集，除排序所需空间外为
Comments