力扣hot100汇总
数组专题
数组是面试中最常考的数据结构，掌握好数组的各种技巧非常重要。
1. 两数之和 (LeetCode 1)
题目：给定一个数组和目标值，找出数组中和为目标值的两个数的下标。
核心思路：用哈希表记录”我需要什么”
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map; // 值 -> 下标
for (int i = 0; i < nums.size(); i++) {
int need = target - nums[i]; // 我需要的数
if (map.count(need)) {
return {map[need], i}; // 找到了！
}
map[nums[i]] = i; // 记录当前数
}
return {};
}记忆口诀：边走边存，看看有没有我需要的。
2. 三数之和 (LeetCode 15)
题目：找出数组中所有和为0的三元组（不重复）。
核心思路：排序 + 固定一个数 + 双指针找另外两个
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end()); // 先排序
for (int i = 0; i < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i-1]) continue; // 跳过重复
int left = i + 1, right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
res.push_back({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--;
} else if (sum < 0) {
left++; // 太小了，左指针右移
} else {
right--; // 太大了，右指针左移
}
}
}
return res;
}记忆口诀：排序去重，固定一个，双指针找两个。
3. 最大子数组和 (LeetCode 53)
题目：找出数组中连续子数组的最大和。
核心思路：动态规划，当前最大和 = max(自己, 自己+前面的最大和)
int maxSubArray(vector<int>& nums) {
int maxSum = nums[0];
int curSum = nums[0];
for (int i = 1; i < nums.size(); i++) {
// 关键决策：要不要加上前面的和？
curSum = max(nums[i], curSum + nums[i]);
maxSum = max(maxSum, curSum);
}
return maxSum;
}记忆口诀：前面的和是累赘就丢掉，不是就加上。
4. 合并区间 (LeetCode 56)
题目：给出若干区间，合并所有重叠的区间。
核心思路：按起点排序，然后逐个合并
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
// 按起点排序
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
res.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
// 当前区间的起点 <= 上一个区间的终点，说明重叠
if (intervals[i][0] <= res.back()[1]) {
res.back()[1] = max(res.back()[1], intervals[i][1]); // 合并
} else {
res.push_back(intervals[i]); // 不重叠，直接加入
}
}
return res;
}记忆口诀：排序后看能不能接上，能接就合并，不能接就新开。
5. 轮转数组 (LeetCode 189)
题目：将数组向右轮转k个位置。
核心思路：三次翻转法
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n; // 处理k大于n的情况
// 三次翻转
reverse(nums.begin(), nums.end()); // 整体翻转
reverse(nums.begin(), nums.begin() + k); // 翻转前k个
reverse(nums.begin() + k, nums.end()); // 翻转后n-k个
}例子：[1,2,3,4,5,6,7] 右移3位
- 整体翻转：
[7,6,5,4,3,2,1] - 前3个翻转：
[5,6,7,4,3,2,1] - 后4个翻转：
[5,6,7,1,2,3,4]✓
记忆口诀：整体翻，前k翻，后面翻。
6. 除自身以外数组的乘积 (LeetCode 238)
题目：返回数组，其中每个元素是原数组中除了该位置外其他元素的乘积（不能用除法）。
核心思路：左边乘积 × 右边乘积
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, 1);
// 第一遍：计算左边的乘积
int left = 1;
for (int i = 0; i < n; i++) {
res[i] = left;
left *= nums[i];
}
// 第二遍：乘上右边的乘积
int right = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= right;
right *= nums[i];
}
return res;
}记忆口诀：先算左边累乘，再乘右边累乘。
7. 缺失的第一个正数 (LeetCode 41)
题目：找出数组中缺失的最小正整数（要求O(n)时间，O(1)空间）。
核心思路：原地哈希，把数字放到对应的位置上
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
// 把每个数放到它应该在的位置：数字x放到下标x-1
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
swap(nums[i], nums[nums[i] - 1]);
}
}
// 找第一个不在正确位置的数
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}记忆口诀：把数字归位，找第一个错位的。
8. 下一个排列 (LeetCode 31)
题目：找出数组的下一个字典序更大的排列。
核心思路：从右往左找第一个下降点，然后做交换和翻转
void nextPermutation(vector<int>& nums) {
int n = nums.size();
int i = n - 2;
// 1. 从右往左，找第一个下降的位置
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
// 2. 从右往左，找第一个比nums[i]大的数
int j = n - 1;
while (nums[j] <= nums[i]) {
j--;
}
swap(nums[i], nums[j]); // 3. 交换
}
// 4. 翻转i后面的部分
reverse(nums.begin() + i + 1, nums.end());
}例子：[1,2,3] → [1,3,2] → [2,1,3] → [2,3,1] → [3,1,2] → [3,2,1] → [1,2,3]
记忆口诀：找下降点，换个稍大的，后面翻转变最小。
9. 搜索二维矩阵 II (LeetCode 240)
题目：在一个每行从左到右递增、每列从上到下递增的矩阵中搜索目标值。
核心思路：从右上角开始搜索
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty()) return false;
int row = 0, col = matrix[0].size() - 1; // 从右上角开始
while (row < matrix.size() && col >= 0) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
col--; // 太大了，往左走
} else {
row++; // 太小了，往下走
}
}
return false;
}记忆口诀：右上角出发，大了往左，小了往下。
10. 数组总结
| 题目 | 核心技巧 | 时间复杂度 |
|---|---|---|
| 两数之和 | 哈希表 | O(n) |
| 三数之和 | 排序+双指针 | O(n²) |
| 最大子数组和 | 动态规划 | O(n) |
| 合并区间 | 排序+贪心 | O(nlogn) |
| 轮转数组 | 三次翻转 | O(n) |
| 除自身以外乘积 | 前缀积+后缀积 | O(n) |
| 缺失的第一个正数 | 原地哈希 | O(n) |
| 下一个排列 | 找规律 | O(n) |
| 搜索二维矩阵 | 从右上角搜索 | O(m+n) |
数组题目常用技巧：
- 双指针：左右指针、快慢指针
- 排序预处理：很多题排序后更好做
- 哈希表：快速查找、去重
- 前缀和/前缀积：区间求和问题
- 原地操作：利用数组本身作为哈希表
双指针与滑动窗口专题
双指针和滑动窗口是解决数组/字符串问题的利器，掌握这两种技巧可以把很多O(n²)的问题优化到O(n)。
1. 盛最多水的容器 (LeetCode 11)
题目：给定数组表示柱子高度，找两根柱子，使它们与x轴构成的容器能盛最多的水。
核心思路：左右指针向中间收缩，每次移动较短的那根
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int maxWater = 0;
while (left < right) {
// 面积 = 宽度 × 较短的高度
int water = (right - left) * min(height[left], height[right]);
maxWater = max(maxWater, water);
// 移动较短的那根（因为移动长的不可能让面积变大）
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}为什么移动短的？ 宽度在减小，只有高度变大才可能让面积变大，而高度取决于短板。
记忆口诀：左右夹逼，移动短板。
2. 接雨水 (LeetCode 42)
题目：给定柱子高度数组，计算能接多少雨水。
核心思路：每个位置能接的水 = min(左边最高, 右边最高) – 当前高度
方法一：双指针法
int trap(vector<int>& height) {
int left = 0, right = height.size() - 1;
int leftMax = 0, rightMax = 0;
int water = 0;
while (left < right) {
if (height[left] < height[right]) {
// 左边较低，处理左边
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
// 右边较低，处理右边
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}方法二：前缀最大值（更好理解）
int trap(vector<int>& height) {
int n = height.size();
vector<int> leftMax(n), rightMax(n);
// 计算每个位置左边的最大值
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = max(leftMax[i-1], height[i]);
}
// 计算每个位置右边的最大值
rightMax[n-1] = height[n-1];
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = max(rightMax[i+1], height[i]);
}
// 计算总水量
int water = 0;
for (int i = 0; i < n; i++) {
water += min(leftMax[i], rightMax[i]) - height[i];
}
return water;
}记忆口诀：每格水量看左右最高的短板。
3. 无重复字符的最长子串 (LeetCode 3)
题目：找出字符串中不含重复字符的最长子串的长度。
核心思路：滑动窗口 + 哈希表记录字符位置
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> charIndex; // 字符 -> 最近出现位置
int maxLen = 0;
int left = 0;
for (int right = 0; right < s.size(); right++) {
char c = s[right];
// 如果字符重复出现，左指针跳到重复位置的下一位
if (charIndex.count(c) && charIndex[c] >= left) {
left = charIndex[c] + 1;
}
charIndex[c] = right;
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}记忆口诀：右指针扩张，遇重复左指针跳过去。
4. 找到字符串中所有字母异位词 (LeetCode 438)
题目：在s中找出所有p的字母异位词（字母相同但顺序可以不同）的起始索引。
核心思路：固定大小的滑动窗口 + 字符计数
vector<int> findAnagrams(string s, string p) {
vector<int> res;
if (s.size() < p.size()) return res;
vector<int> pCount(26, 0), sCount(26, 0);
// 统计p中每个字符的数量
for (char c : p) {
pCount[c - 'a']++;
}
// 滑动窗口
for (int i = 0; i < s.size(); i++) {
sCount[s[i] - 'a']++; // 右边进入窗口
if (i >= p.size()) {
sCount[s[i - p.size()] - 'a']--; // 左边离开窗口
}
if (sCount == pCount) { // 窗口内字符计数相同
res.push_back(i - p.size() + 1);
}
}
return res;
}记忆口诀：固定窗口滑动，计数相等就是答案。
5. 最小覆盖子串 (LeetCode 76)
题目：在s中找出包含t所有字符的最短子串。
核心思路：滑动窗口，先扩张找到可行解，再收缩优化
string minWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0; // 满足条件的字符数
int start = 0, minLen = INT_MAX;
while (right < s.size()) {
char c = s[right++]; // 扩张窗口
if (need.count(c)) {
window[c]++;
if (window[c] == need[c]) valid++;
}
// 当窗口包含了所有需要的字符，尝试收缩
while (valid == need.size()) {
if (right - left < minLen) {
start = left;
minLen = right - left;
}
char d = s[left++]; // 收缩窗口
if (need.count(d)) {
if (window[d] == need[d]) valid--;
window[d]--;
}
}
}
return minLen == INT_MAX ? "" : s.substr(start, minLen);
}记忆口诀：先扩张凑齐，再收缩求最优。
6. 和为K的子数组 (LeetCode 560)
题目：找出数组中和为k的连续子数组的个数。
核心思路：前缀和 + 哈希表
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> prefixCount; // 前缀和 -> 出现次数
prefixCount[0] = 1; // 前缀和为0出现1次
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
// 如果存在前缀和为 sum - k，说明中间那段和为k
if (prefixCount.count(sum - k)) {
count += prefixCount[sum - k];
}
prefixCount[sum]++;
}
return count;
}图解：
前缀和: [0, a, b, c, d, ...]
如果 d - a = k，说明 a到d 这段的和是k记忆口诀：前缀和差值等于k就找到了。
7. 移动零 (LeetCode 283)
题目：将数组中的所有0移动到末尾，保持非零元素的相对顺序。
核心思路：双指针，一个遍历，一个指向下一个非零位置
void moveZeroes(vector<int>& nums) {
int slow = 0; // 指向下一个非零元素应该放的位置
for (int fast = 0; fast < nums.size(); fast++) {
if (nums[fast] != 0) {
swap(nums[slow], nums[fast]);
slow++;
}
}
}记忆口诀：快指针找非零，慢指针来安放。
8. 颜色分类 (LeetCode 75)
题目：对只包含0、1、2的数组进行排序（荷兰国旗问题）。
核心思路：三指针，0往左放，2往右放，1在中间
void sortColors(vector<int>& nums) {
int left = 0; // 0的右边界
int right = nums.size() - 1; // 2的左边界
int cur = 0;
while (cur <= right) {
if (nums[cur] == 0) {
swap(nums[cur], nums[left]);
left++;
cur++;
} else if (nums[cur] == 2) {
swap(nums[cur], nums[right]);
right--;
// 注意：cur不动，因为换过来的数还没检查
} else {
cur++;
}
}
}记忆口诀：0往左扔，2往右扔，1不管。
9. 双指针/滑动窗口模板总结
滑动窗口模板
void slidingWindow(string s) {
unordered_map<char, int> window;
int left = 0, right = 0;
while (right < s.size()) {
char c = s[right];
right++;
// 更新窗口内数据
...
// 判断是否需要收缩窗口
while (需要收缩) {
char d = s[left];
left++;
// 更新窗口内数据
...
}
}
}题目分类
| 题目 | 技巧 | 关键点 |
|---|---|---|
| 盛最多水的容器 | 双指针向中间 | 移动短板 |
| 接雨水 | 双指针/前缀最值 | 取决于左右最高的短板 |
| 无重复字符的最长子串 | 滑动窗口 | 右扩左缩 |
| 找到所有字母异位词 | 固定窗口 | 字符计数 |
| 最小覆盖子串 | 滑动窗口 | 先扩张后收缩 |
| 和为K的子数组 | 前缀和+哈希 | 不是滑动窗口（有负数） |
| 移动零 | 快慢指针 | 非零往前放 |
| 颜色分类 | 三指针 | 荷兰国旗 |
什么时候用滑动窗口？
- 连续子数组/子串问题
- 满足某种条件的最长/最短
- 元素都是正数时求和为k
什么时候用前缀和？
- 有负数的子数组求和问题
- 需要频繁查询区间和
链表专题
链表是面试高频考点，核心技巧包括：快慢指针、虚拟头节点、递归等。
链表基础结构
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};1. 反转链表 (LeetCode 206)
题目：反转一个单链表。
方法一：迭代法（最常用）
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* next = curr->next; // 先保存下一个
curr->next = prev; // 反转指向
prev = curr; // prev前进
curr = next; // curr前进
}
return prev;
}方法二：递归法（更优雅）
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* newHead = reverseList(head->next);
head->next->next = head; // 让下一个节点指向自己
head->next = nullptr; // 断开原来的指向
return newHead;
}图解迭代过程：
1 -> 2 -> 3 -> null
↓
null <- 1 2 -> 3 -> null (prev=1, curr=2)
↓
null <- 1 <- 2 3 -> null (prev=2, curr=3)
↓
null <- 1 <- 2 <- 3 (prev=3, curr=null)记忆口诀：保存下一个，反转当前，双指针前进。
2. 反转链表 II (LeetCode 92)
题目：反转从位置left到right的链表部分。
核心思路：找到需要反转的区间，头插法反转
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode dummy(0);
dummy.next = head;
ListNode* pre = &dummy;
// 找到left的前一个节点
for (int i = 0; i < left - 1; i++) {
pre = pre->next;
}
// 头插法反转
ListNode* cur = pre->next;
for (int i = 0; i < right - left; i++) {
ListNode* next = cur->next;
cur->next = next->next;
next->next = pre->next;
pre->next = next;
}
return dummy.next;
}记忆口诀：找到起点前一位，头插法反转中间段。
3. 合并两个有序链表 (LeetCode 21)
题目：将两个升序链表合并为一个新的升序链表。
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0); // 虚拟头节点
ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
// 接上剩余部分
tail->next = l1 ? l1 : l2;
return dummy.next;
}记忆口诀：虚拟头节点开路，比较大小接小的。
4. 环形链表 (LeetCode 141)
题目：判断链表中是否有环。
核心思路：快慢指针，快指针一次走2步，慢指针一次走1步，有环必相遇
bool hasCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}为什么会相遇？ 快指针每次比慢指针多走1步，如果有环，差距会逐渐缩小直到相遇。
5. 环形链表 II (LeetCode 142)
题目：返回链表入环的第一个节点。
核心思路：快慢指针相遇后，再从head出发，与慢指针相遇处即为入口
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
// 第一次相遇
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (!fast || !fast->next) return nullptr; // 无环
// 从head出发，与slow相遇处即为入口
fast = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}数学证明：设head到入口距离为a，入口到相遇点距离为b，环长为c。
- 相遇时：slow走了a+b，fast走了a+b+nc
- 因为fast=2×slow，所以a+b = nc
- 从head和相遇点同时出发，走a步会在入口相遇
6. 相交链表 (LeetCode 160)
题目：找到两个链表相交的起始节点。
核心思路：让两个指针走相同的路程
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pA = headA, *pB = headB;
// pA走完A再走B，pB走完B再走A
// 如果相交，会在交点相遇；不相交，同时到达null
while (pA != pB) {
pA = pA ? pA->next : headB;
pB = pB ? pB->next : headA;
}
return pA;
}图解：
A: a1 -> a2 -> c1 -> c2
↑
B: b1 -> b2
路径A+B: a1->a2->c1->c2->b1->b2->c1
路径B+A: b1->b2->c1->c2->a1->a2->c1
两者在c1相遇！记忆口诀：你走我的路，我走你的路，终会相遇。
7. 删除链表的倒数第N个节点 (LeetCode 19)
题目：删除链表的倒数第n个节点。
核心思路：快指针先走n步，然后快慢同时走
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0);
dummy.next = head;
ListNode *fast = &dummy, *slow = &dummy;
// fast先走n+1步
for (int i = 0; i <= n; i++) {
fast = fast->next;
}
// 同时走，fast到末尾时，slow在要删除节点的前一个
while (fast) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return dummy.next;
}记忆口诀：快指针先跑n步，然后一起跑到底。
8. 两数相加 (LeetCode 2)
题目：两个链表表示的数字相加（逆序存储）。
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* cur = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
int sum = carry;
if (l1) { sum += l1->val; l1 = l1->next; }
if (l2) { sum += l2->val; l2 = l2->next; }
carry = sum / 10;
cur->next = new ListNode(sum % 10);
cur = cur->next;
}
return dummy.next;
}记忆口诀：逐位相加，别忘进位。
9. 回文链表 (LeetCode 234)
题目：判断链表是否是回文链表。
核心思路：找中点 + 反转后半部分 + 比较
bool isPalindrome(ListNode* head) {
// 1. 快慢指针找中点
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// 2. 反转后半部分
ListNode* prev = nullptr;
while (slow) {
ListNode* next = slow->next;
slow->next = prev;
prev = slow;
slow = next;
}
// 3. 比较前半和后半
ListNode *left = head, *right = prev;
while (right) {
if (left->val != right->val) return false;
left = left->next;
right = right->next;
}
return true;
}记忆口诀：找中点，反转后半，逐个比较。
10. 排序链表 (LeetCode 148)
题目：对链表进行排序（O(nlogn)时间复杂度）。
核心思路：归并排序（找中点 + 分割 + 合并）
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
// 1. 快慢指针找中点
ListNode *slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// 2. 分割成两半
ListNode* mid = slow->next;
slow->next = nullptr;
// 3. 递归排序
ListNode* left = sortList(head);
ListNode* right = sortList(mid);
// 4. 合并
return mergeTwoLists(left, right);
}
// 合并两个有序链表（同第3题）
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (l1 && l2) {
if (l1->val <= l2->val) {
tail->next = l1; l1 = l1->next;
} else {
tail->next = l2; l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}记忆口诀：找中点分两半，递归排序再合并。
11. LRU缓存 (LeetCode 146)
题目：设计一个LRU缓存结构。
核心思路：哈希表 + 双向链表
class LRUCache {
private:
struct Node {
int key, val;
Node *prev, *next;
Node(int k = 0, int v = 0) : key(k), val(v), prev(nullptr), next(nullptr) {}
};
int capacity;
Node *head, *tail; // 虚拟头尾节点
unordered_map<int, Node*> cache;
void addToHead(Node* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void moveToHead(Node* node) {
removeNode(node);
addToHead(node);
}
public:
LRUCache(int capacity) : capacity(capacity) {
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (!cache.count(key)) return -1;
Node* node = cache[key];
moveToHead(node); // 移到头部（最近使用）
return node->val;
}
void put(int key, int value) {
if (cache.count(key)) {
Node* node = cache[key];
node->val = value;
moveToHead(node);
} else {
Node* node = new Node(key, value);
cache[key] = node;
addToHead(node);
if (cache.size() > capacity) {
Node* removed = tail->prev;
removeNode(removed);
cache.erase(removed->key);
delete removed;
}
}
}
};记忆口诀：哈希表快速查，双向链表维护顺序。
12. 链表总结
| 题目 | 核心技巧 |
|---|---|
| 反转链表 | 三指针迭代/递归 |
| 合并有序链表 | 虚拟头节点 |
| 环形链表 | 快慢指针 |
| 环形链表入口 | 数学推导 |
| 相交链表 | 走相同路程 |
| 倒数第N个 | 快指针先走N步 |
| 回文链表 | 找中点+反转 |
| 排序链表 | 归并排序 |
| LRU缓存 | 哈希表+双向链表 |
链表常用技巧：
- 虚拟头节点：简化边界处理
- 快慢指针：找中点、判环
- 递归：很多链表问题可以优雅地递归解决
- 画图：链表题一定要画图，理清指针关系
哈希表专题
哈希表的核心能力是O(1)的查找，常用于快速判重、计数、建立映射关系。
1. 两数之和 (LeetCode 1)
题目：找出数组中和为target的两个数的下标。
核心思路：遍历时记录”我需要什么”
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map; // 值 -> 下标
for (int i = 0; i < nums.size(); i++) {
int need = target - nums[i];
if (map.count(need)) {
return {map[need], i};
}
map[nums[i]] = i;
}
return {};
}记忆口诀：一边遍历一边存，看看有没有我需要的。
2. 字母异位词分组 (LeetCode 49)
题目：把字母异位词（字母相同但顺序不同的单词）分组。
核心思路：排序后作为key，相同key的放一组
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> groups;
for (const string& s : strs) {
string key = s;
sort(key.begin(), key.end()); // 排序作为key
groups[key].push_back(s);
}
vector<vector<string>> res;
for (auto& [key, group] : groups) {
res.push_back(group);
}
return res;
}另一种key的方法（更快）：用字符计数作为key
string getKey(const string& s) {
vector<int> count(26, 0);
for (char c : s) count[c - 'a']++;
string key;
for (int i = 0; i < 26; i++) {
key += to_string(count[i]) + "#";
}
return key;
}记忆口诀：异位词排序后相同，用排序结果做key。
3. 最长连续序列 (LeetCode 128)
题目：找出数组中最长的连续元素序列的长度（要求O(n)时间复杂度）。
核心思路：用哈希集合，只从序列起点开始计数
int longestConsecutive(vector<int>& nums) {
unordered_set<int> numSet(nums.begin(), nums.end());
int maxLen = 0;
for (int num : numSet) {
// 只从序列的起点开始计数（没有num-1说明num是起点）
if (!numSet.count(num - 1)) {
int curNum = num;
int curLen = 1;
while (numSet.count(curNum + 1)) {
curNum++;
curLen++;
}
maxLen = max(maxLen, curLen);
}
}
return maxLen;
}为什么是O(n)？ 每个数最多被访问两次（一次判断是否起点，一次在while中被计数）。
记忆口诀：只从起点开始数，跳过非起点。
4. 有效的字母异位词 (LeetCode 242)
题目：判断两个字符串是否是字母异位词。
核心思路：字符计数
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
vector<int> count(26, 0);
for (int i = 0; i < s.size(); i++) {
count[s[i] - 'a']++;
count[t[i] - 'a']--;
}
for (int c : count) {
if (c != 0) return false;
}
return true;
}记忆口诀：一加一减，全零则是。
5. 存在重复元素 (LeetCode 217)
题目：判断数组中是否有重复元素。
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> seen;
for (int num : nums) {
if (seen.count(num)) return true;
seen.insert(num);
}
return false;
}6. 存在重复元素 II (LeetCode 219)
题目：判断是否存在两个不同下标i和j，使得nums[i]==nums[j]且|i-j|<=k。
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> lastIndex; // 值 -> 最近出现的下标
for (int i = 0; i < nums.size(); i++) {
if (lastIndex.count(nums[i]) && i - lastIndex[nums[i]] <= k) {
return true;
}
lastIndex[nums[i]] = i;
}
return false;
}7. 同构字符串 (LeetCode 205)
题目：判断s和t是否同构（可以通过字符替换使s变成t）。
bool isIsomorphic(string s, string t) {
unordered_map<char, char> s2t, t2s;
for (int i = 0; i < s.size(); i++) {
char a = s[i], b = t[i];
// 检查映射是否一致
if ((s2t.count(a) && s2t[a] != b) ||
(t2s.count(b) && t2s[b] != a)) {
return false;
}
s2t[a] = b;
t2s[b] = a;
}
return true;
}记忆口诀：双向映射必须一致。
8. 单词规律 (LeetCode 290)
题目：判断pattern和字符串s是否匹配（如”abba”匹配”dog cat cat dog”）。
bool wordPattern(string pattern, string s) {
unordered_map<char, string> p2w;
unordered_map<string, char> w2p;
vector<string> words;
stringstream ss(s);
string word;
while (ss >> word) words.push_back(word);
if (pattern.size() != words.size()) return false;
for (int i = 0; i < pattern.size(); i++) {
char p = pattern[i];
const string& w = words[i];
if ((p2w.count(p) && p2w[p] != w) ||
(w2p.count(w) && w2p[w] != p)) {
return false;
}
p2w[p] = w;
w2p[w] = p;
}
return true;
}9. 快乐数 (LeetCode 202)
题目：判断一个数是否是快乐数（各位数字平方和最终等于1）。
核心思路：哈希表检测循环
bool isHappy(int n) {
unordered_set<int> seen;
while (n != 1 && !seen.count(n)) {
seen.insert(n);
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
n = sum;
}
return n == 1;
}也可以用快慢指针（类似环形链表）
10. 前K个高频元素 (LeetCode 347)
题目：返回数组中出现频率最高的k个元素。
方法一：哈希表 + 小顶堆
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> count;
for (int num : nums) count[num]++;
// 小顶堆，按频率排序
auto cmp = [](pair<int,int>& a, pair<int,int>& b) {
return a.second > b.second;
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);
for (auto& [num, freq] : count) {
pq.push({num, freq});
if (pq.size() > k) pq.pop();
}
vector<int> res;
while (!pq.empty()) {
res.push_back(pq.top().first);
pq.pop();
}
return res;
}方法二：桶排序（更快）
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> count;
int maxFreq = 0;
for (int num : nums) {
count[num]++;
maxFreq = max(maxFreq, count[num]);
}
// 桶：下标是频率，值是该频率的数字列表
vector<vector<int>> buckets(maxFreq + 1);
for (auto& [num, freq] : count) {
buckets[freq].push_back(num);
}
vector<int> res;
for (int i = maxFreq; i >= 0 && res.size() < k; i--) {
for (int num : buckets[i]) {
res.push_back(num);
if (res.size() == k) break;
}
}
return res;
}11. 哈希表总结
| 题目 | 核心技巧 | 时间复杂度 |
|---|---|---|
| 两数之和 | 记录需要的值 | O(n) |
| 字母异位词分组 | 排序/计数作为key | O(nklogk) |
| 最长连续序列 | 只从起点开始计数 | O(n) |
| 同构字符串 | 双向映射 | O(n) |
| 前K个高频元素 | 哈希表+堆/桶排序 | O(nlogk)/O(n) |
哈希表常用场景：
- 快速查找：O(1)判断元素是否存在
- 计数统计：统计每个元素出现次数
- 建立映射：一对一或一对多的映射关系
- 去重：利用set的唯一性
C++ STL哈希容器：
unordered_set：元素唯一，无序unordered_map：键值对，键唯一，无序unordered_multiset：允许重复元素unordered_multimap：允许重复键
注意事项：
- 哈希表不保证顺序
- 自定义类型需要提供哈希函数
- 最坏情况O(n)，但一般情况O(1)
字符串专题
字符串处理的核心技巧：双指针、滑动窗口、动态规划、KMP算法。
1. 最长回文子串 (LeetCode 5)
题目：找出字符串中最长的回文子串。
方法一：中心扩展法（推荐）
核心思路：以每个位置为中心，向两边扩展
class Solution {
public:
string longestPalindrome(string s) {
if (s.empty()) return "";
int start = 0, maxLen = 1;
for (int i = 0; i < s.size(); i++) {
// 以i为中心（奇数长度）
auto [l1, r1] = expand(s, i, i);
// 以i和i+1为中心（偶数长度）
auto [l2, r2] = expand(s, i, i + 1);
if (r1 - l1 + 1 > maxLen) {
start = l1;
maxLen = r1 - l1 + 1;
}
if (r2 - l2 + 1 > maxLen) {
start = l2;
maxLen = r2 - l2 + 1;
}
}
return s.substr(start, maxLen);
}
private:
pair<int, int> expand(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return {left + 1, right - 1};
}
};方法二：动态规划
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) return s;
// dp[i][j] = s[i..j]是否是回文
vector<vector<bool>> dp(n, vector<bool>(n, false));
int start = 0, maxLen = 1;
// 所有单个字符都是回文
for (int i = 0; i < n; i++) dp[i][i] = true;
// 枚举子串长度
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s[i] == s[j]) {
if (len <= 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if (dp[i][j] && len > maxLen) {
start = i;
maxLen = len;
}
}
}
return s.substr(start, maxLen);
}记忆口诀：中心扩展最直观，两边相等就继续。
2. 回文子串个数 (LeetCode 647)
题目：计算字符串中有多少个回文子串。
int countSubstrings(string s) {
int count = 0;
for (int i = 0; i < s.size(); i++) {
// 奇数长度回文
count += expandCount(s, i, i);
// 偶数长度回文
count += expandCount(s, i, i + 1);
}
return count;
}
int expandCount(const string& s, int left, int right) {
int count = 0;
while (left >= 0 && right < s.size() && s[left] == s[right]) {
count++;
left--;
right++;
}
return count;
}3. 最长公共前缀 (LeetCode 14)
题目：找出字符串数组中的最长公共前缀。
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
string prefix = strs[0];
for (int i = 1; i < strs.size(); i++) {
// 不断缩短prefix直到它是strs[i]的前缀
while (strs[i].find(prefix) != 0) {
prefix = prefix.substr(0, prefix.size() - 1);
if (prefix.empty()) return "";
}
}
return prefix;
}纵向扫描方法：
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
for (int i = 0; i < strs[0].size(); i++) {
char c = strs[0][i];
for (int j = 1; j < strs.size(); j++) {
if (i >= strs[j].size() || strs[j][i] != c) {
return strs[0].substr(0, i);
}
}
}
return strs[0];
}4. 有效的括号 (LeetCode 20)
题目：判断括号字符串是否有效。
bool isValid(string s) {
stack<char> stk;
unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
for (char c : s) {
if (pairs.count(c)) { // 右括号
if (stk.empty() || stk.top() != pairs[c]) {
return false;
}
stk.pop();
} else { // 左括号
stk.push(c);
}
}
return stk.empty();
}记忆口诀：左括号入栈，右括号匹配出栈。
5. 字符串转整数 (LeetCode 8)
题目：实现atoi函数，将字符串转换为整数。
int myAtoi(string s) {
int i = 0, n = s.size();
// 1. 跳过前导空格
while (i < n && s[i] == ' ') i++;
if (i == n) return 0;
// 2. 处理符号
int sign = 1;
if (s[i] == '+' || s[i] == '-') {
sign = (s[i] == '-') ? -1 : 1;
i++;
}
// 3. 转换数字
long long result = 0;
while (i < n && isdigit(s[i])) {
result = result * 10 + (s[i] - '0');
// 检查溢出
if (result * sign > INT_MAX) return INT_MAX;
if (result * sign < INT_MIN) return INT_MIN;
i++;
}
return result * sign;
}6. 实现strStr() / 找出字符串中第一个匹配项 (LeetCode 28)
题目：在haystack中找needle第一次出现的位置。
方法一：暴力匹配
int strStr(string haystack, string needle) {
int m = haystack.size(), n = needle.size();
for (int i = 0; i <= m - n; i++) {
int j = 0;
while (j < n && haystack[i + j] == needle[j]) {
j++;
}
if (j == n) return i;
}
return -1;
}方法二：KMP算法
核心思想：利用已匹配的信息，避免重复匹配
class Solution {
public:
int strStr(string haystack, string needle) {
int m = haystack.size(), n = needle.size();
if (n == 0) return 0;
// 构建next数组（前缀表）
vector<int> next = buildNext(needle);
int j = 0; // needle指针
for (int i = 0; i < m; i++) { // haystack指针
while (j > 0 && haystack[i] != needle[j]) {
j = next[j - 1]; // 回退
}
if (haystack[i] == needle[j]) {
j++;
}
if (j == n) {
return i - n + 1;
}
}
return -1;
}
private:
vector<int> buildNext(const string& pattern) {
int n = pattern.size();
vector<int> next(n, 0);
int j = 0; // 前缀长度
for (int i = 1; i < n; i++) {
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
if (pattern[i] == pattern[j]) {
j++;
}
next[i] = j;
}
return next;
}
};KMP口诀：不匹配时，用next表回退，避免从头再来。
7. 反转字符串 (LeetCode 344)
题目：原地反转字符串。
void reverseString(vector<char>& s) {
int left = 0, right = s.size() - 1;
while (left < right) {
swap(s[left++], s[right--]);
}
}8. 反转字符串中的单词 (LeetCode 151)
题目：反转字符串中单词的顺序。
string reverseWords(string s) {
// 1. 去除多余空格，反转整个字符串
// 2. 反转每个单词
// 使用stringstream简化处理
stringstream ss(s);
string word, result;
while (ss >> word) {
if (!result.empty()) {
result = word + " " + result;
} else {
result = word;
}
}
return result;
}原地算法：
string reverseWords(string s) {
// 1. 反转整个字符串
reverse(s.begin(), s.end());
int n = s.size();
int idx = 0; // 写入位置
for (int start = 0; start < n; start++) {
if (s[start] != ' ') {
// 添加空格分隔（非第一个单词）
if (idx != 0) s[idx++] = ' ';
// 移动单词
int end = start;
while (end < n && s[end] != ' ') {
s[idx++] = s[end++];
}
// 反转刚添加的单词
reverse(s.begin() + idx - (end - start), s.begin() + idx);
start = end;
}
}
s.resize(idx);
return s;
}9. Z字形变换 (LeetCode 6)
题目：将字符串按Z字形排列后按行读取。
string convert(string s, int numRows) {
if (numRows == 1) return s;
vector<string> rows(min(numRows, (int)s.size()));
int curRow = 0;
bool goingDown = false;
for (char c : s) {
rows[curRow] += c;
// 到达顶部或底部时改变方向
if (curRow == 0 || curRow == numRows - 1) {
goingDown = !goingDown;
}
curRow += goingDown ? 1 : -1;
}
string result;
for (const string& row : rows) {
result += row;
}
return result;
}记忆口诀：模拟走Z字形，到边界就掉头。
10. 字符串相加 (LeetCode 415)
题目：模拟大数加法。
string addStrings(string num1, string num2) {
string result;
int carry = 0;
int i = num1.size() - 1;
int j = num2.size() - 1;
while (i >= 0 || j >= 0 || carry) {
int sum = carry;
if (i >= 0) sum += num1[i--] - '0';
if (j >= 0) sum += num2[j--] - '0';
result += (sum % 10) + '0';
carry = sum / 10;
}
reverse(result.begin(), result.end());
return result;
}11. 字符串相乘 (LeetCode 43)
题目：模拟大数乘法。
string multiply(string num1, string num2) {
int m = num1.size(), n = num2.size();
vector<int> result(m + n, 0);
// 从低位到高位相乘
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int mul = (num1[i] - '0') * (num2[j] - '0');
int p1 = i + j, p2 = i + j + 1; // 结果存放位置
int sum = mul + result[p2];
result[p2] = sum % 10;
result[p1] += sum / 10;
}
}
// 转为字符串，跳过前导零
string str;
for (int num : result) {
if (!(str.empty() && num == 0)) {
str += (num + '0');
}
}
return str.empty() ? "0" : str;
}记忆口诀：i * j 的结果放在 i+j 和 i+j+1 位置。
12. 字符串总结
| 题目 | 核心技巧 | 时间复杂度 |
|---|---|---|
| 最长回文子串 | 中心扩展/DP | O(n²) |
| 有效的括号 | 栈匹配 | O(n) |
| 字符串匹配(strStr) | KMP算法 | O(m+n) |
| 字符串相加/相乘 | 模拟竖式运算 | O(n)/O(mn) |
常用字符串技巧：
- 双指针：反转、回文判断
- 滑动窗口：子串问题
- 栈：括号匹配、表达式计算
- KMP：模式匹配
- DP：最长公共子串、编辑距离
C++字符串常用操作：
s.substr(pos, len) // 子串
s.find(str) // 查找
s.compare(str) // 比较
to_string(num) // 数字转字符串
stoi(s), stol(s) // 字符串转数字
reverse(s.begin(), s.end()) // 反转二叉树专题
二叉树是面试重点，核心是掌握递归思维和遍历方式。
1. 二叉树的遍历
前序遍历 (LeetCode 144)
顺序：根 → 左 → 右
// 递归版
void preorder(TreeNode* root, vector<int>& res) {
if (!root) return;
res.push_back(root->val); // 根
preorder(root->left, res); // 左
preorder(root->right, res); // 右
}
// 迭代版（用栈）
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
res.push_back(node->val);
// 先右后左入栈（出栈时就是先左后右）
if (node->right) stk.push(node->right);
if (node->left) stk.push(node->left);
}
return res;
}中序遍历 (LeetCode 94)
顺序：左 → 根 → 右（BST中序遍历是有序的）
// 递归版
void inorder(TreeNode* root, vector<int>& res) {
if (!root) return;
inorder(root->left, res); // 左
res.push_back(root->val); // 根
inorder(root->right, res); // 右
}
// 迭代版
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
TreeNode* cur = root;
while (cur || !stk.empty()) {
// 一路向左走到底
while (cur) {
stk.push(cur);
cur = cur->left;
}
cur = stk.top();
stk.pop();
res.push_back(cur->val);
cur = cur->right;
}
return res;
}后序遍历 (LeetCode 145)
顺序：左 → 右 → 根
// 递归版
void postorder(TreeNode* root, vector<int>& res) {
if (!root) return;
postorder(root->left, res); // 左
postorder(root->right, res); // 右
res.push_back(root->val); // 根
}
// 迭代版（前序变形后反转）
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
res.push_back(node->val);
// 先左后右（与前序相反）
if (node->left) stk.push(node->left);
if (node->right) stk.push(node->right);
}
// 反转得到后序
reverse(res.begin(), res.end());
return res;
}层序遍历 (LeetCode 102)
用队列BFS
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
vector<int> level;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
res.push_back(level);
}
return res;
}遍历口诀：
- 前序：根左右（中左右）
- 中序：左根右（左中右）
- 后序：左右根（左右中）
- 层序：一层一层来
2. 二叉树的最大深度 (LeetCode 104)
方法一：递归（自底向上）
int maxDepth(TreeNode* root) {
if (!root) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}方法二：BFS层序遍历
int maxDepth(TreeNode* root) {
if (!root) return 0;
queue<TreeNode*> q;
q.push(root);
int depth = 0;
while (!q.empty()) {
int size = q.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return depth;
}3. 翻转二叉树 (LeetCode 226)
TreeNode* invertTree(TreeNode* root) {
if (!root) return nullptr;
// 交换左右子树
swap(root->left, root->right);
// 递归翻转
invertTree(root->left);
invertTree(root->right);
return root;
}记忆口诀：先交换，再递归。
4. 对称二叉树 (LeetCode 101)
bool isSymmetric(TreeNode* root) {
return isMirror(root, root);
}
bool isMirror(TreeNode* t1, TreeNode* t2) {
if (!t1 && !t2) return true;
if (!t1 || !t2) return false;
return t1->val == t2->val &&
isMirror(t1->left, t2->right) &&
isMirror(t1->right, t2->left);
}记忆口诀：左右交叉比较。
5. 二叉树的直径 (LeetCode 543)
题目：求任意两节点间的最长路径。
class Solution {
int diameter = 0;
public:
int diameterOfBinaryTree(TreeNode* root) {
depth(root);
return diameter;
}
private:
int depth(TreeNode* node) {
if (!node) return 0;
int left = depth(node->left);
int right = depth(node->right);
// 更新直径（经过当前节点的最长路径）
diameter = max(diameter, left + right);
return 1 + max(left, right);
}
};记忆口诀：直径 = 左深度 + 右深度。
6. 验证二叉搜索树 (LeetCode 98)
方法一：中序遍历必须有序
class Solution {
long long prev = LLONG_MIN;
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
// 左子树
if (!isValidBST(root->left)) return false;
// 当前节点必须大于前一个
if (root->val <= prev) return false;
prev = root->val;
// 右子树
return isValidBST(root->right);
}
};方法二：传递上下界
bool isValidBST(TreeNode* root) {
return validate(root, LLONG_MIN, LLONG_MAX);
}
bool validate(TreeNode* node, long long minVal, long long maxVal) {
if (!node) return true;
if (node->val <= minVal || node->val >= maxVal) {
return false;
}
return validate(node->left, minVal, node->val) &&
validate(node->right, node->val, maxVal);
}7. 二叉搜索树中第K小的元素 (LeetCode 230)
class Solution {
int count = 0;
int result = 0;
public:
int kthSmallest(TreeNode* root, int k) {
inorder(root, k);
return result;
}
private:
void inorder(TreeNode* node, int k) {
if (!node) return;
inorder(node->left, k);
count++;
if (count == k) {
result = node->val;
return;
}
inorder(node->right, k);
}
};记忆口诀：BST中序遍历是升序，数到第k个就是答案。
8. 二叉树的最近公共祖先 (LeetCode 236)
核心思路：后序遍历，自底向上
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 如果找到p或q，或者到达空节点，返回
if (!root || root == p || root == q) {
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
// 如果左右都找到了，当前节点就是LCA
if (left && right) return root;
// 否则返回非空的那个
return left ? left : right;
}记忆口诀：
- 两边都有 → 当前就是祖先
- 只有一边 → 继续往上传
9. 从前序与中序遍历序列构造二叉树 (LeetCode 105)
核心思路：前序第一个是根，用它在中序中分割左右子树
class Solution {
unordered_map<int, int> inorderIndex;
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
// 用哈希表记录中序遍历中每个值的位置
for (int i = 0; i < inorder.size(); i++) {
inorderIndex[inorder[i]] = i;
}
return build(preorder, 0, preorder.size() - 1,
inorder, 0, inorder.size() - 1);
}
private:
TreeNode* build(vector<int>& preorder, int preL, int preR,
vector<int>& inorder, int inL, int inR) {
if (preL > preR) return nullptr;
// 前序第一个是根
int rootVal = preorder[preL];
TreeNode* root = new TreeNode(rootVal);
// 在中序中找到根的位置
int rootIndex = inorderIndex[rootVal];
int leftSize = rootIndex - inL; // 左子树大小
// 递归构建左右子树
root->left = build(preorder, preL + 1, preL + leftSize,
inorder, inL, rootIndex - 1);
root->right = build(preorder, preL + leftSize + 1, preR,
inorder, rootIndex + 1, inR);
return root;
}
};10. 二叉树展开为链表 (LeetCode 114)
题目：将二叉树原地展开为右倾斜的链表。
void flatten(TreeNode* root) {
TreeNode* cur = root;
while (cur) {
if (cur->left) {
// 找到左子树最右节点
TreeNode* rightmost = cur->left;
while (rightmost->right) {
rightmost = rightmost->right;
}
// 把右子树接到左子树的最右节点
rightmost->right = cur->right;
// 把左子树移到右边
cur->right = cur->left;
cur->left = nullptr;
}
cur = cur->right;
}
}记忆口诀：左子树的最右接右子树，左移到右。
11. 路径总和 III (LeetCode 437)
题目：找出和为targetSum的路径数（路径不需要从根开始）。
class Solution {
public:
int pathSum(TreeNode* root, int targetSum) {
unordered_map<long long, int> prefixSum; // 前缀和 -> 出现次数
prefixSum[0] = 1;
return dfs(root, 0, targetSum, prefixSum);
}
private:
int dfs(TreeNode* node, long long curSum, int target,
unordered_map<long long, int>& prefixSum) {
if (!node) return 0;
curSum += node->val;
// 找是否存在前缀和 = curSum - target
int count = prefixSum[curSum - target];
prefixSum[curSum]++;
count += dfs(node->left, curSum, target, prefixSum);
count += dfs(node->right, curSum, target, prefixSum);
prefixSum[curSum]--; // 回溯
return count;
}
};记忆口诀：前缀和思想，找 curSum – target 的次数。
12. 二叉树的右视图 (LeetCode 199)
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if (!root) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
// 每层最后一个节点
if (i == size - 1) {
res.push_back(node->val);
}
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return res;
}13. 平衡二叉树 (LeetCode 110)
bool isBalanced(TreeNode* root) {
return height(root) != -1;
}
int height(TreeNode* node) {
if (!node) return 0;
int left = height(node->left);
if (left == -1) return -1;
int right = height(node->right);
if (right == -1) return -1;
if (abs(left - right) > 1) return -1;
return 1 + max(left, right);
}记忆口诀：用-1表示不平衡，提前剪枝。
14. 二叉树总结
| 题目 | 核心技巧 | 遍历方式 |
|---|---|---|
| 最大深度 | 递归返回高度 | 后序 |
| 验证BST | 中序有序/传递边界 | 中序 |
| 最近公共祖先 | 左右都有则为祖先 | 后序 |
| 构建二叉树 | 前序定根，中序分左右 | 递归 |
| 路径总和III | 前缀和 | 前序DFS |
二叉树解题模板：
// 模板1：返回值型（自底向上）
int solve(TreeNode* root) {
if (!root) return 边界值;
int left = solve(root->left);
int right = solve(root->right);
return 处理(root->val, left, right);
}
// 模板2：遍历型（自顶向下）
void traverse(TreeNode* root, 参数) {
if (!root) return;
// 前序位置：进入节点时的操作
traverse(root->left, 新参数);
traverse(root->right, 新参数);
// 后序位置：离开节点时的操作
}记住这个思维：
- 前序：能知道父节点信息
- 后序：能知道子树信息
- 中序：BST中能得到有序序列
回溯算法专题
📖 回溯算法 是解决「枚举所有可能」问题的利器。
排列、组合、子集、N皇后……看起来很难，其实都是一个套路！
🤔 为什么需要回溯？
先看一个问题：全排列
给你
[1, 2, 3]，列出所有排列方式。
最直接的想法：三层 for 循环
for (int i : nums)
for (int j : nums)
for (int k : nums)
if (i != j && j != k && i != k)
result.push_back({i, j, k});问题来了：
- 如果是 4 个数呢？要写 4 层循环
- 如果是 n 个数呢？循环层数都不确定，怎么写？
我们需要一种能自动调整层数的方法 —— 这就是递归！
而回溯 = 递归 + 撤销。
🧠 类比：走迷宫
想象你在走迷宫：
- 选择：到了一个岔路口，选一条路走
- 递归：沿着这条路继续走，遇到岔路再选
- 撤销：走到死胡同？退回上一个岔路口，换条路
入口
│
┌────┴────┐
│ │
A B
╱ ╲ ╱ ╲
A1 A2 B1 B2
❌ ✓ ❌ ✓
你的走法：入口→A→A1→死路→退回A→A2→出口！回溯算法 = 走迷宫的策略 = 试错 + 回退
🎯 回溯算法核心
一句话记忆：选择 → 递归 → 撤销
回溯 vs 普通递归
| 对比 | 普通递归 | 回溯 |
|---|---|---|
| 目的 | 计算一个结果 | 枚举所有结果 |
| 过程 | 递归到底返回 | 递归到底后撤销，换条路 |
| 典型题 | 斐波那契、二叉树遍历 | 排列、组合、子集 |
📝 回溯算法模板（背下来！）
void backtrack(路径, 选择列表) {
if (满足结束条件) {
收集结果; // 🎯 到达叶子节点，记录答案
return;
}
for (选择 : 选择列表) {
做选择; // ✅ 将选择加入路径
backtrack(路径, 选择列表); // 🔄 递归
撤销选择; // ↩️ 将选择从路径移除（核心！）
}
}核心口诀：选择→递归→撤销（背10遍！）
🌳 回溯的本质：遍历决策树
以 [1,2,3] 全排列为例，你其实在遍历这棵树：
[]
┌──────────┼──────────┐
1 2 3
┌──┴──┐ ┌──┴──┐ ┌──┴──┐
12 13 21 23 31 32
│ │ │ │ │ │
123 132 213 231 312 321 ← 6个叶子 = 6种排列- 路径：从根到当前节点的选择（如
[1, 2]） - 选择列表：还没选的数（如
[3]） - 结束条件：到达叶子节点（路径长度 = 数组长度）
回溯本质是穷举，核心是做选择→递归→撤销选择。
1. 全排列 (LeetCode 46)
题目：给定不含重复数字的数组，返回所有可能的全排列。
🧠 生活类比
你有3张不同的扑克牌（A、K、Q），要摆成一排拍照。
第1个位置可以放 A、K、Q 任意一张；
第2个位置只能放剩下的2张中的1张；
第3个位置只能放最后剩的那张。
每次拍完一张照片（一种排列），把牌收回来，换种摆法。
📊 决策树图示
[]
┌──────────┼──────────┐
[1] [2] [3] ← 第一个位置选谁
┌──┴──┐ ┌──┴──┐ ┌──┴──┐
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2] ← 第二个位置选谁
│ │ │ │ │ │
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1] ← 结果💻 代码实现
class Solution {
vector<vector<int>> res;
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<int> path;
vector<bool> used(nums.size(), false);
backtrack(nums, path, used);
return res;
}
private:
void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used) {
if (path.size() == nums.size()) {
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i]) continue; // 跳过已使用的
used[i] = true;
path.push_back(nums[i]);
backtrack(nums, path, used);
path.pop_back();
used[i] = false;
}
}
};2. 全排列 II (LeetCode 47)
题目：含重复数字的数组，返回所有不重复的全排列。
关键：排序 + 剪枝去重
class Solution {
vector<vector<int>> res;
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 排序是关键！
vector<int> path;
vector<bool> used(nums.size(), false);
backtrack(nums, path, used);
return res;
}
private:
void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used) {
if (path.size() == nums.size()) {
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i]) continue;
// 去重：相同的数，前一个没用过，当前就跳过
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
used[i] = true;
path.push_back(nums[i]);
backtrack(nums, path, used);
path.pop_back();
used[i] = false;
}
}
};去重口诀：相同元素，保持相对顺序。
3. 子集 (LeetCode 78)
题目：返回数组的所有子集（幂集）。
class Solution {
vector<vector<int>> res;
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> path;
backtrack(nums, 0, path);
return res;
}
private:
void backtrack(vector<int>& nums, int start, vector<int>& path) {
res.push_back(path); // 每个节点都是一个子集
for (int i = start; i < nums.size(); i++) {
path.push_back(nums[i]);
backtrack(nums, i + 1, path); // 从i+1开始，避免重复
path.pop_back();
}
}
};子集 vs 排列：
- 排列：从0开始，用used数组
- 子集：从start开始，不回头
4. 子集 II (LeetCode 90)
题目：含重复元素的数组，返回所有不重复的子集。
class Solution {
vector<vector<int>> res;
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 排序去重
vector<int> path;
backtrack(nums, 0, path);
return res;
}
private:
void backtrack(vector<int>& nums, int start, vector<int>& path) {
res.push_back(path);
for (int i = start; i < nums.size(); i++) {
// 去重：同层相同元素只选第一个
if (i > start && nums[i] == nums[i-1]) continue;
path.push_back(nums[i]);
backtrack(nums, i + 1, path);
path.pop_back();
}
}
};5. 组合 (LeetCode 77)
题目：从1到n中选k个数的所有组合。
class Solution {
vector<vector<int>> res;
public:
vector<vector<int>> combine(int n, int k) {
vector<int> path;
backtrack(n, k, 1, path);
return res;
}
private:
void backtrack(int n, int k, int start, vector<int>& path) {
if (path.size() == k) {
res.push_back(path);
return;
}
// 剪枝：剩余数字不够了就不用继续了
for (int i = start; i <= n - (k - path.size()) + 1; i++) {
path.push_back(i);
backtrack(n, k, i + 1, path);
path.pop_back();
}
}
};6. 组合总和 (LeetCode 39)
题目：从candidates中选数（可重复选），使和等于target。
class Solution {
vector<vector<int>> res;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> path;
backtrack(candidates, target, 0, path);
return res;
}
private:
void backtrack(vector<int>& candidates, int remain, int start, vector<int>& path) {
if (remain == 0) {
res.push_back(path);
return;
}
if (remain < 0) return;
for (int i = start; i < candidates.size(); i++) {
path.push_back(candidates[i]);
// 可重复选，所以还是从i开始
backtrack(candidates, remain - candidates[i], i, path);
path.pop_back();
}
}
};7. 组合总和 II (LeetCode 40)
题目：每个数只能用一次，不能有重复组合。
class Solution {
vector<vector<int>> res;
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end()); // 排序去重
vector<int> path;
backtrack(candidates, target, 0, path);
return res;
}
private:
void backtrack(vector<int>& candidates, int remain, int start, vector<int>& path) {
if (remain == 0) {
res.push_back(path);
return;
}
for (int i = start; i < candidates.size() && candidates[i] <= remain; i++) {
// 去重
if (i > start && candidates[i] == candidates[i-1]) continue;
path.push_back(candidates[i]);
backtrack(candidates, remain - candidates[i], i + 1, path);
path.pop_back();
}
}
};8. 电话号码的字母组合 (LeetCode 17)
题目：给定数字字符串，返回所有可能的字母组合。
class Solution {
vector<string> res;
string letterMap[10] = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return res;
string path;
backtrack(digits, 0, path);
return res;
}
private:
void backtrack(const string& digits, int index, string& path) {
if (index == digits.size()) {
res.push_back(path);
return;
}
string letters = letterMap[digits[index] - '0'];
for (char c : letters) {
path.push_back(c);
backtrack(digits, index + 1, path);
path.pop_back();
}
}
};9. 分割回文串 (LeetCode 131)
题目：将字符串分割成若干回文子串。
class Solution {
vector<vector<string>> res;
public:
vector<vector<string>> partition(string s) {
vector<string> path;
backtrack(s, 0, path);
return res;
}
private:
void backtrack(const string& s, int start, vector<string>& path) {
if (start == s.size()) {
res.push_back(path);
return;
}
for (int i = start; i < s.size(); i++) {
if (isPalindrome(s, start, i)) {
path.push_back(s.substr(start, i - start + 1));
backtrack(s, i + 1, path);
path.pop_back();
}
}
}
bool isPalindrome(const string& s, int left, int right) {
while (left < right) {
if (s[left++] != s[right--]) return false;
}
return true;
}
};10. N皇后 (LeetCode 51)
题目：在n×n棋盘上放置n个皇后，使其互不攻击。
class Solution {
vector<vector<string>> res;
public:
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.'));
backtrack(board, 0);
return res;
}
private:
void backtrack(vector<string>& board, int row) {
if (row == board.size()) {
res.push_back(board);
return;
}
int n = board.size();
for (int col = 0; col < n; col++) {
if (!isValid(board, row, col)) continue;
board[row][col] = 'Q';
backtrack(board, row + 1);
board[row][col] = '.';
}
}
bool isValid(vector<string>& board, int row, int col) {
int n = board.size();
// 检查列
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') return false;
}
// 检查左上对角线
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') return false;
}
// 检查右上对角线
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') return false;
}
return true;
}
};皇后规则：同行、同列、同对角线不能有其他皇后。
11. 单词搜索 (LeetCode 79)
题目：在二维字符网格中搜索单词。
class Solution {
int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (backtrack(board, word, 0, i, j)) {
return true;
}
}
}
return false;
}
private:
bool backtrack(vector<vector<char>>& board, const string& word,
int index, int row, int col) {
if (index == word.size()) return true;
if (row < 0 || row >= board.size() ||
col < 0 || col >= board[0].size() ||
board[row][col] != word[index]) {
return false;
}
char temp = board[row][col];
board[row][col] = '#'; // 标记已访问
for (auto& dir : dirs) {
if (backtrack(board, word, index + 1, row + dir[0], col + dir[1])) {
return true;
}
}
board[row][col] = temp; // 回溯
return false;
}
};12. 回溯算法总结
| 问题类型 | 模板特点 | 去重方法 |
|---|---|---|
| 排列 | 从0开始，用used数组 | 排序+!used[i-1] |
| 子集/组合 | 从start开始，不回头 | 排序+i>start判断 |
| 分割 | 类似子集，起点是分割位置 | – |
| 棋盘 | 逐行/逐格尝试 | 检查合法性 |
回溯三要素：
- 路径：已经做出的选择
- 选择列表：当前可以做的选择
- 结束条件：到达决策树底层
剪枝优化：
- 排序：使相同元素相邻，便于去重
- 提前终止：remain < 0 或 path.size() > k
- 合法性检查：如N皇后的isValid
记忆口诀：
- 排列用used，子集用start
- 有重复先排序，同层相同跳过
- 选择→递归→撤销
动态规划专题
📖 动态规划（Dynamic Programming, DP） 是算法面试的重中之重。
很多人觉得 DP 很难，其实只是没理解它的本质。本章用类比帮你彻底搞懂！
🤔 为什么需要动态规划？
先看一个问题：爬楼梯
有 n 级台阶，每次可以爬 1 级或 2 级，问有多少种爬法？
最直接的想法：递归
int climb(int n) {
if (n <= 2) return n;
return climb(n-1) + climb(n-2); // 最后一步爬1级 + 最后一步爬2级
}问题来了：当 n=40 时，程序慢到爆炸！为什么？
画出递归树你就明白了：
climb(5)
/ \
climb(4) climb(3)
/ \ / \
climb(3) climb(2) climb(2) climb(1)
/ \
climb(2) climb(1)看到问题了吗？climb(3) 被算了 2 次，climb(2) 被算了 3 次！
当 n=40 时，重复计算的次数是指数级的（约 2^40 次）！
🧠 类比：笨学生 vs 聪明学生
想象你在考试，有道大题分成很多小题，每道小题的答案下一题会用到。
- 笨学生：每道题都从头推导，即使前面算过也再算一遍
- 聪明学生：把每道小题的答案记在草稿纸上，后面直接查
动态规划 = 聪明学生的做法 = 记住子问题的答案
🎯 动态规划的核心思想
一句话记忆：把大问题拆成小问题，记住小问题的答案，避免重复计算。
DP 的两个关键条件
| 条件 | 解释 | 类比 |
|---|---|---|
| 最优子结构 | 大问题的最优解可以由小问题的最优解推出 | 到北京的最短路 = 到石家庄最短路 + 石家庄到北京 |
| 重叠子问题 | 同一个小问题被多次需要 | 爬楼梯中 climb(3) 被算多次 |
📝 DP 解题五步法（每道题都这样想）
| 步骤 | 内容 | 爬楼梯示例 |
|---|---|---|
| 1️⃣ 定义状态 | dp[i] 代表什么 | dp[i] = 爬到第 i 级的方法数 |
| 2️⃣ 状态转移 | dp[i] 怎么从之前推出 | dp[i] = dp[i-1] + dp[i-2] |
| 3️⃣ 初始化 | 边界值是什么 | dp[1] = 1, dp[2] = 2 |
| 4️⃣ 遍历顺序 | 从前往后还是从后往前 | 从 3 到 n |
| 5️⃣ 返回值 | 最终答案是什么 | dp[n] |
一、基础DP
1. 爬楼梯 (LeetCode 70)
题目：每次可以爬1或2个台阶，爬n阶有多少种方法。
🧠 生活类比
你站在楼梯底，想上到第 n 级。问：你走到第 n 级，最后一步是从哪来的？
- 可能1：从第 n-1 级爬 1 步上来
- 可能2：从第 n-2 级爬 2 步上来
所以：到第 n 级的方法 = 到第 n-1 级的方法 + 到第 n-2 级的方法
📊 图示演示
台阶: 1 2 3 4 5
方法数: 1 2 3 5 8
推导过程:
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp[5] = dp[4] + dp[3] = 5 + 3 = 8💻 代码实现
int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2; // dp[i-2] 和 dp[i-1]
for (int i = 3; i <= n; i++) {
int cur = prev1 + prev2; // dp[i] = dp[i-1] + dp[i-2]
prev2 = prev1; // 滚动：准备下一轮
prev1 = cur;
}
return prev1;
}⚠️ 易错点
- 初始化搞错：dp[1]=1, dp[2]=2，不是 dp[0]=1, dp[1]=1
- 空间优化时变量覆盖顺序错误：先更新 prev2，再更新 prev1
📝 面试怎么答
面试官：讲一下爬楼梯这道题的思路？
答：这是典型的DP问题。
- 状态定义：dp[i] 表示爬到第 i 级的方法数
- 转移方程：dp[i] = dp[i-1] + dp[i-2]，因为最后一步要么爬1级要么爬2级
- 空间优化：只用两个变量滚动，O(1) 空间
- 时间 O(n)，空间 O(1)
状态转移：dp[i] = dp[i-1] + dp[i-2]（斐波那契数列）
2. 打家劫舍 (LeetCode 198)
题目：不能偷相邻的房子，求最大金额。
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
int prev2 = nums[0];
int prev1 = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
int cur = max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
- 偷第i家：dp[i-2] + nums[i]
- 不偷第i家：dp[i-1]
3. 打家劫舍 II (LeetCode 213)
题目：房子围成一圈，首尾相邻。
思路：分两种情况：偷第一家（不偷最后一家）/ 不偷第一家（可偷最后一家）
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
if (n == 2) return max(nums[0], nums[1]);
// 偷 [0, n-2] 或 [1, n-1]
return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}
int robRange(vector<int>& nums, int start, int end) {
int prev2 = nums[start];
int prev1 = max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
int cur = max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}4. 最大子数组和 (LeetCode 53)
int maxSubArray(vector<int>& nums) {
int maxSum = nums[0];
int curSum = nums[0];
for (int i = 1; i < nums.size(); i++) {
// 要么接着前面，要么从当前重新开始
curSum = max(nums[i], curSum + nums[i]);
maxSum = max(maxSum, curSum);
}
return maxSum;
}状态转移：dp[i] = max(nums[i], dp[i-1] + nums[i])
二、路径问题
5. 不同路径 (LeetCode 62)
题目：从左上角到右下角有多少条路径（只能向右或向下）。
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 1));
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}空间优化：
int uniquePaths(int m, int n) {
vector<int> dp(n, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j-1];
}
}
return dp[n-1];
}6. 最小路径和 (LeetCode 64)
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) continue;
else if (i == 0) grid[i][j] += grid[i][j-1];
else if (j == 0) grid[i][j] += grid[i-1][j];
else grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
}
}
return grid[m-1][n-1];
}三、字符串DP
7. 最长公共子序列 (LeetCode 1143)
题目：两个字符串的最长公共子序列长度。
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
// dp[i][j] = text1[0..i-1]和text2[0..j-1]的LCS长度
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1[i-1] == text2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}状态转移：
- 相等：dp[i][j] = dp[i-1][j-1] + 1
- 不等：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
8. 编辑距离 (LeetCode 72)
题目：将word1转换成word2的最少操作数（插入、删除、替换）。
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
// dp[i][j] = word1[0..i-1]转换为word2[0..j-1]的最小操作数
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
// 初始化
for (int i = 0; i <= m; i++) dp[i][0] = i; // 删除i个字符
for (int j = 0; j <= n; j++) dp[0][j] = j; // 插入j个字符
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i-1] == word2[j-1]) {
dp[i][j] = dp[i-1][j-1]; // 不操作
} else {
dp[i][j] = 1 + min({
dp[i-1][j], // 删除
dp[i][j-1], // 插入
dp[i-1][j-1] // 替换
});
}
}
}
return dp[m][n];
}9. 最长回文子序列 (LeetCode 516)
int longestPalindromeSubseq(string s) {
int n = s.size();
// dp[i][j] = s[i..j]的最长回文子序列长度
vector<vector<int>> dp(n, vector<int>(n, 0));
// 单个字符是长度为1的回文
for (int i = 0; i < n; i++) dp[i][i] = 1;
// 从短到长枚举
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s[i] == s[j]) {
dp[i][j] = dp[i+1][j-1] + 2;
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][n-1];
}10. 单词拆分 (LeetCode 139)
题目：判断字符串是否可以拆分成字典中的单词。
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
int n = s.size();
// dp[i] = s[0..i-1]能否被拆分
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordSet.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}四、背包问题
11. 0-1背包
问题：n个物品，每个物品只能选一次，背包容量W，求最大价值。
int knapsack01(vector<int>& weights, vector<int>& values, int W) {
int n = weights.size();
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
// 逆序遍历，保证每个物品只用一次
for (int w = W; w >= weights[i]; w--) {
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[W];
}口诀：0-1背包逆序遍历容量
12. 完全背包
问题：每个物品可以选无限次。
int knapsackComplete(vector<int>& weights, vector<int>& values, int W) {
int n = weights.size();
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
// 正序遍历，允许重复选择
for (int w = weights[i]; w <= W; w++) {
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[W];
}口诀：完全背包正序遍历容量
13. 分割等和子集 (LeetCode 416)
题目：判断能否分成两个和相等的子集。
转化：能否选出若干数，和为 sum/2（0-1背包）
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 != 0) return false;
int target = sum / 2;
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int num : nums) {
for (int j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}14. 零钱兑换 (LeetCode 322)
题目：用最少的硬币凑成amount。
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, amount + 1); // 初始化为不可能的大值
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}15. 零钱兑换 II (LeetCode 518)
题目：凑成amount的组合数。
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
// 先遍历硬币（组合问题）
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}组合 vs 排列：
- 组合（无序）：先遍历物品，再遍历容量
- 排列（有序）：先遍历容量，再遍历物品
五、序列DP
16. 最长递增子序列 (LeetCode 300)
// O(n²) DP解法
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1); // dp[i] = 以nums[i]结尾的LIS长度
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxLen = max(maxLen, dp[i]);
}
return maxLen;
}
// O(nlogn) 贪心+二分解法
int lengthOfLIS(vector<int>& nums) {
vector<int> tails; // tails[i] = 长度为i+1的LIS的最小末尾元素
for (int num : nums) {
auto it = lower_bound(tails.begin(), tails.end(), num);
if (it == tails.end()) {
tails.push_back(num);
} else {
*it = num;
}
}
return tails.size();
}17. 乘积最大子数组 (LeetCode 152)
关键：负数乘负数可能变最大，需要同时记录最大值和最小值。
int maxProduct(vector<int>& nums) {
int maxProd = nums[0];
int minProd = nums[0];
int result = nums[0];
for (int i = 1; i < nums.size(); i++) {
if (nums[i] < 0) {
swap(maxProd, minProd);
}
maxProd = max(nums[i], maxProd * nums[i]);
minProd = min(nums[i], minProd * nums[i]);
result = max(result, maxProd);
}
return result;
}六、区间DP
18. 戳气球 (LeetCode 312)
int maxCoins(vector<int>& nums) {
int n = nums.size();
// 添加虚拟边界
vector<int> points(n + 2);
points[0] = points[n + 1] = 1;
for (int i = 1; i <= n; i++) {
points[i] = nums[i - 1];
}
// dp[i][j] = 戳破(i,j)开区间内所有气球的最大硬币数
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
// 从小区间到大区间
for (int len = 3; len <= n + 2; len++) {
for (int i = 0; i + len - 1 <= n + 1; i++) {
int j = i + len - 1;
// 枚举最后一个戳破的气球
for (int k = i + 1; k < j; k++) {
dp[i][j] = max(dp[i][j],
dp[i][k] + dp[k][j] + points[i] * points[k] * points[j]);
}
}
}
return dp[0][n + 1];
}动态规划总结
| 类型 | 经典题目 | 状态定义 |
|---|---|---|
| 线性DP | 爬楼梯、打家劫舍 | dp[i] = 到第i个位置的结果 |
| 路径DP | 不同路径、最小路径和 | dp[i][j] = 到(i,j)的结果 |
| 字符串DP | LCS、编辑距离 | dp[i][j] = s1[0..i]和s2[0..j]的结果 |
| 背包DP | 零钱兑换、分割等和 | dp[j] = 容量为j时的结果 |
| 区间DP | 戳气球 | dp[i][j] = 区间[i,j]的结果 |
DP优化技巧：
- 滚动数组：空间从O(n)降到O(1)
- 状态压缩：将二维dp压缩成一维
- 记忆化搜索：自顶向下的DP
解题口诀：
- 先想暴力递归
- 递归有重复子问题就用DP
- 画表格找规律
贪心算法专题
贪心的核心思想：每一步都做当前最优选择，期望达到全局最优。
贪心与动态规划的区别：
- 贪心：只看眼前，不回头
- DP：考虑所有可能，取最优
1. 买卖股票的最佳时机 (LeetCode 121)
题目：只能买卖一次，求最大利润。
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX;
int maxProfit = 0;
for (int price : prices) {
minPrice = min(minPrice, price);
maxProfit = max(maxProfit, price - minPrice);
}
return maxProfit;
}贪心策略：记录历史最低价，每天计算卖出利润。
2. 买卖股票的最佳时机 II (LeetCode 122)
题目：可以多次买卖，求最大利润。
int maxProfit(vector<int>& prices) {
int profit = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}贪心策略：只要明天比今天贵，就今天买明天卖。
3. 跳跃游戏 (LeetCode 55)
题目：判断能否跳到最后一个位置。
bool canJump(vector<int>& nums) {
int maxReach = 0; // 能到达的最远位置
for (int i = 0; i < nums.size(); i++) {
if (i > maxReach) return false; // 到不了当前位置
maxReach = max(maxReach, i + nums[i]);
}
return true;
}贪心策略：不断更新能到达的最远位置。
4. 跳跃游戏 II (LeetCode 45)
题目：跳到最后位置的最少跳跃次数。
int jump(vector<int>& nums) {
int jumps = 0;
int curEnd = 0; // 当前跳跃能到达的边界
int curFarthest = 0; // 当前能到达的最远位置
for (int i = 0; i < nums.size() - 1; i++) {
curFarthest = max(curFarthest, i + nums[i]);
if (i == curEnd) { // 到达当前跳跃的边界，必须跳了
jumps++;
curEnd = curFarthest;
}
}
return jumps;
}贪心策略：在每次跳跃范围内，选择能跳得最远的位置。
5. 划分字母区间 (LeetCode 763)
题目：把字符串划分成尽可能多的片段，同一字母最多出现在一个片段中。
vector<int> partitionLabels(string s) {
// 记录每个字母最后出现的位置
vector<int> last(26);
for (int i = 0; i < s.size(); i++) {
last[s[i] - 'a'] = i;
}
vector<int> result;
int start = 0, end = 0;
for (int i = 0; i < s.size(); i++) {
end = max(end, last[s[i] - 'a']);
if (i == end) { // 当前片段结束
result.push_back(end - start + 1);
start = end + 1;
}
}
return result;
}贪心策略：扩展当前区间到所有字母都满足条件。
6. 合并区间 (LeetCode 56)
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
for (auto& interval : intervals) {
if (merged.empty() || merged.back()[1] < interval[0]) {
// 不重叠，直接加入
merged.push_back(interval);
} else {
// 重叠，合并
merged.back()[1] = max(merged.back()[1], interval[1]);
}
}
return merged;
}7. 无重叠区间 (LeetCode 435)
题目：移除最少的区间，使剩余区间互不重叠。
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
// 按结束时间排序
sort(intervals.begin(), intervals.end(),
[](auto& a, auto& b) { return a[1] < b[1]; });
int count = 1; // 不重叠区间数量
int end = intervals[0][1];
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] >= end) { // 不重叠
count++;
end = intervals[i][1];
}
}
return intervals.size() - count;
}贪心策略：优先保留结束早的区间，给后面留更多空间。
8. 用最少数量的箭引爆气球 (LeetCode 452)
题目：用最少的箭射爆所有气球。
int findMinArrowPoints(vector<vector<int>>& points) {
if (points.empty()) return 0;
// 按结束位置排序
sort(points.begin(), points.end(),
[](auto& a, auto& b) { return a[1] < b[1]; });
int arrows = 1;
int arrowPos = points[0][1];
for (int i = 1; i < points.size(); i++) {
if (points[i][0] > arrowPos) { // 当前气球无法被射中
arrows++;
arrowPos = points[i][1];
}
}
return arrows;
}9. 分发饼干 (LeetCode 455)
题目：每个孩子有胃口g[i]，每块饼干大小s[j]，求最多能满足几个孩子。
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int child = 0, cookie = 0;
while (child < g.size() && cookie < s.size()) {
if (s[cookie] >= g[child]) {
child++; // 满足了一个孩子
}
cookie++; // 饼干用掉或太小
}
return child;
}贪心策略：用最小的饼干满足胃口最小的孩子。
10. 分发糖果 (LeetCode 135)
题目：每个孩子至少1个糖果，评分高的比相邻孩子糖果多。
int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> candies(n, 1);
// 从左到右：比左边评分高的多给一个
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// 从右到左：比右边评分高的也要多
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = max(candies[i], candies[i + 1] + 1);
}
}
return accumulate(candies.begin(), candies.end(), 0);
}贪心策略：两次遍历，分别处理左右两个方向的约束。
11. 加油站 (LeetCode 134)
题目：能否从某个加油站出发环绕一圈。
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int totalTank = 0;
int currTank = 0;
int startStation = 0;
for (int i = 0; i < gas.size(); i++) {
int diff = gas[i] - cost[i];
totalTank += diff;
currTank += diff;
if (currTank < 0) {
// 从当前站无法到达下一站，换起点
startStation = i + 1;
currTank = 0;
}
}
return totalTank >= 0 ? startStation : -1;
}贪心策略：如果从A到不了B，那A到B之间的任何站都到不了B。
12. 任务调度器 (LeetCode 621)
题目：CPU执行任务，相同任务需间隔n个时间单位。
int leastInterval(vector<char>& tasks, int n) {
vector<int> count(26, 0);
int maxCount = 0;
int maxCountTasks = 0;
for (char task : tasks) {
count[task - 'A']++;
if (count[task - 'A'] > maxCount) {
maxCount = count[task - 'A'];
maxCountTasks = 1;
} else if (count[task - 'A'] == maxCount) {
maxCountTasks++;
}
}
// 最少时间 = (maxCount-1) * (n+1) + maxCountTasks
// 或者就是任务总数（没有空闲）
int result = (maxCount - 1) * (n + 1) + maxCountTasks;
return max(result, (int)tasks.size());
}图解：假设最多的任务是A出现3次，n=2
A _ _ A _ _ A填充其他任务到空位。
13. 会议室 II (LeetCode 253)
题目：至少需要多少个会议室。
int minMeetingRooms(vector<vector<int>>& intervals) {
vector<pair<int, int>> events;
for (auto& interval : intervals) {
events.push_back({interval[0], 1}); // 开始
events.push_back({interval[1], -1}); // 结束
}
sort(events.begin(), events.end());
int rooms = 0, maxRooms = 0;
for (auto& [time, delta] : events) {
rooms += delta;
maxRooms = max(maxRooms, rooms);
}
return maxRooms;
}贪心策略：用差分思想，统计同时进行的最大会议数。
14. 贪心算法总结
| 题目类型 | 贪心策略 | 例题 |
|---|---|---|
| 股票问题 | 记录历史最优 | 买卖股票 |
| 区间问题 | 按端点排序 | 合并区间、无重叠区间 |
| 跳跃问题 | 更新最远距离 | 跳跃游戏 |
| 分配问题 | 排序后匹配 | 分发饼干 |
贪心解题套路：
- 排序：通常需要先排序
- 局部最优：每一步选当前最优
- 证明正确性：反证法或交换论证
判断能否用贪心：
- 问题有”最优子结构”
- 局部最优能推出全局最优
- 如果不确定，先用DP
贪心口诀：
- 区间问题按端点排序
- 每一步做当前最优选择
- 不回头，不后悔
栈与队列专题
📖 栈（LIFO）和队列（FIFO）是最基础的数据结构，但能解决很多巧妙的问题。
本章重点：单调栈——面试高频，必须掌握！
🧠 类比速记
| 结构 | 类比 | 一句话 |
|---|---|---|
| 栈 | 叠盘子 | 后放的先拿（LIFO） |
| 队列 | 排队买票 | 先来先服务（FIFO） |
| 单调栈 | 排队看演唱会 | 矮的看不到就走人 |
| 单调队列 | 滑动的身高榜 | 窗口内实时维护最值 |
一、栈的基础应用
1. 有效的括号 (LeetCode 20)
bool isValid(string s) {
stack<char> stk;
unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
for (char c : s) {
if (pairs.count(c)) { // 右括号
if (stk.empty() || stk.top() != pairs[c]) {
return false;
}
stk.pop();
} else { // 左括号
stk.push(c);
}
}
return stk.empty();
}2. 最小栈 (LeetCode 155)
题目：设计一个栈，支持O(1)时间获取最小值。
class MinStack {
stack<int> dataStack;
stack<int> minStack;
public:
MinStack() {
minStack.push(INT_MAX);
}
void push(int val) {
dataStack.push(val);
minStack.push(min(minStack.top(), val));
}
void pop() {
dataStack.pop();
minStack.pop();
}
int top() {
return dataStack.top();
}
int getMin() {
return minStack.top();
}
};核心思路：辅助栈同步记录当前最小值。
3. 逆波兰表达式求值 (LeetCode 150)
int evalRPN(vector<string>& tokens) {
stack<int> stk;
for (const string& token : tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
int b = stk.top(); stk.pop();
int a = stk.top(); stk.pop();
if (token == "+") stk.push(a + b);
else if (token == "-") stk.push(a - b);
else if (token == "*") stk.push(a * b);
else stk.push(a / b);
} else {
stk.push(stoi(token));
}
}
return stk.top();
}4. 基本计算器 II (LeetCode 227)
题目：实现包含+、-、*、/的计算器。
int calculate(string s) {
stack<int> stk;
int num = 0;
char lastOp = '+';
for (int i = 0; i < s.size(); i++) {
char c = s[i];
if (isdigit(c)) {
num = num * 10 + (c - '0');
}
if ((!isdigit(c) && c != ' ') || i == s.size() - 1) {
if (lastOp == '+') {
stk.push(num);
} else if (lastOp == '-') {
stk.push(-num);
} else if (lastOp == '*') {
int top = stk.top(); stk.pop();
stk.push(top * num);
} else if (lastOp == '/') {
int top = stk.top(); stk.pop();
stk.push(top / num);
}
lastOp = c;
num = 0;
}
}
int result = 0;
while (!stk.empty()) {
result += stk.top();
stk.pop();
}
return result;
}5. 简化路径 (LeetCode 71)
string simplifyPath(string path) {
vector<string> stk;
stringstream ss(path);
string token;
while (getline(ss, token, '/')) {
if (token == "" || token == ".") {
continue;
} else if (token == "..") {
if (!stk.empty()) stk.pop_back();
} else {
stk.push_back(token);
}
}
string result;
for (const string& dir : stk) {
result += "/" + dir;
}
return result.empty() ? "/" : result;
}二、单调栈
🎯 单调栈是面试高频考点！ 接雨水、每日温度、柱状图最大矩形都要用。
🤔 为什么需要单调栈？
问题：给一个数组，求每个元素右边第一个比它大的数。
暴力解法：对每个元素，向右扫描找第一个更大的 → O(n²)
能不能优化到 O(n)？ 这就需要单调栈！
🧠 类比：排队看演唱会
想象一群人排队看演唱会，每个人只能看到前面第一个比自己高的人的后脑勺。
身高: 170 160 175 165 180
编号: A B C D E
站位（从左到右面向舞台）：
A(170) - B(160) - C(175) - D(165) - E(180)
E 进场（180）：
- D(165) 被 E 挡住了 → D 看到的第一个更高的是 E
- C(175) 被 E 挡住了 → C 看到的第一个更高的是 E
- B 已经被 C 挡了，不用管
- A 已经被 C 挡了，不用管规律：新人来了，把比他矮的都「赶走」（他们已经找到答案了）
📝 单调栈模板
stack<int> stk; // 存下标，栈内元素单调递减
for (int i = 0; i < n; i++) {
// 当前元素比栈顶大，栈顶的「下一个更大」就是当前元素
while (!stk.empty() && nums[i] > nums[stk.top()]) {
int idx = stk.top();
stk.pop();
answer[idx] = nums[i]; // 栈顶元素的答案
}
stk.push(i);
}口诀：单调递减栈，遇大出栈，栈顶找到答案
6. 每日温度 (LeetCode 739) ⭐ 必刷
题目：找出每一天需要等几天才能遇到更高的温度。
🧠 生活类比
你每天记录气温，想知道「再过几天能变暖和」。
- 今天 20°，明天 25° → 等 1 天
- 今天 25°，明天 20°，后天 30° → 等 2 天
- 如果后面都没更高的 → 等 0 天
📊 图示演示
温度: [73, 74, 75, 71, 69, 72, 76, 73]
下标: 0 1 2 3 4 5 6 7
栈变化过程（存下标）：
i=0: 栈空，push(0) 栈: [0]
i=1: 74>73，pop(0)，ans[0]=1 栈: []，push(1) → [1]
i=2: 75>74，pop(1)，ans[1]=1 栈: []，push(2) → [2]
i=3: 71<75，push(3) 栈: [2,3]
i=4: 69<71，push(4) 栈: [2,3,4]
i=5: 72>69，pop(4)，ans[4]=1 栈: [2,3]
72>71，pop(3)，ans[3]=2 栈: [2]
72<75，push(5) 栈: [2,5]
i=6: 76>72，pop(5)，ans[5]=1 栈: [2]
76>75，pop(2)，ans[2]=4 栈: []，push(6) → [6]
i=7: 73<76，push(7) 栈: [6,7]
结果: [1, 1, 4, 2, 1, 1, 0, 0]💻 代码实现
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> answer(n, 0); // 默认0表示后面没有更高温度
stack<int> stk; // 存储下标（不是温度！）
for (int i = 0; i < n; i++) {
// 当前温度比栈顶高 → 栈顶等到了更高温度
while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
int prevIndex = stk.top();
stk.pop();
answer[prevIndex] = i - prevIndex; // 等待天数 = 当前下标 - 栈顶下标
}
stk.push(i); // 当前下标入栈
}
return answer; // 留在栈里的元素，answer 保持默认值 0
}⚠️ 易错点
- 栈里存下标还是值？ 存下标！因为要计算距离
- 忘记初始化 answer：默认值应该是 0（没有更高温度）
- while 写成 if：可能连续出栈多个元素
📝 面试怎么答
面试官：讲一下每日温度的思路？
答：这道题本质是求每个元素右边第一个更大元素的距离。
- 用单调递减栈，栈内存下标
- 遍历数组，如果当前温度比栈顶高，说明栈顶找到了答案
- 出栈并记录距离，然后当前元素入栈
- 每个元素最多入栈出栈一次，时间 O(n)，空间 O(n)
7. 下一个更大元素 I (LeetCode 496)
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> nextGreater;
stack<int> stk;
// 用nums2构建每个元素的"下一个更大元素"
for (int num : nums2) {
while (!stk.empty() && num > stk.top()) {
nextGreater[stk.top()] = num;
stk.pop();
}
stk.push(num);
}
vector<int> result;
for (int num : nums1) {
result.push_back(nextGreater.count(num) ? nextGreater[num] : -1);
}
return result;
}8. 柱状图中最大的矩形 (LeetCode 84)
题目：找出柱状图中能勾勒出的最大矩形面积。
int largestRectangleArea(vector<int>& heights) {
stack<int> stk;
int maxArea = 0;
int n = heights.size();
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i];
while (!stk.empty() && h < heights[stk.top()]) {
int height = heights[stk.top()];
stk.pop();
int width = stk.empty() ? i : (i - stk.top() - 1);
maxArea = max(maxArea, height * width);
}
stk.push(i);
}
return maxArea;
}核心思路：
- 维护单调递增栈
- 遇到更矮的柱子，计算栈顶柱子能形成的最大矩形
- 栈顶柱子的宽度 = 当前位置 – 新栈顶位置 – 1
9. 接雨水 (LeetCode 42) – 单调栈解法
int trap(vector<int>& height) {
stack<int> stk;
int water = 0;
for (int i = 0; i < height.size(); i++) {
while (!stk.empty() && height[i] > height[stk.top()]) {
int bottom = stk.top();
stk.pop();
if (stk.empty()) break;
int left = stk.top();
int h = min(height[left], height[i]) - height[bottom];
int w = i - left - 1;
water += h * w;
}
stk.push(i);
}
return water;
}三、队列应用
10. 用栈实现队列 (LeetCode 232)
class MyQueue {
stack<int> input;
stack<int> output;
void transfer() {
while (!input.empty()) {
output.push(input.top());
input.pop();
}
}
public:
void push(int x) {
input.push(x);
}
int pop() {
if (output.empty()) transfer();
int val = output.top();
output.pop();
return val;
}
int peek() {
if (output.empty()) transfer();
return output.top();
}
bool empty() {
return input.empty() && output.empty();
}
};11. 用队列实现栈 (LeetCode 225)
class MyStack {
queue<int> q;
public:
void push(int x) {
q.push(x);
// 把新元素转到队首
for (int i = 0; i < q.size() - 1; i++) {
q.push(q.front());
q.pop();
}
}
int pop() {
int val = q.front();
q.pop();
return val;
}
int top() {
return q.front();
}
bool empty() {
return q.empty();
}
};四、单调队列
12. 滑动窗口最大值 (LeetCode 239)
题目：返回滑动窗口中的最大值。
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq; // 存储下标，单调递减
vector<int> result;
for (int i = 0; i < nums.size(); i++) {
// 移除窗口外的元素
if (!dq.empty() && dq.front() < i - k + 1) {
dq.pop_front();
}
// 保持单调递减：移除比当前小的元素
while (!dq.empty() && nums[dq.back()] < nums[i]) {
dq.pop_back();
}
dq.push_back(i);
// 窗口形成后记录最大值
if (i >= k - 1) {
result.push_back(nums[dq.front()]);
}
}
return result;
}口诀：单调递减双端队列，队首就是最大值。
五、栈与队列总结
| 题目类型 | 数据结构 | 典型题目 |
|---|---|---|
| 括号匹配 | 栈 | 有效的括号 |
| 表达式计算 | 栈 | 逆波兰表达式、基本计算器 |
| 下一个更大元素 | 单调栈 | 每日温度、柱状图最大矩形 |
| 滑动窗口最值 | 单调队列(deque) | 滑动窗口最大值 |
| 栈/队列互相实现 | 两个栈/队列 | 用栈实现队列 |
单调栈模板：
// 找下一个更大元素
stack<int> stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && nums[i] > nums[stk.top()]) {
int idx = stk.top();
stk.pop();
// nums[idx]的下一个更大元素是nums[i]
}
stk.push(i);
}单调队列模板：
// 滑动窗口最大值
deque<int> dq;
for (int i = 0; i < n; i++) {
// 1. 移除窗口外元素
if (!dq.empty() && dq.front() < i - k + 1) {
dq.pop_front();
}
// 2. 保持单调性
while (!dq.empty() && nums[dq.back()] < nums[i]) {
dq.pop_back();
}
// 3. 加入当前元素
dq.push_back(i);
// 4. 队首就是窗口最值
}记忆口诀：
- 栈：后进先出，匹配问题
- 单调栈：找下一个更大/更小
- 单调队列：滑动窗口最值
堆与优先队列专题
堆（Heap）是一种特殊的完全二叉树，常用于实现优先队列，解决TopK、合并有序序列等问题。
堆的基础
大顶堆：父节点 ≥ 子节点，堆顶最大
小顶堆：父节点 ≤ 子节点，堆顶最小
C++ STL：priority_queue
- 默认是大顶堆
- 小顶堆：
priority_queue<int, vector<int>, greater<int>>
// 大顶堆
priority_queue<int> maxHeap;
// 小顶堆
priority_queue<int, vector<int>, greater<int>> minHeap;
// 自定义比较
auto cmp = [](int a, int b) { return a > b; }; // 小顶堆
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);1. 数组中的第K个最大元素 (LeetCode 215)
方法一：小顶堆（维护K个最大元素）
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int num : nums) {
minHeap.push(num);
if (minHeap.size() > k) {
minHeap.pop(); // 弹出最小的
}
}
return minHeap.top(); // 第K大就是堆顶
}时间复杂度：O(nlogk)
方法二：快速选择（平均O(n)）
int findKthLargest(vector<int>& nums, int k) {
int target = nums.size() - k; // 转换为第target小
return quickSelect(nums, 0, nums.size() - 1, target);
}
int quickSelect(vector<int>& nums, int left, int right, int target) {
int pivotIndex = partition(nums, left, right);
if (pivotIndex == target) {
return nums[pivotIndex];
} else if (pivotIndex < target) {
return quickSelect(nums, pivotIndex + 1, right, target);
} else {
return quickSelect(nums, left, pivotIndex - 1, target);
}
}
int partition(vector<int>& nums, int left, int right) {
int pivot = nums[right];
int i = left;
for (int j = left; j < right; j++) {
if (nums[j] < pivot) {
swap(nums[i], nums[j]);
i++;
}
}
swap(nums[i], nums[right]);
return i;
}2. 前 K 个高频元素 (LeetCode 347)
vector<int> topKFrequent(vector<int>& nums, int k) {
// 统计频率
unordered_map<int, int> count;
for (int num : nums) count[num]++;
// 小顶堆，按频率排序
auto cmp = [&count](int a, int b) {
return count[a] > count[b]; // 频率小的在堆顶
};
priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
for (auto& [num, freq] : count) {
pq.push(num);
if (pq.size() > k) pq.pop();
}
vector<int> result;
while (!pq.empty()) {
result.push_back(pq.top());
pq.pop();
}
return result;
}3. 合并K个升序链表 (LeetCode 23)
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto cmp = [](ListNode* a, ListNode* b) {
return a->val > b->val; // 小顶堆
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
// 初始化：每个链表的头节点入堆
for (ListNode* list : lists) {
if (list) pq.push(list);
}
ListNode dummy(0);
ListNode* tail = &dummy;
while (!pq.empty()) {
ListNode* minNode = pq.top();
pq.pop();
tail->next = minNode;
tail = tail->next;
if (minNode->next) {
pq.push(minNode->next);
}
}
return dummy.next;
}时间复杂度：O(nlogk)，n是所有节点数，k是链表数
4. 数据流的中位数 (LeetCode 295)
核心思路：用两个堆
- 大顶堆：存较小的一半
- 小顶堆：存较大的一半
- 中位数 = 两堆顶的平均值
class MedianFinder {
priority_queue<int> maxHeap; // 左边（较小的一半）
priority_queue<int, vector<int>, greater<int>> minHeap; // 右边（较大的一半）
public:
void addNum(int num) {
// 先加入左边（大顶堆）
maxHeap.push(num);
// 把左边最大的给右边
minHeap.push(maxHeap.top());
maxHeap.pop();
// 保持平衡：左边可以比右边多1个
if (maxHeap.size() < minHeap.size()) {
maxHeap.push(minHeap.top());
minHeap.pop();
}
}
double findMedian() {
if (maxHeap.size() > minHeap.size()) {
return maxHeap.top();
}
return (maxHeap.top() + minHeap.top()) / 2.0;
}
};图解：
数据流: 1, 5, 2, 8, 3
大顶堆(左) | 小顶堆(右)
1 |
1 | 5
1,2 | 5
1,2 | 5,8
1,2,3 | 5,8
中位数 = maxHeap.top() = 35. 丑数 II (LeetCode 264)
题目：找第n个丑数（只包含因子2,3,5）。
int nthUglyNumber(int n) {
priority_queue<long, vector<long>, greater<long>> pq;
unordered_set<long> seen;
pq.push(1);
seen.insert(1);
vector<int> primes = {2, 3, 5};
long ugly = 1;
for (int i = 0; i < n; i++) {
ugly = pq.top();
pq.pop();
for (int prime : primes) {
long next = ugly * prime;
if (!seen.count(next)) {
seen.insert(next);
pq.push(next);
}
}
}
return ugly;
}更优解法：三指针DP：
int nthUglyNumber(int n) {
vector<int> ugly(n);
ugly[0] = 1;
int p2 = 0, p3 = 0, p5 = 0;
for (int i = 1; i < n; i++) {
int next2 = ugly[p2] * 2;
int next3 = ugly[p3] * 3;
int next5 = ugly[p5] * 5;
ugly[i] = min({next2, next3, next5});
if (ugly[i] == next2) p2++;
if (ugly[i] == next3) p3++;
if (ugly[i] == next5) p5++;
}
return ugly[n - 1];
}6. 会议室 II (LeetCode 253)
题目：求最少需要多少个会议室。
int minMeetingRooms(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end()); // 按开始时间排序
// 小顶堆，存储会议结束时间
priority_queue<int, vector<int>, greater<int>> endTimes;
for (auto& interval : intervals) {
// 如果当前会议开始时间 >= 最早结束时间，可以复用会议室
if (!endTimes.empty() && interval[0] >= endTimes.top()) {
endTimes.pop();
}
endTimes.push(interval[1]);
}
return endTimes.size();
}7. 最小的k个数 (LeetCode 剑指Offer 40)
vector<int> getLeastNumbers(vector<int>& arr, int k) {
if (k == 0) return {};
// 大顶堆，维护k个最小
priority_queue<int> maxHeap;
for (int num : arr) {
maxHeap.push(num);
if (maxHeap.size() > k) {
maxHeap.pop();
}
}
vector<int> result;
while (!maxHeap.empty()) {
result.push_back(maxHeap.top());
maxHeap.pop();
}
return result;
}8. 根据字符出现频率排序 (LeetCode 451)
string frequencySort(string s) {
unordered_map<char, int> count;
for (char c : s) count[c]++;
// 大顶堆，按频率排序
priority_queue<pair<int, char>> pq;
for (auto& [c, freq] : count) {
pq.push({freq, c});
}
string result;
while (!pq.empty()) {
auto [freq, c] = pq.top();
pq.pop();
result += string(freq, c);
}
return result;
}9. 有序矩阵中第K小的元素 (LeetCode 378)
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
auto cmp = [&matrix](pair<int,int>& a, pair<int,int>& b) {
return matrix[a.first][a.second] > matrix[b.first][b.second];
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);
// 第一列入堆
for (int i = 0; i < n; i++) {
pq.push({i, 0});
}
int result = 0;
for (int i = 0; i < k; i++) {
auto [row, col] = pq.top();
pq.pop();
result = matrix[row][col];
if (col + 1 < n) {
pq.push({row, col + 1});
}
}
return result;
}10. 堆排序实现
class HeapSort {
public:
void heapSort(vector<int>& nums) {
int n = nums.size();
// 建堆（从最后一个非叶子节点开始）
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(nums, n, i);
}
// 排序
for (int i = n - 1; i > 0; i--) {
swap(nums[0], nums[i]); // 最大值放到末尾
heapify(nums, i, 0); // 调整剩余堆
}
}
private:
void heapify(vector<int>& nums, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && nums[left] > nums[largest]) {
largest = left;
}
if (right < n && nums[right] > nums[largest]) {
largest = right;
}
if (largest != i) {
swap(nums[i], nums[largest]);
heapify(nums, n, largest);
}
}
};堆与优先队列总结
| 问题类型 | 堆类型 | 例题 |
|---|---|---|
| 第K大 | 小顶堆（维护K个） | 第K大元素 |
| 第K小 | 大顶堆（维护K个） | 最小的K个数 |
| 合并有序序列 | 小顶堆 | 合并K个链表 |
| 动态中位数 | 大顶堆+小顶堆 | 数据流中位数 |
| TopK频率 | 小顶堆 | 前K高频元素 |
选择堆类型口诀：
- 找大用小堆，找小用大堆
- 维护TopK个最大 → 小顶堆（弹出最小的）
- 维护TopK个最小 → 大顶堆（弹出最大的）
C++ priority_queue 要点：
// 大顶堆（默认）
priority_queue<int> maxHeap;
// 小顶堆
priority_queue<int, vector<int>, greater<int>> minHeap;
// 自定义类型
auto cmp = [](const T& a, const T& b) { return a.val > b.val; };
priority_queue<T, vector<T>, decltype(cmp)> pq(cmp);时间复杂度：
- 插入/删除：O(logn)
- 获取堆顶：O(1)
- 建堆：O(n)
二分查找专题
二分查找的核心思想：通过比较中间元素，每次排除一半的搜索空间。
二分查找模板
模板一：标准二分（查找精确值）
int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}模板二：左边界（第一个>=target的位置）
int lowerBound(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left; // 第一个 >= target 的位置
}模板三：右边界（最后一个<=target的位置）
int upperBound(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1; // 最后一个 <= target 的位置
}口诀：左闭右开找左边界，左开右闭找右边界。
1. 二分查找 (LeetCode 704)
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}2. 在排序数组中查找元素的第一个和最后一个位置 (LeetCode 34)
vector<int> searchRange(vector<int>& nums, int target) {
int first = findFirst(nums, target);
if (first == -1) return {-1, -1};
int last = findLast(nums, target);
return {first, last};
}
int findFirst(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
// 找到target，继续往左找
if (mid == 0 || nums[mid - 1] != target) {
return mid;
}
right = mid - 1;
}
}
return -1;
}
int findLast(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
// 找到target，继续往右找
if (mid == nums.size() - 1 || nums[mid + 1] != target) {
return mid;
}
left = mid + 1;
}
}
return -1;
}3. 搜索旋转排序数组 (LeetCode 33)
题目：在旋转过的有序数组中查找target。
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
// 判断哪半部分是有序的
if (nums[left] <= nums[mid]) {
// 左半部分有序
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
// 右半部分有序
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}核心思路：先判断哪半部分有序，再判断target在不在有序的那半部分。
4. 寻找旋转排序数组中的最小值 (LeetCode 153)
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
// 最小值在右半部分
left = mid + 1;
} else {
// 最小值在左半部分（包括mid）
right = mid;
}
}
return nums[left];
}5. 搜索二维矩阵 (LeetCode 74)
题目：每行有序，每行第一个数大于上一行最后一个数。
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int left = 0, right = m * n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int midVal = matrix[mid / n][mid % n];
if (midVal == target) return true;
else if (midVal < target) left = mid + 1;
else right = mid - 1;
}
return false;
}关键：把二维数组展平成一维，mid对应位置是 (mid/n, mid%n)。
6. 搜索二维矩阵 II (LeetCode 240)
题目：每行每列递增，但不保证行间递增。
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int row = 0, col = n - 1; // 从右上角开始
while (row < m && col >= 0) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
col--; // 当前列太大，向左移
} else {
row++; // 当前行太小，向下移
}
}
return false;
}核心思路：从右上角（或左下角）开始，利用行列递增性质。
7. 寻找两个正序数组的中位数 (LeetCode 4)
题目：O(log(m+n))时间复杂度。
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// 确保nums1是较短的数组
if (nums1.size() > nums2.size()) {
swap(nums1, nums2);
}
int m = nums1.size(), n = nums2.size();
int left = 0, right = m;
while (left <= right) {
int i = (left + right) / 2;
int j = (m + n + 1) / 2 - i;
int nums1LeftMax = (i == 0) ? INT_MIN : nums1[i - 1];
int nums1RightMin = (i == m) ? INT_MAX : nums1[i];
int nums2LeftMax = (j == 0) ? INT_MIN : nums2[j - 1];
int nums2RightMin = (j == n) ? INT_MAX : nums2[j];
if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
// 找到正确的分割
int leftMax = max(nums1LeftMax, nums2LeftMax);
int rightMin = min(nums1RightMin, nums2RightMin);
if ((m + n) % 2 == 0) {
return (leftMax + rightMin) / 2.0;
} else {
return leftMax;
}
} else if (nums1LeftMax > nums2RightMin) {
right = i - 1;
} else {
left = i + 1;
}
}
return 0;
}8. 寻找峰值 (LeetCode 162)
题目：峰值是比左右邻居都大的元素。
int findPeakElement(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
// 峰值在左边（包括mid）
right = mid;
} else {
// 峰值在右边
left = mid + 1;
}
}
return left;
}核心思路：往更高的方向走，一定能找到峰值。
9. x的平方根 (LeetCode 69)
int mySqrt(int x) {
if (x == 0) return 0;
long left = 1, right = x;
while (left <= right) {
long mid = left + (right - left) / 2;
if (mid * mid == x) {
return mid;
} else if (mid * mid < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right; // 返回right（最后一个平方<=x的数）
}10. 有效的完全平方数 (LeetCode 367)
bool isPerfectSquare(int num) {
long left = 1, right = num;
while (left <= right) {
long mid = left + (right - left) / 2;
long square = mid * mid;
if (square == num) return true;
else if (square < num) left = mid + 1;
else right = mid - 1;
}
return false;
}11. 在排序数组中查找数字出现次数
int countTarget(vector<int>& nums, int target) {
// 使用STL
auto lower = lower_bound(nums.begin(), nums.end(), target);
auto upper = upper_bound(nums.begin(), nums.end(), target);
return upper - lower;
}12. 搜索插入位置 (LeetCode 35)
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}13. 分割数组的最大值 (LeetCode 410)
题目：将数组分成k个子数组，使得各子数组的和的最大值最小。
核心思路：二分答案
int splitArray(vector<int>& nums, int k) {
int left = *max_element(nums.begin(), nums.end());
int right = accumulate(nums.begin(), nums.end(), 0);
while (left < right) {
int mid = left + (right - left) / 2;
if (canSplit(nums, k, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
bool canSplit(vector<int>& nums, int k, int maxSum) {
int count = 1;
int curSum = 0;
for (int num : nums) {
if (curSum + num > maxSum) {
count++;
curSum = num;
} else {
curSum += num;
}
}
return count <= k;
}14. 爱吃香蕉的珂珂 (LeetCode 875)
题目：在h小时内吃完所有香蕉，求最小速度。
int minEatingSpeed(vector<int>& piles, int h) {
int left = 1;
int right = *max_element(piles.begin(), piles.end());
while (left < right) {
int mid = left + (right - left) / 2;
if (canFinish(piles, h, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
bool canFinish(vector<int>& piles, int h, int speed) {
int hours = 0;
for (int pile : piles) {
hours += (pile + speed - 1) / speed; // 向上取整
}
return hours <= h;
}二分查找总结
| 题目类型 | 二分对象 | 典型题目 |
|---|---|---|
| 有序数组查找 | 下标 | 二分查找、搜索范围 |
| 旋转数组 | 下标 | 搜索旋转排序数组 |
| 矩阵搜索 | 展平下标或坐标 | 搜索二维矩阵 |
| 求平方根 | 数值 | x的平方根 |
| 二分答案 | 答案值 | 分割数组、吃香蕉 |
二分查找要点：
- 循环条件：
left <= right：闭区间 [left, right]left < right：左闭右开 [left, right)
- 取中间值：
mid = left + (right - left) / 2：防止溢出
- 边界更新：
- 找左边界：
right = mid - 找右边界：
left = mid + 1
- 二分答案：
- 对答案的范围二分，用check函数验证
STL二分函数：
lower_bound(a, a+n, x) // 第一个 >= x 的位置
upper_bound(a, a+n, x) // 第一个 > x 的位置
binary_search(a, a+n, x) // 是否存在x口诀：
- 单调性是二分的前提
- 找不到精确值就二分答案
- left/right的更新决定找左边界还是右边界
图论专题
图论是面试中较难的部分，核心是掌握BFS/DFS遍历和拓扑排序。
图的表示
邻接矩阵
// n个节点的图
vector<vector<int>> graph(n, vector<int>(n, 0));
graph[u][v] = 1; // u到v有边邻接表（更常用）
// n个节点的图
vector<vector<int>> graph(n);
graph[u].push_back(v); // u到v有边一、图的遍历
1. 岛屿数量 (LeetCode 200)
题目：计算二维网格中岛屿的数量。
class Solution {
int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
}
private:
void dfs(vector<vector<char>>& grid, int row, int col) {
int m = grid.size(), n = grid[0].size();
if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] != '1') {
return;
}
grid[row][col] = '0'; // 标记已访问
for (auto& dir : dirs) {
dfs(grid, row + dir[0], col + dir[1]);
}
}
};BFS解法：
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
int count = 0;
int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
count++;
queue<pair<int, int>> q;
q.push({i, j});
grid[i][j] = '0';
while (!q.empty()) {
auto [row, col] = q.front();
q.pop();
for (auto& dir : dirs) {
int nr = row + dir[0];
int nc = col + dir[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == '1') {
q.push({nr, nc});
grid[nr][nc] = '0';
}
}
}
}
}
}
return count;
}2. 岛屿的最大面积 (LeetCode 695)
class Solution {
int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int maxArea = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
maxArea = max(maxArea, dfs(grid, i, j));
}
}
}
return maxArea;
}
private:
int dfs(vector<vector<int>>& grid, int row, int col) {
int m = grid.size(), n = grid[0].size();
if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] != 1) {
return 0;
}
grid[row][col] = 0; // 标记已访问
int area = 1;
for (auto& dir : dirs) {
area += dfs(grid, row + dir[0], col + dir[1]);
}
return area;
}
};3. 被围绕的区域 (LeetCode 130)
题目：将被’X’包围的’O’转换为’X’（边界上的’O’不算被围绕）。
class Solution {
public:
void solve(vector<vector<char>>& board) {
int m = board.size(), n = board[0].size();
// 从边界开始DFS，标记不被围绕的'O'
for (int i = 0; i < m; i++) {
dfs(board, i, 0);
dfs(board, i, n - 1);
}
for (int j = 0; j < n; j++) {
dfs(board, 0, j);
dfs(board, m - 1, j);
}
// 把'#'改回'O'，把剩余的'O'改成'X'
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
} else if (board[i][j] == '#') {
board[i][j] = 'O';
}
}
}
}
private:
void dfs(vector<vector<char>>& board, int row, int col) {
int m = board.size(), n = board[0].size();
if (row < 0 || row >= m || col < 0 || col >= n || board[row][col] != 'O') {
return;
}
board[row][col] = '#'; // 临时标记
dfs(board, row + 1, col);
dfs(board, row - 1, col);
dfs(board, row, col + 1);
dfs(board, row, col - 1);
}
};4. 腐烂的橘子 (LeetCode 994)
题目：每分钟腐烂的橘子会感染相邻的新鲜橘子，求全部腐烂的最少时间。
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
queue<pair<int, int>> q;
int fresh = 0;
// 初始化：找到所有腐烂橘子和新鲜橘子数量
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
q.push({i, j});
} else if (grid[i][j] == 1) {
fresh++;
}
}
}
if (fresh == 0) return 0;
int minutes = 0;
int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while (!q.empty()) {
int size = q.size();
bool rotted = false;
for (int i = 0; i < size; i++) {
auto [row, col] = q.front();
q.pop();
for (auto& dir : dirs) {
int nr = row + dir[0];
int nc = col + dir[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
grid[nr][nc] = 2;
q.push({nr, nc});
fresh--;
rotted = true;
}
}
}
if (rotted) minutes++;
}
return fresh == 0 ? minutes : -1;
}二、拓扑排序
5. 课程表 (LeetCode 207)
题目：判断是否可能完成所有课程（检测有向图中是否有环）。
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> inDegree(numCourses, 0);
vector<vector<int>> graph(numCourses);
// 建图
for (auto& pre : prerequisites) {
int course = pre[0], prereq = pre[1];
graph[prereq].push_back(course);
inDegree[course]++;
}
// BFS拓扑排序
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
int count = 0;
while (!q.empty()) {
int course = q.front();
q.pop();
count++;
for (int next : graph[course]) {
inDegree[next]--;
if (inDegree[next] == 0) {
q.push(next);
}
}
}
return count == numCourses;
}拓扑排序步骤：
- 统计每个节点的入度
- 把入度为0的节点入队
- 出队处理，邻居入度减1
- 如果邻居入度变0，入队
- 如果最终处理的节点数 = 总节点数，无环
6. 课程表 II (LeetCode 210)
题目：返回完成所有课程的顺序。
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> inDegree(numCourses, 0);
vector<vector<int>> graph(numCourses);
for (auto& pre : prerequisites) {
graph[pre[1]].push_back(pre[0]);
inDegree[pre[0]]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
vector<int> order;
while (!q.empty()) {
int course = q.front();
q.pop();
order.push_back(course);
for (int next : graph[course]) {
inDegree[next]--;
if (inDegree[next] == 0) {
q.push(next);
}
}
}
return order.size() == numCourses ? order : vector<int>();
}三、并查集
7. 并查集模板
class UnionFind {
vector<int> parent, rank;
public:
UnionFind(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
void unite(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return;
// 按秩合并
if (rank[px] < rank[py]) {
parent[px] = py;
} else if (rank[px] > rank[py]) {
parent[py] = px;
} else {
parent[py] = px;
rank[px]++;
}
}
bool connected(int x, int y) {
return find(x) == find(y);
}
};8. 省份数量 (LeetCode 547)
题目：给定n×n的邻接矩阵，求连通分量数量。
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
UnionFind uf(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isConnected[i][j] == 1) {
uf.unite(i, j);
}
}
}
// 统计根节点数量
int count = 0;
for (int i = 0; i < n; i++) {
if (uf.find(i) == i) count++;
}
return count;
}9. 冗余连接 (LeetCode 684)
题目：找出使树变成图的那条边（删除后恢复成树）。
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
UnionFind uf(n + 1);
for (auto& edge : edges) {
if (uf.connected(edge[0], edge[1])) {
return edge; // 这条边形成了环
}
uf.unite(edge[0], edge[1]);
}
return {};
}四、最短路径
10. 网络延迟时间 (LeetCode 743) – Dijkstra
题目：求从节点k到所有节点的最短时间。
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
// 建图
vector<vector<pair<int, int>>> graph(n + 1);
for (auto& t : times) {
graph[t[0]].push_back({t[1], t[2]});
}
// Dijkstra
vector<int> dist(n + 1, INT_MAX);
dist[k] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, k}); // {距离, 节点}
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue; // 已经有更短路径
for (auto& [v, w] : graph[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
int maxDist = *max_element(dist.begin() + 1, dist.end());
return maxDist == INT_MAX ? -1 : maxDist;
}11. 单词接龙 (LeetCode 127)
题目：从beginWord变换到endWord，每次只能改一个字母，求最短变换序列长度。
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordSet(wordList.begin(), wordList.end());
if (!wordSet.count(endWord)) return 0;
queue<string> q;
q.push(beginWord);
int level = 1;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
string word = q.front();
q.pop();
if (word == endWord) return level;
// 尝试改变每个字符
for (int j = 0; j < word.size(); j++) {
char original = word[j];
for (char c = 'a'; c <= 'z'; c++) {
if (c == original) continue;
word[j] = c;
if (wordSet.count(word)) {
q.push(word);
wordSet.erase(word); // 避免重复访问
}
}
word[j] = original;
}
}
level++;
}
return 0;
}12. 克隆图 (LeetCode 133)
class Solution {
unordered_map<Node*, Node*> visited;
public:
Node* cloneGraph(Node* node) {
if (!node) return nullptr;
if (visited.count(node)) {
return visited[node];
}
Node* clone = new Node(node->val);
visited[node] = clone;
for (Node* neighbor : node->neighbors) {
clone->neighbors.push_back(cloneGraph(neighbor));
}
return clone;
}
};图论总结
| 问题类型 | 算法 | 典型题目 |
|---|---|---|
| 连通性 | DFS/BFS/并查集 | 岛屿数量、省份数量 |
| 有向图环检测 | 拓扑排序 | 课程表 |
| 最短路径（无权） | BFS | 单词接龙 |
| 最短路径（有权） | Dijkstra | 网络延迟时间 |
| 连通分量 | 并查集 | 冗余连接 |
图遍历模板：
// DFS
void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
if (visited[node]) return;
visited[node] = true;
for (int next : graph[node]) {
dfs(next, graph, visited);
}
}
// BFS
void bfs(int start, vector<vector<int>>& graph) {
queue<int> q;
vector<bool> visited(graph.size(), false);
q.push(start);
visited[start] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int next : graph[node]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
}
}
}
}口诀：
- 网格问题用DFS/BFS，四个方向遍历
- 有向图先考虑拓扑排序
- 连通性问题考虑并查集
- 最短路径：无权BFS，有权Dijkstra
技巧与其他专题
本章涵盖一些不好归类但面试常考的技巧和算法。
一、位运算
位运算基础
| 运算 | 符号 | 示例 |
|---|---|---|
| 与 | & | 5 & 3 = 1 (101 & 011 = 001) |
| 或 | | | 5 | 3 = 7 (101 | 011 = 111) |
| 异或 | ^ | 5 ^ 3 = 6 (101 ^ 011 = 110) |
| 取反 | ~ | ~5 = -6 |
| 左移 | << | 5 << 1 = 10 |
| 右移 | >> | 5 >> 1 = 2 |
常用技巧：
n & 1：判断奇偶（最后一位是1则为奇）n & (n-1)：消去最右边的1n & (-n)：获取最右边的1a ^ a = 0：相同数异或为0a ^ 0 = a：任何数异或0等于自身
1. 只出现一次的数字 (LeetCode 136)
题目：数组中只有一个数出现一次，其他都出现两次。
int singleNumber(vector<int>& nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}原理：a ^ a = 0，所有出现两次的数异或后抵消，剩下的就是只出现一次的。
2. 只出现一次的数字 II (LeetCode 137)
题目：其他数都出现三次，找出只出现一次的那个。
int singleNumber(vector<int>& nums) {
int result = 0;
for (int i = 0; i < 32; i++) {
int bitSum = 0;
for (int num : nums) {
bitSum += (num >> i) & 1;
}
if (bitSum % 3 != 0) {
result |= (1 << i);
}
}
return result;
}原理：统计每一位上1的个数，对3取余，余数就是结果在该位的值。
3. 只出现一次的数字 III (LeetCode 260)
题目：有两个数只出现一次，其他都出现两次。
vector<int> singleNumber(vector<int>& nums) {
// 1. 全部异或，得到 a ^ b
int xorSum = 0;
for (int num : nums) {
xorSum ^= num;
}
// 2. 找到 xorSum 中任意一个为1的位（a和b在这一位不同）
int diff = xorSum & (-xorSum); // 最右边的1
// 3. 按这一位分成两组，分别异或
int a = 0, b = 0;
for (int num : nums) {
if (num & diff) {
a ^= num;
} else {
b ^= num;
}
}
return {a, b};
}4. 位1的个数 (LeetCode 191)
int hammingWeight(uint32_t n) {
int count = 0;
while (n) {
n &= (n - 1); // 消去最右边的1
count++;
}
return count;
}5. 2的幂 (LeetCode 231)
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}原理：2的幂只有一个1，消去后变成0。
6. 比特位计数 (LeetCode 338)
题目：返回0到n每个数二进制中1的个数。
vector<int> countBits(int n) {
vector<int> dp(n + 1);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i >> 1] + (i & 1);
}
return dp;
}原理：i的1的个数 = i/2的1的个数 + i的最后一位。
7. 颠倒二进制位 (LeetCode 190)
uint32_t reverseBits(uint32_t n) {
uint32_t result = 0;
for (int i = 0; i < 32; i++) {
result = (result << 1) | (n & 1);
n >>= 1;
}
return result;
}二、数学技巧
8. 快速幂 (LeetCode 50)
double myPow(double x, int n) {
long long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double result = 1.0;
while (N > 0) {
if (N & 1) {
result *= x;
}
x *= x;
N >>= 1;
}
return result;
}原理：x^n = (x^2)^(n/2)，时间复杂度O(logn)。
9. 阶乘后的零 (LeetCode 172)
题目：计算n!末尾有多少个零。
int trailingZeroes(int n) {
int count = 0;
while (n >= 5) {
n /= 5;
count += n;
}
return count;
}原理：0来自2×5，2的数量远多于5，所以只需数5的个数。
10. 整数反转 (LeetCode 7)
int reverse(int x) {
int rev = 0;
while (x != 0) {
int digit = x % 10;
// 检查溢出
if (rev > INT_MAX / 10 || rev < INT_MIN / 10) {
return 0;
}
rev = rev * 10 + digit;
x /= 10;
}
return rev;
}11. 回文数 (LeetCode 9)
bool isPalindrome(int x) {
if (x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int reversed = 0;
while (x > reversed) {
reversed = reversed * 10 + x % 10;
x /= 10;
}
return x == reversed || x == reversed / 10;
}12. 计数质数 (LeetCode 204)
int countPrimes(int n) {
if (n <= 2) return 0;
vector<bool> isPrime(n, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i < n; i++) {
if (isPrime[i]) {
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
return count(isPrime.begin(), isPrime.end(), true);
}埃拉托斯特尼筛法：从2开始，把每个质数的倍数标记为非质数。
三、前缀和与差分
13. 前缀和基础
// 构建前缀和数组
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
// 查询区间 [l, r] 的和
int sum = prefix[r + 1] - prefix[l];14. 二维前缀和 (LeetCode 304)
class NumMatrix {
vector<vector<int>> prefix;
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
prefix.assign(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
prefix[i+1][j+1] = matrix[i][j] + prefix[i][j+1]
+ prefix[i+1][j] - prefix[i][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return prefix[row2+1][col2+1] - prefix[row2+1][col1]
- prefix[row1][col2+1] + prefix[row1][col1];
}
};15. 差分数组
用途：区间修改，单点查询
// 对区间 [l, r] 中每个元素加 val
diff[l] += val;
diff[r + 1] -= val;
// 还原原数组
for (int i = 1; i < n; i++) {
diff[i] += diff[i - 1];
}拼车 (LeetCode 1094)
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<int> diff(1001, 0);
for (auto& trip : trips) {
diff[trip[1]] += trip[0]; // 上车
diff[trip[2]] -= trip[0]; // 下车
}
int passengers = 0;
for (int i = 0; i < 1001; i++) {
passengers += diff[i];
if (passengers > capacity) return false;
}
return true;
}四、多指针技巧
16. 多数元素 (LeetCode 169) – 摩尔投票
题目：找出出现次数超过n/2的元素。
int majorityElement(vector<int>& nums) {
int candidate = 0, count = 0;
for (int num : nums) {
if (count == 0) {
candidate = num;
}
count += (num == candidate) ? 1 : -1;
}
return candidate;
}摩尔投票原理：不同的数相互抵消，最后剩下的就是多数元素。
17. 寻找重复数 (LeetCode 287)
题目：n+1个整数，值在[1,n]之间，必有一个重复数。
int findDuplicate(vector<int>& nums) {
// 快慢指针找环
int slow = nums[0], fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
// 找环入口
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}原理：把值看作下标，形成链表，重复数就是环的入口。
18. 下一个排列 (LeetCode 31)
void nextPermutation(vector<int>& nums) {
int n = nums.size();
int i = n - 2;
// 1. 从右往左找第一个下降的数
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i >= 0) {
// 2. 从右往左找第一个比nums[i]大的数
int j = n - 1;
while (nums[j] <= nums[i]) {
j--;
}
swap(nums[i], nums[j]);
}
// 3. 反转i后面的部分
reverse(nums.begin() + i + 1, nums.end());
}五、设计类
19. LRU缓存 (LeetCode 146)
class LRUCache {
int capacity;
list<pair<int, int>> cache; // 双向链表：{key, value}
unordered_map<int, list<pair<int, int>>::iterator> map; // key -> 链表迭代器
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
if (!map.count(key)) return -1;
// 移到链表头部
cache.splice(cache.begin(), cache, map[key]);
return map[key]->second;
}
void put(int key, int value) {
if (map.count(key)) {
// 更新值并移到头部
map[key]->second = value;
cache.splice(cache.begin(), cache, map[key]);
} else {
// 容量满了，删除尾部
if (cache.size() == capacity) {
map.erase(cache.back().first);
cache.pop_back();
}
// 插入头部
cache.emplace_front(key, value);
map[key] = cache.begin();
}
}
};20. 随机打乱数组 (LeetCode 384)
class Solution {
vector<int> original;
public:
Solution(vector<int>& nums) : original(nums) {}
vector<int> reset() {
return original;
}
vector<int> shuffle() {
vector<int> shuffled = original;
int n = shuffled.size();
// Fisher-Yates洗牌算法
for (int i = n - 1; i > 0; i--) {
int j = rand() % (i + 1);
swap(shuffled[i], shuffled[j]);
}
return shuffled;
}
};六、其他常见问题
21. 缺失的第一个正数 (LeetCode 41)
题目：找出未出现的最小正整数，要求O(n)时间O(1)空间。
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
// 把每个数放到它应该在的位置：nums[i] 应该是 i+1
for (int i = 0; i < n; i++) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
swap(nums[i], nums[nums[i] - 1]);
}
}
// 找第一个不对的位置
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}22. 螺旋矩阵 (LeetCode 54)
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> result;
int top = 0, bottom = matrix.size() - 1;
int left = 0, right = matrix[0].size() - 1;
while (top <= bottom && left <= right) {
// 向右
for (int j = left; j <= right; j++) {
result.push_back(matrix[top][j]);
}
top++;
// 向下
for (int i = top; i <= bottom; i++) {
result.push_back(matrix[i][right]);
}
right--;
// 向左
if (top <= bottom) {
for (int j = right; j >= left; j--) {
result.push_back(matrix[bottom][j]);
}
bottom--;
}
// 向上
if (left <= right) {
for (int i = bottom; i >= top; i--) {
result.push_back(matrix[i][left]);
}
left++;
}
}
return result;
}23. 旋转图像 (LeetCode 48)
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
// 先转置
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
// 再左右翻转
for (int i = 0; i < n; i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
}口诀：顺时针90° = 转置 + 左右翻转
总结
| 技巧类型 | 常用场景 | 典型题目 |
|---|---|---|
| 位运算 | 找单一元素、快速计算 | 只出现一次的数字 |
| 摩尔投票 | 找多数元素 | 多数元素 |
| 快慢指针 | 找环、找重复 | 寻找重复数 |
| 前缀和/差分 | 区间查询/修改 | 区域和检索 |
| 原地交换 | O(1)空间要求 | 缺失的第一个正数 |
面试小技巧：
- 遇到”O(1)空间”考虑位运算或原地修改
- 遇到”超过一半”考虑摩尔投票
- 遇到”区间操作”考虑前缀和或差分
- 遇到”不用额外空间找重复”考虑快慢指针