Appearance
常见算法题
两数之和
两数之和是什么？ 题目一般是：
给你一个整数数组 nums 和一个目标值 target。
请你在数组中找出两个数，使它们相加等于 target。
返回这两个数的下标。比如：
nums = [2, 7, 11, 15]
target = 9因为：
2 + 7 = 9所以返回：
[0, 1]注意：返回的是下标，不是数字本身。
核心思路
暴力做法是两层循环：
拿 nums[i] 和后面每个 nums[j] 相加这样时间复杂度是：
c
O(n²)更好的做法是用 C# 的：
c
Dictionary<int, int>它相当于哈希表。
字典里存：
key：数字
value：数字对应的下标遍历当前数字 nums[i] 时，我们不去暴力找另一个数，而是直接算：
c
complement = target - nums[i]然后问字典：
之前有没有出现过 complement？如果出现过，就找到答案了。
C# 代码
c
using System.Collections.Generic; // 引入集合命名空间，用来使用 Dictionary
public class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public int[] TwoSum(int[] nums, int target) // 定义 TwoSum 函数，输入数组 nums 和目标值 target，返回两个下标
{ // TwoSum 函数开始
Dictionary<int, int> map = new Dictionary<int, int>(); // 创建字典，key 存数字，value 存数字对应的下标
for (int i = 0; i < nums.Length; i++) // 从左到右遍历数组中的每一个数字
{ // for 循环开始
int current = nums[i]; // 取出当前数字
int complement = target - current; // 计算当前数字需要搭配的另一个数字
if (map.ContainsKey(complement)) // 如果字典里已经出现过 complement
{ // if 语句开始
return new int[] { map[complement], i }; // 返回 complement 的下标和当前数字的下标
} // if 语句结束
if (!map.ContainsKey(current)) // 如果当前数字还没有被放进字典
{ // if 语句开始
map.Add(current, i); // 把当前数字和它的下标加入字典
} // if 语句结束
} // for 循环结束
return new int[] { }; // 如果没有找到答案，返回空数组
} // TwoSum 函数结束
} // Solution 类结束为什么要先查再存？
这点很关键。
假设：
c
nums = [3, 3]
target = 6当我们遍历第一个 3 时：
c
complement = 6 - 3 = 3如果先把自己存进去，再查字典，就可能把同一个下标用了两次。
所以正确顺序是：
先查 complement 是否存在
再把当前数字存入字典这样可以保证：
两个下标一定不同为什么 Dictionary 快？
Dictionary 底层是哈希表。
查找一个 key 平均情况下是：
O(1)所以整个数组只需要遍历一次：
O(n)比暴力双循环的：
O(n²)快很多。
复杂度
时间复杂度：
O(n)因为只遍历一次数组。
空间复杂度：
O(n)因为最坏情况下，字典里可能存下很多数字。
面试高分回答
CAUTION
两数之和可以用哈希表优化。遍历数组时，对于当前数字 nums[i]，我们计算它需要的另一个数字 complement = target - nums[i]。如果 complement 已经在字典中，说明之前出现过一个数字可以和当前数字相加得到 target，直接返回两个下标。如果没有找到，就把当前数字和下标存入字典。这样每个元素只遍历一次，字典查询平均是 O(1)，所以总时间复杂度是 O(n)，空间复杂度是 O(n)。
三数之和
一句话理解
三数之和就是：在数组里找所有不重复的三元组，让它们相加等于 0。经典解法是：先排序，再固定一个数，剩下两个数用双指针找。
题目意思
给你一个数组：
c
nums = [-1, 0, 1, 2, -1, -4]你要找所有三元组：
c
a + b + c = 0并且三元组不能重复。
这个例子的答案是：
c
[-1, -1, 2]
[-1, 0, 1]注意：返回的是数字组合，不是下标。
核心思路
两数之和可以用哈希表。
三数之和最经典的是：
先排序。
固定第一个数 nums[i]。
剩下部分用 left 和 right 双指针找另外两个数。
排序后：
c
[-4, -1, -1, 0, 1, 2]假设固定：
c
nums[i] = -1那问题就变成：
c
在 i 后面找两个数，让 left + right = 1也就是：
c
-1 + nums[left] + nums[right] = 0为什么要排序
排序后，数组从小到大。
如果三数之和太小：
c
sum < 0说明需要更大的数，所以 left 右移。
如果三数之和太大：
c
sum > 0说明需要更小的数，所以 right 左移。
如果不排序，你就不知道指针应该往哪边移动。
双指针怎么走
固定 i 后：
c
left = i + 1
right = nums.size() - 1然后计算：
c
sum = nums[i] + nums[left] + nums[right]如果：
c
sum == 0说明找到一个答案。
如果：
c
sum < 0说明当前和太小，让 left++。
如果：
c
sum > 0说明当前和太大，让 right--。
去重非常重要
三数之和最容易错在重复答案。
比如排序后：
c
[-4, -1, -1, 0, 1, 2]这里有两个 -1。
如果不跳过重复的固定数，[-1, 0, 1] 可能会被加入多次。
所以要做三层去重：
固定数 i 去重。
找到答案后，left 去重。
找到答案后，right 去重。
C++ 标准写法
c
#include <algorithm> // 引入 sort 函数，用来给数组排序
#include <vector> // 引入 vector 容器，用来保存数组和答案
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
vector<vector<int>> threeSum(vector<int>& nums) // 定义 threeSum 函数，返回所有不重复三元组
{ // threeSum 函数开始
vector<vector<int>> result; // 创建结果数组，用来保存所有满足条件的三元组
sort(nums.begin(), nums.end()); // 先给数组排序，方便双指针移动和去重
int n = nums.size(); // 保存数组长度，避免后面反复调用 size
for (int i = 0; i < n - 2; i++) // 枚举第一个数，至少要给 left 和 right 留两个位置
{ // for 循环开始
if (i > 0 && nums[i] == nums[i - 1]) // 如果当前固定数和上一个固定数相同
{ // if 语句开始
continue; // 跳过重复固定数，避免重复三元组
} // if 语句结束
if (nums[i] > 0) // 如果固定数已经大于 0
{ // if 语句开始
break; // 后面的数都更大，三数之和不可能等于 0，直接结束
} // if 语句结束
int left = i + 1; // 左指针从固定数后面一位开始
int right = n - 1; // 右指针从数组最后一位开始
while (left < right) // 只要左右指针还没有相遇，就继续查找
{ // while 循环开始
int sum = nums[i] + nums[left] + nums[right]; // 计算当前三数之和
if (sum == 0) // 如果三数之和正好等于 0
{ // if 语句开始
result.push_back({nums[i], nums[left], nums[right]}); // 把当前三元组加入答案
left++; // 左指针右移，继续找新的组合
right--; // 右指针左移，继续找新的组合
while (left < right && nums[left] == nums[left - 1]) // 如果左指针遇到重复值
{ // while 循环开始
left++; // 跳过重复的左值，避免重复答案
} // while 循环结束
while (left < right && nums[right] == nums[right + 1]) // 如果右指针遇到重复值
{ // while 循环开始
right--; // 跳过重复的右值，避免重复答案
} // while 循环结束
} // if 语句结束
else if (sum < 0) // 如果三数之和小于 0
{ // else if 语句开始
left++; // 说明和太小，需要更大的数，所以左指针右移
} // else if 语句结束
else // 否则说明三数之和大于 0
{ // else 语句开始
right--; // 说明和太大，需要更小的数，所以右指针左移
} // else 语句结束
} // while 循环结束
} // for 循环结束
return result; // 返回所有不重复三元组
} // threeSum 函数结束
}; // Solution 类结束复杂度
时间复杂度是 O(n²)。
因为外层固定一个数是 O(n)，里面双指针整体移动是 O(n)。
空间复杂度通常认为是 O(1) 或 O(log n)，看排序实现是否使用额外栈空间；结果数组不算额外空间。
常见坑
第一个坑：没有排序就直接双指针。
第二个坑：没有去重，导致答案重复。
第三个坑：返回下标。三数之和一般返回三元组数字，不是下标。
第四个坑：找到一个答案后，只移动一个指针。通常命中后 left++ 和 right-- 都要移动，并且跳过重复值。
面试高分回答
CAUTION
三数之和通常用排序加双指针。先对数组排序，然后枚举第一个数 nums[i]，把问题转化为在 i 后面的区间里寻找两个数，使三数之和为 0。由于数组有序，如果当前和小于 0，就让 left 右移增大和；如果当前和大于 0，就让 right 左移减小和；如果等于 0，就记录答案，并跳过重复的 left 和 right。为了避免重复三元组，还要跳过重复的固定数 i。整体时间复杂度是 O(n²)。
反转链表
一句话理解
反转链表就是把每个节点的 next 指针反过来：原来 1 -> 2 -> 3 -> null，反转后变成 3 -> 2 -> 1 -> null。
核心思路
反转链表最经典的写法是三个指针：
prev：已经反转好的前半部分的头。
current：当前正在处理的节点。
next：提前保存 current 后面的节点，防止链表断掉。
为什么一定要保存 next？
因为一旦你执行：
c
current->next = prev当前节点就不再指向原来的后面节点了。如果没提前保存，后面的链表就丢了。
循环过程
假设原链表是：
c
1 -> 2 -> 3 -> null一开始：
c
prev = null
current = 1第一轮：
c
next = 2
1->next = null
prev = 1
current = 2此时已经反转好的部分是：
c
1 -> null还没处理的是：
c
2 -> 3 -> null最后会变成：
c
3 -> 2 -> 1 -> nullC++ 代码：迭代写法
这是面试最推荐写法，简单、稳定、空间复杂度低。
c
struct ListNode // 定义链表节点结构体
{ // ListNode 结构体开始
int val; // 保存当前节点的值
ListNode* next; // 保存下一个节点的地址
ListNode(int x) : val(x), next(nullptr) // 构造函数，用传入的 x 初始化节点值，并让 next 默认为空
{ // 构造函数开始
} // 构造函数结束
}; // ListNode 结构体结束
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
ListNode* reverseList(ListNode* head) // 定义反转链表函数，传入旧头节点，返回新头节点
{ // reverseList 函数开始
ListNode* prev = nullptr; // prev 表示已经反转好的前半部分，一开始为空
ListNode* current = head; // current 表示当前正在处理的节点，一开始是旧头节点
while (current != nullptr) // 只要当前节点不为空，就继续反转
{ // while 循环开始
ListNode* next = current->next; // 先保存 current 后面的节点，防止反转指针后丢失链表
current->next = prev; // 把 current 的 next 指向 prev，完成当前节点的指针反转
prev = current; // prev 向前推进到 current，表示反转好的部分变长了
current = next; // current 移动到原来的下一个节点，继续处理后面的链表
} // while 循环结束
return prev; // current 为空时，prev 就是反转后的新头节点
} // reverseList 函数结束
}; // Solution 类结束为什么返回 prev
循环结束时：
c
current == null说明旧链表已经全部处理完。
这时候 prev 指向最后处理的节点。
而最后处理的节点，正好是反转后链表的新头节点。
比如：
c
1 -> 2 -> 3 -> null最后处理的是 3，所以新头就是 3。
复杂度
时间复杂度是 O(n)。
因为每个节点只处理一次。
空间复杂度是 O(1)。
因为只用了 prev、current、next 三个指针，没有额外开数组或栈。
递归写法
递归写法也可以，但面试时更容易写错。它的思想是：先把后面的链表反转好，再把当前节点接到尾部。
c
struct ListNode // 定义链表节点结构体
{ // ListNode 结构体开始
int val; // 保存当前节点的值
ListNode* next; // 保存下一个节点的地址
ListNode(int x) : val(x), next(nullptr) // 构造函数，用传入的 x 初始化节点值，并让 next 默认为空
{ // 构造函数开始
} // 构造函数结束
}; // ListNode 结构体结束
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
ListNode* reverseList(ListNode* head) // 定义递归反转链表函数
{ // reverseList 函数开始
if (head == nullptr || head->next == nullptr) // 如果链表为空，或者只有一个节点
{ // if 语句开始
return head; // 空链表或单节点链表反转后还是自己
} // if 语句结束
ListNode* newHead = reverseList(head->next); // 递归反转 head 后面的链表，并拿到新头节点
head->next->next = head; // 让原来的下一个节点反过来指向 head
head->next = nullptr; // 把 head 的 next 断开，避免形成环
return newHead; // 返回反转后的新头节点
} // reverseList 函数结束
}; // Solution 类结束递归为什么要 head->next = nullptr
原来是：
c
1 -> 2递归回来后会做：
c
2 -> 1但原来的：
c
1 -> 2还在。
如果不把 1->next 置空，就会变成：
c
1 <-> 2也就是形成环。
所以递归写法一定要断开旧指针。
面试高分回答
NOTE
反转链表的核心是逐个改变节点的 next 指针方向。迭代做法通常使用三个指针：prev 表示已经反转好的部分，current 表示当前处理节点，next 用来提前保存后续节点，避免修改 current->next 后丢失链表。每次循环先保存 next，再令 current->next = prev，然后 prev 和 current 向后移动。循环结束时 prev 就是新的头节点。时间复杂度是 O(n)，空间复杂度是 O(1)。
合并两个有序链表
一句话理解
合并两个有序链表，就是每次比较两个链表当前头节点，谁小就把谁接到结果链表后面，然后那个链表往后走一步。
题目意思
给你两个已经升序排好的链表：
list1: 1 -> 2 -> 4
list2: 1 -> 3 -> 4你要把它们合成一个新的升序链表：
1 -> 1 -> 2 -> 3 -> 4 -> 4注意：链表本来就是有序的，所以我们不用重新排序，只要像拉拉链一样，每次拿更小的节点接到结果后面。
核心思路
准备一个 dummy 虚拟头节点。
再准备一个 tail 指针，表示结果链表当前最后一个节点。
然后循环比较：
c
list1 当前节点
list2 当前节点如果 list1->val <= list2->val，就接 list1。
否则接 list2。
接完之后：
被接走的链表往后移动。
tail 也往后移动。
为什么要用 dummy
如果不用 dummy，你要单独处理“结果链表第一个节点是谁”。
用了 dummy 之后，所有节点都统一接在 tail->next 后面。
最后返回：
c
dummy.next因为 dummy 自己不是答案的一部分，dummy.next 才是真正的新头节点。
C++ 迭代写法
c
struct ListNode // 定义链表节点结构体
{ // ListNode 结构体开始
int val; // 保存当前节点的值
ListNode* next; // 保存下一个节点的地址
ListNode(int x) : val(x), next(nullptr) // 构造函数，用 x 初始化 val，并让 next 默认指向空
{ // 构造函数开始
} // 构造函数结束
}; // ListNode 结构体结束
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) // 定义合并两个有序链表的函数
{ // mergeTwoLists 函数开始
ListNode dummy(0); // 创建虚拟头节点，方便统一处理结果链表的开头
ListNode* tail = &dummy; // tail 指向结果链表的尾部，一开始指向 dummy
while (list1 != nullptr && list2 != nullptr) // 只要两个链表都还没有走完，就继续比较
{ // while 循环开始
if (list1->val <= list2->val) // 如果 list1 当前节点的值更小或相等
{ // if 语句开始
tail->next = list1; // 把 list1 当前节点接到结果链表尾部
list1 = list1->next; // list1 指针向后移动一位
} // if 语句结束
else // 否则说明 list2 当前节点更小
{ // else 语句开始
tail->next = list2; // 把 list2 当前节点接到结果链表尾部
list2 = list2->next; // list2 指针向后移动一位
} // else 语句结束
tail = tail->next; // tail 向后移动到结果链表新的尾节点
} // while 循环结束
if (list1 != nullptr) // 如果 list1 还有剩余节点
{ // if 语句开始
tail->next = list1; // 直接把 list1 剩余部分接到结果链表后面
} // if 语句结束
else // 否则说明 list1 已经走完
{ // else 语句开始
tail->next = list2; // 直接把 list2 剩余部分接到结果链表后面
} // else 语句结束
return dummy.next; // 返回 dummy 后面的节点，也就是真正的新链表头
} // mergeTwoLists 函数结束
}; // Solution 类结束为什么剩余链表可以直接接上
因为两个输入链表本身已经是有序的。
比如比较到后面时：
c
结果链表: 1 -> 1 -> 2
list1: 4
list2: 3 -> 4接完 3 后，如果 list2 走完了，list1 剩下的 4 本来就是有序的，直接接上即可。
不需要再创建新节点，也不需要再排序。
递归写法
递归写法更短，但零基础时更推荐先掌握迭代法。
c
struct ListNode // 定义链表节点结构体
{ // ListNode 结构体开始
int val; // 保存当前节点的值
ListNode* next; // 保存下一个节点的地址
ListNode(int x) : val(x), next(nullptr) // 构造函数，用 x 初始化 val，并让 next 默认指向空
{ // 构造函数开始
} // 构造函数结束
}; // ListNode 结构体结束
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) // 定义递归合并两个有序链表的函数
{ // mergeTwoLists 函数开始
if (list1 == nullptr) // 如果 list1 已经为空
{ // if 语句开始
return list2; // 直接返回 list2 剩余部分
} // if 语句结束
if (list2 == nullptr) // 如果 list2 已经为空
{ // if 语句开始
return list1; // 直接返回 list1 剩余部分
} // if 语句结束
if (list1->val <= list2->val) // 如果 list1 当前节点更小或相等
{ // if 语句开始
list1->next = mergeTwoLists(list1->next, list2); // list1 当前节点后面接递归合并后的结果
return list1; // 返回 list1 作为当前合并结果的头
} // if 语句结束
else // 否则说明 list2 当前节点更小
{ // else 语句开始
list2->next = mergeTwoLists(list1, list2->next); // list2 当前节点后面接递归合并后的结果
return list2; // 返回 list2 作为当前合并结果的头
} // else 语句结束
} // mergeTwoLists 函数结束
}; // Solution 类结束复杂度
时间复杂度是 O(m + n)。
因为两个链表的每个节点最多被处理一次。
空间复杂度：
迭代法是 O(1)。
递归法是 O(m + n)，因为递归调用会占用函数栈。
面试高分回答
NOTE
合并两个有序链表可以用双指针。分别指向两个链表当前头节点，每次比较两个节点的值，把较小的节点接到结果链表尾部，然后对应链表向后移动。为了简化处理结果链表的头节点，通常使用一个 dummy 虚拟头节点和一个 tail 尾指针。循环结束后，如果某个链表还有剩余节点，因为它本身已经有序，可以直接接到 tail 后面。迭代法时间复杂度是 O(m+n)，空间复杂度是 O(1)。
判断链表是否有环
一句话理解
判断链表是否有环，最经典的方法是“快慢指针”：slow 每次走 1 步，fast 每次走 2 步。如果有环，fast 一定会在环里追上 slow；如果没有环，fast 会先走到 null。
什么叫链表有环
正常链表是这样：
c
1 -> 2 -> 3 -> null最后会走到 null。
有环链表是这样：
1 -> 2 -> 3 -> 4 -> 5
↑ |
└─────────┘节点 5 的 next 指回了节点 3，所以一直走下去会在 3 -> 4 -> 5 -> 3 里面绕圈，永远走不到 null。
快慢指针思路
准备两个指针：
slow：慢指针，每次走一步。
fast：快指针，每次走两步。
每一轮：
c
slow = slow->next
fast = fast->next->next如果链表没有环，fast 走得更快，所以它会先到链表尾部，也就是遇到 null。
如果链表有环，fast 和 slow 都会进入环。进入环之后，fast 每轮比 slow 多走一步，所以它一定会追上 slow。
为什么有环一定会相遇
你可以把环想成操场跑道。
slow 每次走 1 格。
fast 每次走 2 格。
它们都进入跑道后，fast 每一轮都会比 slow 多接近 1 格。
只要一直跑，快的人一定会追上慢的人。
所以：
c
slow == fast就说明链表有环。
C++ 标准写法
c
struct ListNode // 定义链表节点结构体
{ // ListNode 结构体开始
int val; // 保存当前节点的值
ListNode* next; // 保存下一个节点的地址
ListNode(int x) : val(x), next(nullptr) // 构造函数，用 x 初始化 val，并让 next 默认指向空
{ // 构造函数开始
} // 构造函数结束
}; // ListNode 结构体结束
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
bool hasCycle(ListNode* head) // 定义判断链表是否有环的函数
{ // hasCycle 函数开始
ListNode* slow = head; // slow 是慢指针，一开始指向头节点
ListNode* fast = head; // fast 是快指针，一开始也指向头节点
while (fast != nullptr && fast->next != nullptr) // 只有 fast 和 fast->next 都不为空，fast 才能安全走两步
{ // while 循环开始
slow = slow->next; // 慢指针每次走一步
fast = fast->next->next; // 快指针每次走两步
if (slow == fast) // 如果快慢指针相遇
{ // if 语句开始
return true; // 说明链表有环
} // if 语句结束
} // while 循环结束
return false; // fast 走到了 null，说明链表没有环
} // hasCycle 函数结束
}; // Solution 类结束为什么 while 条件要写两个判断
这里必须写：
c
fast != nullptr && fast->next != nullptr因为 fast 每次要走两步：
c
fast = fast->next->next如果 fast 已经是 null，访问 fast->next 会崩。
如果 fast->next 是 null，访问 fast->next->next 也不安全。
所以循环条件是在保护快指针安全移动。
哈希表写法
也可以用哈希表记录访问过的节点。
如果某个节点第二次出现，说明有环。
这个方法更直观，但空间复杂度是 O(n)。
c
#include <unordered_set> // 引入 unordered_set，用来记录访问过的节点地址
using namespace std; // 使用标准命名空间，避免每次写 std::
struct ListNode // 定义链表节点结构体
{ // ListNode 结构体开始
int val; // 保存当前节点的值
ListNode* next; // 保存下一个节点的地址
ListNode(int x) : val(x), next(nullptr) // 构造函数，用 x 初始化 val，并让 next 默认指向空
{ // 构造函数开始
} // 构造函数结束
}; // ListNode 结构体结束
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
bool hasCycle(ListNode* head) // 定义判断链表是否有环的函数
{ // hasCycle 函数开始
unordered_set<ListNode*> visited; // 创建哈希集合，用来保存已经访问过的节点地址
ListNode* current = head; // current 从头节点开始遍历
while (current != nullptr) // 只要 current 还没有走到空，就继续遍历
{ // while 循环开始
if (visited.find(current) != visited.end()) // 如果当前节点之前已经访问过
{ // if 语句开始
return true; // 说明链表绕回来了，也就是有环
} // if 语句结束
visited.insert(current); // 把当前节点地址记录到哈希集合里
current = current->next; // current 移动到下一个节点
} // while 循环结束
return false; // 如果正常走到 null，说明没有环
} // hasCycle 函数结束
}; // Solution 类结束复杂度对比
| 方法 | 时间复杂度 | 空间复杂度 | 面试推荐 |
|---|---|---|---|
| 快慢指针 | O(n) | O(1) | 推荐 |
| 哈希表 | O(n) | O(n) | 好理解，但不够省空间 |
常见坑
第一个坑：只写普通遍历。
c
while (head != nullptr)如果链表有环，这个循环永远不会结束。
第二个坑：快指针移动前没有判断 fast->next。
第三个坑：比较节点值，而不是比较节点地址。
判断是否相遇要写：
c
slow == fast不是：
c
slow->val == fast->val因为链表里可能有多个节点的值相同，值相同不代表是同一个节点。
面试高分回答
NOTE
判断链表是否有环可以用 Floyd 快慢指针算法。定义 slow 和 fast 两个指针，初始都指向头节点。每轮 slow 走一步，fast 走两步。如果链表无环，fast 会先到达 null；如果链表有环，两个指针进入环后，fast 每轮都会比 slow 多走一步，最终一定会相遇。因此只要出现 slow == fast，就说明有环。这个方法时间复杂度是 O(n)，空间复杂度是 O(1)。
有效括号
一句话理解
“有效括号”就是判断括号有没有正确配对、正确闭合。最经典做法是用栈：左括号入栈，右括号来了就和栈顶匹配。
题目意思
给你一个只包含这些字符的字符串：
c
'(', ')', '[', ']', '{', '}'判断它是不是有效括号字符串。
有效例子：
c
()
()[]{}
({[]})无效例子：
c
(]
([)]
((
]有效括号必须满足：
左括号要被同类型右括号关闭。
括号关闭顺序要正确。
不能多左括号，也不能多右括号。
为什么用栈
括号匹配有一个特点：
后打开的括号，要先关闭。比如：
c
({[]})打开顺序是：
c
( { [关闭顺序必须是：
c
] } )这正好符合栈的特点：
后进先出所以这题天然适合用栈。
核心规则
遇到左括号：
入栈遇到右括号：
看栈顶是不是对应的左括号如果匹配：
弹出栈顶如果不匹配：
c
直接返回 false最后：
栈为空，说明全部匹配成功
栈不为空，说明还有左括号没被关闭C++ 标准写法
c
#include <stack> // 引入 stack 容器，用来保存还没有匹配的左括号
#include <string> // 引入 string 类型，用来接收括号字符串
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
bool isValid(string s) // 定义判断括号是否有效的函数
{ // isValid 函数开始
stack<char> st; // 创建字符栈，用来保存左括号
for (char ch : s) // 从左到右遍历字符串中的每一个字符
{ // for 循环开始
if (ch == '(' || ch == '[' || ch == '{') // 如果当前字符是左括号
{ // if 语句开始
st.push(ch); // 把左括号压入栈中，等待后续右括号匹配
} // if 语句结束
else // 否则当前字符就是右括号
{ // else 语句开始
if (st.empty()) // 如果右括号来了，但是栈里没有左括号
{ // if 语句开始
return false; // 说明没有可匹配的左括号，括号无效
} // if 语句结束
char top = st.top(); // 取出栈顶左括号，也就是最近出现的左括号
if (ch == ')' && top != '(') // 如果当前是右小括号，但栈顶不是左小括号
{ // if 语句开始
return false; // 类型不匹配，括号无效
} // if 语句结束
if (ch == ']' && top != '[') // 如果当前是右中括号，但栈顶不是左中括号
{ // if 语句开始
return false; // 类型不匹配，括号无效
} // if 语句结束
if (ch == '}' && top != '{') // 如果当前是右大括号，但栈顶不是左大括号
{ // if 语句开始
return false; // 类型不匹配，括号无效
} // if 语句结束
st.pop(); // 匹配成功后，弹出栈顶左括号
} // else 语句结束
} // for 循环结束
return st.empty(); // 遍历结束后，栈为空才说明所有左括号都被匹配了
} // isValid 函数结束
}; // Solution 类结束执行过程例子
字符串：
c
({[]})读到 (：
c
栈：[ ( ]读到 {：
c
栈：[ (, { ]读到 [：
c
栈：[ (, {, [ ]读到 ]：
栈顶是 [，匹配成功，弹出 [读到 }：
栈顶是 {，匹配成功，弹出 {读到 )：
栈顶是 (，匹配成功，弹出 (最后栈为空：
有效无效情况
第一种：右括号太早出现。
c
")"一开始就遇到右括号，但栈是空的，没有左括号可以匹配，所以无效。
第二种：括号类型不匹配。
c
"(]"遇到 ] 时，栈顶是 (，类型不匹配，所以无效。
第三种：最后还有左括号没关。
c
"(()"遍历结束后，栈里还有 (，说明没闭合，所以无效。
复杂度
时间复杂度是 O(n)。
因为每个字符只遍历一次。
空间复杂度是 O(n)。
最坏情况下，字符串全是左括号，栈里要存 n 个字符。
面试高分回答
NOTE
有效括号可以用栈来判断。因为括号闭合满足“后打开的括号先关闭”，这正好符合栈的后进先出。遍历字符串时，遇到左括号就入栈；遇到右括号时，先判断栈是否为空，如果为空说明没有左括号匹配，直接返回 false；如果不为空，就检查栈顶左括号是否和当前右括号类型匹配，不匹配也返回 false，匹配则弹出栈顶。遍历结束后，只有栈为空才说明所有括号都正确闭合。时间复杂度是 O(n)，空间复杂度是 O(n)。
最小栈
一句话理解
最小栈就是：除了普通栈的 push、pop、top，还要能用 O(1) 时间拿到当前栈里的最小值 getMin()。
题目要求
普通栈支持：
c
push(x)：压入元素
pop()：弹出栈顶
top()：查看栈顶最小栈额外要求：
c
getMin()：快速拿到当前栈里的最小值关键是：getMin() 不能每次都遍历整个栈，否则就是 O(n)。题目通常要求它是 O(1)。
核心思路
用两个栈：
dataStack：正常保存所有数据。
minStack：保存“当前这一层为止的最小值”。
比如依次压入：
c
5, 2, -3, 0dataStack 是：
c
0
-3
2
5minStack 是：
c
-3
-3
2
5为什么最后一层是 -3？
因为压入 0 时，当前最小值已经是 -3，所以这一层的最小值仍然是 -3。
这样 getMin() 只需要看：
c
minStack.top()就能立刻拿到最小值。
为什么 pop 要两个栈一起弹
因为 minStack 的每一层和 dataStack 的每一层是对应的。
dataStack 弹掉一个元素，当前栈的最小值状态也要回到上一层。
所以：
c
dataStack.pop()
minStack.pop()必须一起做。
C++ 标准写法
c
#include <stack> // 引入 stack 容器，用来实现普通栈和辅助最小栈
#include <algorithm> // 引入 min 函数，用来计算两个数中的较小值
using namespace std; // 使用标准命名空间，避免每次写 std::
class MinStack // 定义最小栈类
{ // MinStack 类开始
private: // private 表示下面成员只能在类内部访问
stack<int> dataStack; // dataStack 保存真实压入的所有数据
stack<int> minStack; // minStack 保存每一层对应的当前最小值
public: // public 表示下面函数可以被外部调用
MinStack() // 定义构造函数
{ // 构造函数开始
} // 构造函数结束
void push(int val) // 定义 push 函数，用来压入一个元素
{ // push 函数开始
dataStack.push(val); // 真实数据栈直接压入 val
if (minStack.empty()) // 如果最小栈当前为空
{ // if 语句开始
minStack.push(val); // 第一个元素就是当前最小值
} // if 语句结束
else // 否则说明最小栈里已经有当前最小值
{ // else 语句开始
int currentMin = minStack.top(); // 取出压入 val 之前的最小值
minStack.push(min(val, currentMin)); // 把 val 和旧最小值中更小的那个压入最小栈
} // else 语句结束
} // push 函数结束
void pop() // 定义 pop 函数，用来弹出栈顶元素
{ // pop 函数开始
dataStack.pop(); // 弹出真实数据栈的栈顶
minStack.pop(); // 同时弹出最小栈的栈顶，让最小值状态回到上一层
} // pop 函数结束
int top() // 定义 top 函数，用来查看当前栈顶元素
{ // top 函数开始
return dataStack.top(); // 返回真实数据栈的栈顶
} // top 函数结束
int getMin() // 定义 getMin 函数，用来获取当前最小值
{ // getMin 函数开始
return minStack.top(); // 最小栈的栈顶永远保存当前最小值
} // getMin 函数结束
}; // MinStack 类结束执行过程
依次执行：
c
push(5)
push(2)
push(-3)
push(0)状态如下：
| 操作 | dataStack 栈顶 | minStack 栈顶 | 当前最小值 |
|---|---|---|---|
push(5) | 5 | 5 | 5 |
push(2) | 2 | 2 | 2 |
push(-3) | -3 | -3 | -3 |
push(0) | 0 | -3 | -3 |
执行：
c
getMin()直接返回：
c
-3执行：
c
pop()弹出 0，两个栈都弹一层，当前最小值还是 -3。
再执行：
c
pop()弹出 -3，两个栈都弹一层，当前最小值回到 2。
为什么不能只保存一个 min 变量
如果只用一个变量：
c
minValue = 当前最小值当最小值被弹出时，你不知道“上一个最小值”是谁。
比如：
c
push(5)
push(2)
push(-3)当前最小值是 -3。
如果 pop() 弹出了 -3，新的最小值应该变回 2。
但只靠一个 minValue，你已经忘了之前的最小值历史。
所以要用辅助栈保存每一层的最小值状态。
复杂度
push：O(1)。
pop：O(1)。
top：O(1)。
getMin：O(1)。
空间复杂度是 O(n)，因为除了数据栈，还需要一个辅助最小栈。
面试高分回答
NOTE
最小栈通常用两个栈实现。一个普通栈保存真实数据，另一个辅助栈保存每一层对应的当前最小值。每次 push 时，真实栈压入原值，辅助栈压入 val 和之前最小值中的较小者；每次 pop 时两个栈同时弹出。这样辅助栈的栈顶始终是当前栈中的最小值，所以 getMin() 可以做到 O(1)。这种做法的时间复杂度都是 O(1)，空间复杂度是 O(n)。
二分查找
一句话理解
二分查找就是：在有序数组里，每次看中间元素 mid，如果目标更大就去右半边找，如果目标更小就去左半边找，每次都能排除一半。
前提条件
二分查找必须用于“有序”数据。
比如：
c
[1, 3, 5, 7, 9, 11, 13]如果数组是乱的：
c
[7, 1, 13, 3, 9]就不能直接二分，因为你无法通过 mid 判断目标应该在左边还是右边。
核心过程
假设要找：
c
target = 9数组是：
[1, 3, 5, 7, 9, 11, 13]一开始：
c
left = 0
right = 6
mid = 3
nums[mid] = 7因为：
c
7 < 9说明目标如果存在，一定在右边，所以：
c
left = mid + 1下一轮继续在右半边找。
C++ 标准写法：闭区间
闭区间的意思是：当前查找范围包含 left，也包含 right。
所以循环条件写：
c
left <= right
#include <vector> // 引入 vector 容器，用来保存数组
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
int search(vector<int>& nums, int target) // 定义二分查找函数，找到返回下标，找不到返回 -1
{ // search 函数开始
int left = 0; // left 表示当前查找范围的左边界
int right = nums.size() - 1; // right 表示当前查找范围的右边界
while (left <= right) // 闭区间 [left, right] 还有元素时继续查找
{ // while 循环开始
int mid = left + (right - left) / 2; // 计算中间下标，避免 left + right 可能溢出
if (nums[mid] == target) // 如果中间元素正好等于目标值
{ // if 语句开始
return mid; // 直接返回目标值所在下标
} // if 语句结束
else if (nums[mid] < target) // 如果中间元素小于目标值
{ // else if 语句开始
left = mid + 1; // 目标只可能在右半边，所以左边界移动到 mid 右边
} // else if 语句结束
else // 否则说明中间元素大于目标值
{ // else 语句开始
right = mid - 1; // 目标只可能在左半边，所以右边界移动到 mid 左边
} // else 语句结束
} // while 循环结束
return -1; // 循环结束还没找到，说明目标不存在
} // search 函数结束
}; // Solution 类结束为什么 mid 这样写
推荐写：
c
mid = left + (right - left) / 2而不是：
c
mid = (left + right) / 2因为如果 left 和 right 都很大，left + right 可能整数溢出。
虽然很多面试小数组不会真的溢出，但这么写更专业。
复杂度
时间复杂度是 O(log n)。
因为每次都把查找范围砍掉一半。
比如 1024 个数：
c
1024 -> 512 -> 256 -> 128 -> ... -> 1大约只要查 10 次。
空间复杂度是 O(1)。
因为只用了 left、right、mid 几个变量。
常见坑
第一个坑：数组没排序就用二分。
第二个坑：闭区间写法中，循环条件应该是：
c
left <= right第三个坑：更新边界时要跳过 mid：
c
left = mid + 1
right = mid - 1因为 mid 已经比较过了。
第四个坑：如果要找“第一个等于 target 的位置”或“最后一个等于 target 的位置”，普通二分不够，还要改边界逻辑。
面试高分回答
WARNING
二分查找适用于有序数组。维护左右边界 left 和 right，每次计算中间位置 mid。如果 nums[mid] == target，直接返回；如果 nums[mid] < target，说明目标只可能在右半边，于是令 left = mid + 1；如果 nums[mid] > target，说明目标只可能在左半边，于是令 right = mid - 1。每次都能排除一半数据，所以时间复杂度是 O(log n)，空间复杂度是 O(1)。
搜索旋转排序数组
一句话理解
搜索旋转排序数组，就是在“被旋转过的有序数组”里找 target。它还是用二分查找，但每轮要先判断哪一半是有序的。
题目意思
原本有序数组：
v
[0, 1, 2, 4, 5, 6, 7]旋转后可能变成：
c
[4, 5, 6, 7, 0, 1, 2]现在给你这个旋转数组和一个目标值：
c
target = 0你要返回它的下标。
这里 0 的下标是 4，所以返回：
c
4如果找不到，就返回：
c
-1为什么不能直接普通二分
普通二分要求数组整体有序。
但旋转数组不是整体有序：
c
[4, 5, 6, 7, 0, 1, 2]中间有一个断点：
c
7 -> 0所以不能简单地说：
c
nums[mid] < target 就一定去右边
nums[mid] > target 就一定去左边但是它有一个关键性质：
每次二分时，左半边和右半边至少有一边是有序的。这就是解题关键。
核心判断
每轮都有：
c
left
mid
right先看：
c
nums[left] <= nums[mid]如果成立，说明左半边有序。
否则，说明右半边有序。
然后判断 target 是否在有序的那一半里。
如果在，就保留那一半。
如果不在，就去另一半。
例子走一遍
数组：
c
[4, 5, 6, 7, 0, 1, 2]目标：
target = 0一开始：c#
c
left = 0
right = 6
mid = 3
nums[mid] = 7判断左半边：
c
nums[left] = 4
nums[mid] = 7
4 <= 7所以左半边 [4, 5, 6, 7] 是有序的。
但 target = 0 不在 [4, 7] 之间。
所以目标不可能在左半边，丢掉左半边：
c
left = mid + 1下一轮就在右半边 [0, 1, 2] 里继续二分。
C++ 标准写法
下面这个版本对应 LeetCode 33：数组里没有重复元素。
c
#include <vector> // 引入 vector 容器，用来接收数组
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
int search(vector<int>& nums, int target) // 定义搜索函数，找到 target 返回下标，找不到返回 -1
{ // search 函数开始
int left = 0; // left 表示当前搜索区间的左边界
int right = nums.size() - 1; // right 表示当前搜索区间的右边界
while (left <= right) // 闭区间 [left, right] 还有元素时继续搜索
{ // while 循环开始
int mid = left + (right - left) / 2; // 计算中间下标，避免 left + right 整数溢出
if (nums[mid] == target) // 如果中间值正好等于目标值
{ // if 语句开始
return mid; // 直接返回目标值下标
} // if 语句结束
if (nums[left] <= nums[mid]) // 如果左半边从 left 到 mid 是有序的
{ // if 语句开始
if (nums[left] <= target && target < nums[mid]) // 如果 target 落在左半边有序范围内
{ // if 语句开始
right = mid - 1; // 保留左半边，丢掉 mid 和右半边
} // if 语句结束
else // 否则 target 不在左半边
{ // else 语句开始
left = mid + 1; // 丢掉左半边和 mid，去右半边搜索
} // else 语句结束
} // if 语句结束
else // 否则说明右半边从 mid 到 right 是有序的
{ // else 语句开始
if (nums[mid] < target && target <= nums[right]) // 如果 target 落在右半边有序范围内
{ // if 语句开始
left = mid + 1; // 保留右半边，丢掉左半边和 mid
} // if 语句结束
else // 否则 target 不在右半边
{ // else 语句开始
right = mid - 1; // 丢掉右半边和 mid，去左半边搜索
} // else 语句结束
} // else 语句结束
} // while 循环结束
return -1; // 搜索区间为空还没找到，说明 target 不存在
} // search 函数结束
}; // Solution 类结束为什么边界条件是这样
在左半边有序时：
c
nums[left] <= target && target < nums[mid]这里右边写 < nums[mid]，不是 <= nums[mid]，因为前面已经判断过：
c
nums[mid] == target如果等于早就返回了。
所以这里不需要再包含 mid。
右半边同理：
c
nums[mid] < target && target <= nums[right]mid 已经排除，只判断 mid 右边到 right。
复杂度
时间复杂度是 O(log n)。
因为每轮仍然丢掉一半元素。
空间复杂度是 O(1)。
因为只用了 left、right、mid 几个变量。
常见坑
第一个坑：忘记先判断哪一半有序。
旋转数组不能直接套普通二分。
第二个坑：边界写乱。
建议记住闭区间写法：
c
while (left <= right)
left = mid + 1
right = mid - 1第三个坑：重复元素版本会更复杂。
如果数组里有重复元素，比如：
c
[1, 0, 1, 1, 1]有时 nums[left] == nums[mid]，你无法判断哪边有序，这时通常要移动 left 或 right 去跳过重复，最坏可能退化到 O(n)。
面试高分回答
NOTE
搜索旋转排序数组可以用二分查找。虽然数组整体不是有序的，但每次根据 left、mid、right 切分后，至少有一半是有序的。先判断 nums[left] <= nums[mid]，如果成立说明左半边有序，再判断 target 是否落在 [nums[left], nums[mid]) 中；如果落在里面就搜索左半边，否则搜索右半边。反之说明右半边有序，再判断 target 是否落在 (nums[mid], nums[right]] 中。每轮都能排除一半元素，所以无重复元素时复杂度是 O(log n)。
快速排序
一句话理解
快速排序就是：选一个基准值 pivot，把比它小的放左边，比它大的放右边，然后递归排序左右两边。
核心思想
快速排序分三步：
选一个基准值 pivot。
做 partition 分区，让小于等于 pivot 的元素去左边，大于等于 pivot 的元素去右边。
递归排序 pivot 左边和右边。
比如：
c
[6, 3, 8, 5, 2, 7, 4, 1]选 1 做 pivot。
分区后，1 会被放到它最终应该在的位置。
然后继续对 1 左边、右边做同样的事。
partition 是什么
partition 是快排最关键的步骤。
它的目标不是一次性把整个数组排好，而是先把 pivot 放对位置。
分区完成后一定满足：
c
pivot 左边 <= pivot
pivot 右边 >= pivot所以 pivot 自己已经排好了，后面不需要再动它。
C++ 标准写法
下面用的是比较好理解的 Lomuto 分区法：选最后一个元素作为 pivot。
c
#include <vector> // 引入 vector 容器，用来保存数组
#include <algorithm> // 引入 swap 函数，用来交换两个元素
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义一个排序类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
void quickSort(vector<int>& nums) // 定义快速排序入口函数
{ // quickSort 入口函数开始
if (nums.empty()) // 如果数组为空
{ // if 语句开始
return; // 空数组不需要排序，直接返回
} // if 语句结束
quickSortRange(nums, 0, nums.size() - 1); // 对整个数组区间执行快速排序
} // quickSort 入口函数结束
private: // private 表示下面函数只在类内部使用
void quickSortRange(vector<int>& nums, int left, int right) // 定义对指定区间排序的递归函数
{ // quickSortRange 函数开始
if (left >= right) // 如果区间里没有元素，或者只有一个元素
{ // if 语句开始
return; // 这种区间天然有序，直接返回
} // if 语句结束
int pivotIndex = partition(nums, left, right); // 执行分区，并拿到 pivot 最终位置
quickSortRange(nums, left, pivotIndex - 1); // 递归排序 pivot 左边的区间
quickSortRange(nums, pivotIndex + 1, right); // 递归排序 pivot 右边的区间
} // quickSortRange 函数结束
int partition(vector<int>& nums, int left, int right) // 定义分区函数，把 pivot 放到正确位置
{ // partition 函数开始
int pivot = nums[right]; // 选择最右边的元素作为 pivot
int smaller = left - 1; // smaller 表示“小于等于 pivot 区域”的最后一个位置
for (int current = left; current < right; current++) // 从 left 遍历到 right - 1，不包含 pivot 本身
{ // for 循环开始
if (nums[current] <= pivot) // 如果当前元素小于等于 pivot
{ // if 语句开始
smaller++; // 小于等于区域扩大一格
swap(nums[smaller], nums[current]); // 把当前元素交换到小于等于区域末尾
} // if 语句结束
} // for 循环结束
swap(nums[smaller + 1], nums[right]); // 把 pivot 放到小于等于区域后面，也就是它的最终位置
return smaller + 1; // 返回 pivot 的最终下标
} // partition 函数结束
}; // Solution 类结束为什么递归左右两边
分区之后，pivot 已经在正确位置。
但是左边内部不一定有序，右边内部也不一定有序。
比如：
c
左边都 <= pivot
右边都 >= pivot这只是“大方向对了”，不是全部排好了。
所以还要对左边和右边继续快排，直到区间长度变成 0 或 1。
复杂度
平均时间复杂度是：
c
O(n log n)因为理想情况下，每次分区都能把数组分成差不多两半。
最坏时间复杂度是：
c
O(n²)比如数组本来就有序，而你每次都选最左或最右作为 pivot，分区会非常不均匀。
空间复杂度平均是：
c
O(log n)主要来自递归调用栈。
最坏空间复杂度可能是：
c
O(n)因为递归太深。
快排稳定吗
普通快速排序不稳定。
稳定的意思是：相等元素排序前后的相对顺序不变。
快排在分区时会交换元素，所以相等元素的相对顺序可能改变。
如何避免最坏情况
常见优化：
随机选择 pivot。
三数取中：从左、中、右三个数里选中间大小的作为 pivot。
小区间改用插入排序。
递归时优先处理较小区间，减少栈深度。
工程里的排序通常会做很多混合优化，不只是最朴素快排。
面试高分回答
WARNING
快速排序是一种分治排序算法。它每次选择一个基准值 pivot，通过 partition 操作把数组分成两部分，使左边元素小于等于 pivot，右边元素大于等于 pivot，此时 pivot 已经处在最终位置。然后递归排序左右两个子区间。快排平均时间复杂度是 O(n log n)，最坏情况下会退化到 O(n²)，空间复杂度平均是 O(log n)。普通快排不是稳定排序。为了降低退化概率，常见做法是随机选择 pivot 或三数取中。
归并排序
一句话理解
归并排序就是：先把数组不断拆成很小的有序段，再把两个有序段合并成更大的有序段，最后整个数组就有序了。
核心思想
归并排序分两步：
Divide：把数组从中间不断拆开。
Merge：把两个已经有序的小数组合并成一个更大的有序数组。
比如：
c
[6, 3, 8, 5, 2, 7, 4, 1]先拆到单个元素：
c
[6] [3] [8] [5] [2] [7] [4] [1]单个元素天然有序。
然后开始合并：
c
[6] + [3] -> [3, 6]
[8] + [5] -> [5, 8]
[2] + [7] -> [2, 7]
[4] + [1] -> [1, 4]再继续合并，直到变成完整有序数组。
Merge 是关键
假设有两个有序数组：
c
left = [3, 5, 6, 8]
right = [1, 2, 4, 7]合并时准备两个指针：
i 指向 left 当前元素。
j 指向 right 当前元素。
每次比较：
c
left[i] 和 right[j]谁小就放进临时数组，然后对应指针后移。
最后得到：
c
[1, 2, 3, 4, 5, 6, 7, 8]C++ 标准写法
c
#include <vector> // 引入 vector 容器，用来保存数组和临时数组
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义排序类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
void mergeSort(vector<int>& nums) // 定义归并排序入口函数
{ // mergeSort 函数开始
if (nums.empty()) // 如果数组为空
{ // if 语句开始
return; // 空数组不需要排序，直接返回
} // if 语句结束
vector<int> temp(nums.size()); // 创建临时数组，用来辅助合并
sortRange(nums, temp, 0, nums.size() - 1); // 对整个数组范围执行归并排序
} // mergeSort 函数结束
private: // private 表示下面函数只在类内部使用
void sortRange(vector<int>& nums, vector<int>& temp, int left, int right) // 定义递归排序区间的函数
{ // sortRange 函数开始
if (left >= right) // 如果区间里只有一个元素或者没有元素
{ // if 语句开始
return; // 单个元素天然有序，直接返回
} // if 语句结束
int mid = left + (right - left) / 2; // 计算中间位置，避免 left + right 溢出
sortRange(nums, temp, left, mid); // 递归排序左半边
sortRange(nums, temp, mid + 1, right); // 递归排序右半边
merge(nums, temp, left, mid, right); // 把两个有序半边合并起来
} // sortRange 函数结束
void merge(vector<int>& nums, vector<int>& temp, int left, int mid, int right) // 定义合并两个有序区间的函数
{ // merge 函数开始
int i = left; // i 指向左半边当前元素
int j = mid + 1; // j 指向右半边当前元素
int k = left; // k 指向临时数组当前要写入的位置
while (i <= mid && j <= right) // 当左右两边都还有元素时继续比较
{ // while 循环开始
if (nums[i] <= nums[j]) // 如果左边当前元素小于等于右边当前元素
{ // if 语句开始
temp[k] = nums[i]; // 把左边当前元素放入临时数组
i++; // 左边指针后移一位
} // if 语句结束
else // 否则说明右边当前元素更小
{ // else 语句开始
temp[k] = nums[j]; // 把右边当前元素放入临时数组
j++; // 右边指针后移一位
} // else 语句结束
k++; // 临时数组写入位置后移一位
} // while 循环结束
while (i <= mid) // 如果左半边还有剩余元素
{ // while 循环开始
temp[k] = nums[i]; // 把左半边剩余元素复制到临时数组
i++; // 左边指针后移一位
k++; // 临时数组写入位置后移一位
} // while 循环结束
while (j <= right) // 如果右半边还有剩余元素
{ // while 循环开始
temp[k] = nums[j]; // 把右半边剩余元素复制到临时数组
j++; // 右边指针后移一位
k++; // 临时数组写入位置后移一位
} // while 循环结束
for (int p = left; p <= right; p++) // 遍历当前合并区间
{ // for 循环开始
nums[p] = temp[p]; // 把临时数组中的有序结果拷贝回原数组
} // for 循环结束
} // merge 函数结束
}; // Solution 类结束复杂度
时间复杂度稳定是：
c
O(n log n)因为一共拆成大约 log n 层，每一层合并时都会处理全部 n 个元素。
空间复杂度是：
c
O(n)因为合并时需要临时数组。
归并排序稳定吗
稳定。
稳定的意思是：如果两个元素相等，排序前后它们的相对顺序不变。
代码里用了：
c
nums[i] <= nums[j]相等时优先取左边元素，这样可以保持稳定性。
和快速排序区别
快速排序平均很快，通常原地排序，额外空间少，但最坏可能退化到 O(n²)，而且普通快排不稳定。
归并排序时间稳定，总是 O(n log n)，而且稳定，但需要额外 O(n) 空间。
链表排序里经常用归并排序，因为链表合并很方便，不需要像数组那样频繁随机访问。
面试高分回答
NOTE
归并排序是一种分治排序算法。它先把数组递归拆分成左右两半，直到每个区间只有一个元素，然后再把两个有序区间合并成一个更大的有序区间。合并时使用两个指针分别指向左右区间当前元素，每次取较小者放入临时数组，最后再拷贝回原数组。归并排序时间复杂度稳定为 O(n log n)，空间复杂度是 O(n)，并且它是稳定排序，适合对稳定性有要求的场景，也常用于链表排序和外部排序。
堆排序
一句话理解
堆排序就是：先把数组变成大根堆，让最大值在堆顶；然后每次把堆顶最大值换到数组末尾，再调整剩下的部分继续保持大根堆。
先理解堆排序用什么堆
如果想把数组升序排序：
从小到大通常用大根堆。
因为大根堆的堆顶永远是当前最大值。
每一轮把最大值放到数组最后，最后面的有序区就会越来越大。
堆排序流程
第一步：建大根堆。
比如数组：
c
[6, 3, 8, 5, 2, 7, 4, 1]建成大根堆后，最大值会到 nums[0]。
第二步：交换堆顶和末尾。
c
swap(nums[0], nums[end])这样最大值就被放到了最后。
第三步：缩小堆范围。
最后一个元素已经排好了，不再参与堆调整。
第四步：对堆顶做 heapify。
因为刚换上来的堆顶可能破坏大根堆规则，所以要让它往下沉，直到重新满足父节点大于等于孩子。
重复这个过程，数组就排好了。
为什么 heapify 是下沉
假设堆顶被换成了一个很小的数。
它可能比孩子小，违反大根堆规则。
那就让它和较大的孩子交换。
交换后继续往下看，直到它比孩子都大，或者已经到叶子节点。
这个过程叫：
c
下沉也叫：
c
sift down
heapifyC++ 标准写法
c
#include <vector> // 引入 vector 容器，用来保存数组
#include <algorithm> // 引入 swap 函数，用来交换数组元素
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义排序类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
void heapSort(vector<int>& nums) // 定义堆排序入口函数
{ // heapSort 函数开始
int n = nums.size(); // 保存数组长度
for (int i = n / 2 - 1; i >= 0; i--) // 从最后一个非叶子节点开始向前建堆
{ // for 循环开始
heapify(nums, n, i); // 对当前位置执行下沉调整，让子树满足大根堆
} // for 循环结束
for (int end = n - 1; end > 0; end--) // 从数组末尾开始，把最大值一个个放到最终位置
{ // for 循环开始
swap(nums[0], nums[end]); // 把堆顶最大值交换到当前堆的最后位置
heapify(nums, end, 0); // 缩小堆范围后，从堆顶重新下沉调整
} // for 循环结束
} // heapSort 函数结束
private: // private 表示下面函数只在类内部使用
void heapify(vector<int>& nums, int heapSize, int root) // 定义下沉调整函数，heapSize 表示当前堆大小
{ // heapify 函数开始
int largest = root; // 假设当前 root 是父子三者中最大的
int left = root * 2 + 1; // 根据数组下标计算左孩子位置
int right = root * 2 + 2; // 根据数组下标计算右孩子位置
if (left < heapSize && nums[left] > nums[largest]) // 如果左孩子存在，并且左孩子比当前最大值更大
{ // if 语句开始
largest = left; // 把最大值位置更新为左孩子
} // if 语句结束
if (right < heapSize && nums[right] > nums[largest]) // 如果右孩子存在，并且右孩子比当前最大值更大
{ // if 语句开始
largest = right; // 把最大值位置更新为右孩子
} // if 语句结束
if (largest != root) // 如果最大值不是 root，说明 root 违反了大根堆规则
{ // if 语句开始
swap(nums[root], nums[largest]); // 把 root 和更大的孩子交换
heapify(nums, heapSize, largest); // 交换后继续向下调整被换下去的节点
} // if 语句结束
} // heapify 函数结束
}; // Solution 类结束为什么建堆从 n / 2 - 1 开始
数组表示堆时：
c
左孩子 = 2 * i + 1
右孩子 = 2 * i + 2叶子节点没有孩子，不需要 heapify。
最后一个非叶子节点的位置是：
c
n / 2 - 1所以建堆从这里开始，往前调整到根节点。
复杂度
建堆复杂度是：
c
O(n)排序阶段有 n - 1 轮，每轮 heapify 是：
c
O(log n)所以总时间复杂度是：
c
O(n log n)空间复杂度是：
c
O(1)因为堆排序是在原数组上交换，不需要额外开一个大数组。
堆排序稳定吗
普通堆排序不稳定。
因为它会交换堆顶和末尾元素，可能改变相等元素的相对顺序。
比如两个相同分数的玩家，排序前 A 在 B 前面，堆排序后它们的相对顺序可能变。
和快排、归并排序对比
堆排序：时间稳定 O(n log n)，空间 O(1)，不稳定，缓存局部性一般。
快速排序：平均 O(n log n)，最坏 O(n²)，通常实际很快，不稳定。
归并排序：稳定 O(n log n)，但需要 O(n) 额外空间。
面试高分回答
NOTE
堆排序通常用大根堆实现升序排序。先从最后一个非叶子节点开始向前 heapify，把数组建成大根堆，此时堆顶就是最大值。然后不断把堆顶和当前堆的最后一个元素交换，使最大值进入最终位置，再缩小堆的范围，并从堆顶重新 heapify，恢复大根堆性质。重复这个过程直到堆大小为 1。堆排序时间复杂度是 O(n log n)，空间复杂度是 O(1)，属于原地排序，但普通堆排序不是稳定排序。
Top K 问题
一句话理解
Top K 问题就是：从一堆数据里找出“最大的 K 个”“最小的 K 个”或“频率最高的 K 个”。它不一定需要把所有数据完整排序。
常见题型
比如：
c
nums = [7, 1, 9, 3, 10, 5, 8]
k = 3找最大的 3 个数：
c
[10, 9, 8]注意，很多题只要求找出 Top K，不一定要求这 K 个数内部有序。
方法一：直接排序
最简单的做法：
先排序，再取前 K 个如果是找最大 K 个，就降序排序后取前 K 个。
优点：简单，代码不容易错。
缺点：做了多余工作，因为我们其实只关心前 K 个，不一定需要整个数组都排好。
复杂度：
c
O(n log n)方法二：大小为 K 的小根堆
如果要找最大的 K 个数，最常用的是维护一个大小为 K 的小根堆。
为什么是小根堆？
因为堆里保存“当前最大的 K 个数”，而这 K 个数里最小的那个在堆顶。
每来一个新数 x：
如果堆大小还不到 K，直接放进去。
如果堆已经有 K 个元素，并且 x > 堆顶，说明 x 比当前 Top K 里面最小的数更强，应该替换掉堆顶。
如果 x <= 堆顶，说明它进不了 Top K，直接忽略。
复杂度：
c
O(n log k)当 k 比 n 小很多时，这个方法非常好。
C++ 小根堆写法：找最大 K 个
c
#include <queue> // 引入 priority_queue，用来实现堆
#include <vector> // 引入 vector，用来保存数组和答案
#include <functional> // 引入 greater，用来创建小根堆
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
vector<int> topKLargest(vector<int>& nums, int k) // 定义函数，用来找最大的 k 个数
{ // topKLargest 函数开始
priority_queue<int, vector<int>, greater<int>> heap; // 创建小根堆，堆顶是当前 Top K 中最小的数
for (int num : nums) // 遍历数组中的每一个数字
{ // for 循环开始
if (heap.size() < k) // 如果堆里还不足 k 个数
{ // if 语句开始
heap.push(num); // 直接把当前数字放入堆
} // if 语句结束
else if (num > heap.top()) // 如果当前数字比堆顶更大
{ // else if 语句开始
heap.pop(); // 弹出当前 Top K 中最小的那个数
heap.push(num); // 把更大的当前数字放入堆
} // else if 语句结束
} // for 循环结束
vector<int> result; // 创建结果数组，用来保存最大的 k 个数
while (!heap.empty()) // 只要堆不为空，就继续取出元素
{ // while 循环开始
result.push_back(heap.top()); // 把堆顶元素加入结果数组
heap.pop(); // 弹出堆顶元素
} // while 循环结束
return result; // 返回结果数组，注意这里结果不一定是降序
} // topKLargest 函数结束
}; // Solution 类结束方法三：快速选择 QuickSelect
快速选择和快速排序很像，也用 partition。
快排是：
左右两边都递归排序快速选择是：
c
只去目标所在的一边继续找比如找第 K 大。
每次 partition 后，某个位置已经确定。
如果这个位置正好是第 K 大的位置，就结束。
如果目标在左边，只处理左边。
如果目标在右边，只处理右边。
平均复杂度：
c
O(n)最坏复杂度：
c
O(n²)但随机选 pivot 后，平均表现很好。
三种方法怎么选
| 方法 | 时间复杂度 | 空间复杂度 | 适合场景 |
|---|---|---|---|
| 排序 | O(n log n) | 看排序实现 | 数据不大，想快速写对 |
| K 大小堆 | O(n log k) | O(k) | 数据很大，K 比较小，流式数据 |
| 快速选择 | 平均 O(n) | O(1) 左右 | 只要找到 Top K 分界，不要求内部有序 |
面试高分回答
TIP
Top K 问题不能一上来只说排序。最简单可以排序后取前 K 个，复杂度是 O(n log n)。如果数据量大且 K 比较小，常用大小为 K 的堆，例如找最大 K 个就维护小根堆，堆里始终保存当前最大的 K 个元素，复杂度是 O(n log k)，也适合流式数据。如果只需要找到 Top K 的集合或第 K 大元素，可以用快速选择，利用 partition 每次只递归目标所在的一边，平均复杂度是 O(n)。所以面试里要根据是否要求有序、数据规模、K 的大小、是否流式输入来选择方案。
二叉树前中后序遍历
一句话理解
二叉树的前序、中序、后序，区别就是“根节点什么时候访问”。
先记口诀
前序遍历：
根 -> 左 -> 右中序遍历：
左 -> 根 -> 右后序遍历：
左 -> 右 -> 根注意：左子树永远在右子树前面。前、中、后说的是“根节点”的位置。
举个例子
假设二叉树是：
A
/ \
B C
/ \ / \
D E F G前序遍历：
c
A B D E C F G因为先访问根 A，再访问左子树 B D E，再访问右子树 C F G。
中序遍历：
c
D B E A F C G因为先访问左子树，再访问根 A，最后访问右子树。
后序遍历：
c
D E B F G C A因为先访问左子树，再访问右子树，最后访问根 A。
递归代码
c
#include <iostream> // 引入输入输出库，用来打印遍历结果
using namespace std; // 使用标准命名空间，避免每次写 std::
struct TreeNode // 定义二叉树节点结构体
{ // TreeNode 结构体开始
char val; // 保存当前节点的值
TreeNode* left; // 保存左孩子节点的地址
TreeNode* right; // 保存右孩子节点的地址
TreeNode(char x) : val(x), left(nullptr), right(nullptr) // 构造函数，用 x 初始化节点值，并让左右孩子默认为空
{ // 构造函数开始
} // 构造函数结束
}; // TreeNode 结构体结束
void preorder(TreeNode* root) // 定义前序遍历函数，顺序是根、左、右
{ // preorder 函数开始
if (root == nullptr) // 如果当前节点为空
{ // if 语句开始
return; // 空节点不需要处理，直接返回
} // if 语句结束
cout << root->val << " "; // 先访问根节点
preorder(root->left); // 再递归遍历左子树
preorder(root->right); // 最后递归遍历右子树
} // preorder 函数结束
void inorder(TreeNode* root) // 定义中序遍历函数，顺序是左、根、右
{ // inorder 函数开始
if (root == nullptr) // 如果当前节点为空
{ // if 语句开始
return; // 空节点不需要处理，直接返回
} // if 语句结束
inorder(root->left); // 先递归遍历左子树
cout << root->val << " "; // 再访问根节点
inorder(root->right); // 最后递归遍历右子树
} // inorder 函数结束
void postorder(TreeNode* root) // 定义后序遍历函数，顺序是左、右、根
{ // postorder 函数开始
if (root == nullptr) // 如果当前节点为空
{ // if 语句开始
return; // 空节点不需要处理，直接返回
} // if 语句结束
postorder(root->left); // 先递归遍历左子树
postorder(root->right); // 再递归遍历右子树
cout << root->val << " "; // 最后访问根节点
} // postorder 函数结束它们分别适合什么场景
前序遍历常用于“先处理自己，再处理孩子”的场景。
比如：复制一棵树、序列化树、打印目录结构。
中序遍历常用于二叉搜索树。
因为二叉搜索树满足左小右大，所以中序遍历会得到升序结果。
后序遍历常用于“先处理孩子，再处理自己”的场景。
比如：释放整棵树、删除目录、计算文件夹大小、表达式树求值。复杂度
时间复杂度都是：
c
O(n)因为每个节点都会访问一次。
空间复杂度是：
c
O(h)其中 h 是树的高度，主要来自递归调用栈。
如果树很平衡，h 大约是 log n。
如果树退化成链表，h 可能是 n。
面试高分回答
NOTE
前序、中序、后序遍历都是深度优先遍历。它们的区别在于访问根节点的时机：前序是根左右，中序是左根右，后序是左右根。对于同一棵树，左子树总是在右子树之前被处理。前序常用于复制或序列化树，中序遍历二叉搜索树可以得到有序序列，后序适合先处理子节点再处理父节点的场景，比如释放树或计算子树信息。三种遍历时间复杂度都是 O(n)。
二叉树层序遍历
一句话理解
二叉树层序遍历就是：从上到下、从左到右，一层一层访问节点。它本质是 BFS，通常用队列 queue 实现。
例子
假设二叉树是：
A
/ \
B C
/ \ / \
D E F G层序遍历结果是：
c
A B C D E F G如果题目要求“按层返回”，结果就是：
c
[[A], [B, C], [D, E, F, G]]为什么用队列
队列是先进先出。
先把根节点放进队列。
每次从队头取出一个节点，访问它。
然后把它的左孩子、右孩子放到队尾。
这样就能保证：上一层的节点一定比下一层的节点先被处理。
C++ 代码：按层返回
c
#include <queue> // 引入 queue 容器，用来做广度优先遍历
#include <vector> // 引入 vector 容器，用来保存每一层的结果
using namespace std; // 使用标准命名空间，避免每次写 std::
struct TreeNode // 定义二叉树节点结构体
{ // TreeNode 结构体开始
int val; // 保存当前节点的值
TreeNode* left; // 保存左孩子节点地址
TreeNode* right; // 保存右孩子节点地址
TreeNode(int x) : val(x), left(nullptr), right(nullptr) // 构造函数，用 x 初始化节点值，并让左右孩子默认为空
{ // 构造函数开始
} // 构造函数结束
}; // TreeNode 结构体结束
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
vector<vector<int>> levelOrder(TreeNode* root) // 定义层序遍历函数，按层返回节点值
{ // levelOrder 函数开始
vector<vector<int>> result; // 创建结果数组，用来保存每一层的节点值
if (root == nullptr) // 如果根节点为空
{ // if 语句开始
return result; // 空树没有节点，直接返回空结果
} // if 语句结束
queue<TreeNode*> q; // 创建队列，用来保存等待访问的节点
q.push(root); // 先把根节点放入队列
while (!q.empty()) // 只要队列不为空，就继续遍历
{ // while 循环开始
int levelSize = q.size(); // 记录当前层有多少个节点
vector<int> currentLevel; // 创建数组，用来保存当前层的节点值
for (int i = 0; i < levelSize; i++) // 只处理当前层的这些节点
{ // for 循环开始
TreeNode* node = q.front(); // 取出队头节点
q.pop(); // 把队头节点从队列中弹出
currentLevel.push_back(node->val); // 把当前节点的值加入当前层结果
if (node->left != nullptr) // 如果当前节点有左孩子
{ // if 语句开始
q.push(node->left); // 把左孩子放入队列，等待下一层处理
} // if 语句结束
if (node->right != nullptr) // 如果当前节点有右孩子
{ // if 语句开始
q.push(node->right); // 把右孩子放入队列，等待下一层处理
} // if 语句结束
} // for 循环结束
result.push_back(currentLevel); // 当前层处理完后，把这一层结果加入总结果
} // while 循环结束
return result; // 返回所有层的遍历结果
} // levelOrder 函数结束
}; // Solution 类结束为什么要记录 levelSize
如果只是普通遍历，可以一直弹队列。
但如果题目要求：
每一层单独放一个数组那就必须知道“当前层有几个节点”。
所以每一轮 while 开始时记录：
c
levelSize = q.size()然后只处理这 levelSize 个节点。
处理这些节点时，新加入队列的孩子节点属于下一层，不能混到当前层里。
复杂度
时间复杂度是 O(n)。
因为每个节点都会进队一次、出队一次。
空间复杂度是 O(w)。
w 是树的最大宽度。最坏情况下，队列里可能放下某一整层的节点，所以也可以说最坏是 O(n)。
面试高分回答
NOTE
二叉树层序遍历本质是广度优先搜索 BFS，通常用队列实现。先把根节点入队，然后循环取出队头节点并访问它，再把它的左孩子和右孩子依次入队。由于队列先进先出，所以可以保证节点按从上到下、从左到右的顺序被访问。如果题目要求按层返回，就在每轮循环开始时记录当前队列大小 levelSize，只处理这 levelSize 个节点，它们正好属于当前层。时间复杂度是 O(n)，空间复杂度最坏是 O(n)。
二叉树最大深度
一句话理解
二叉树最大深度，就是从根节点走到最远叶子节点，最多经过多少层节点。
先看定义
如果树是空的：
深度 = 0如果只有一个根节点：
深度 = 1如果最长路径是：
A -> B -> D -> H一共经过 4 个节点，那么最大深度就是：
4递归思路
对任意一个节点来说，它的最大深度等于：
左子树最大深度 和 右子树最大深度 的较大值 + 1公式就是：
c
maxDepth(root) = max(maxDepth(root->left), maxDepth(root->right)) + 1为什么要 +1？
因为左子树和右子树算的是孩子下面的深度，而当前 root 自己也占一层。
C++ 递归写法
c
#include <algorithm> // 引入 max 函数，用来比较左右子树深度
using namespace std; // 使用标准命名空间，避免每次写 std::
struct TreeNode // 定义二叉树节点结构体
{ // TreeNode 结构体开始
int val; // 保存当前节点的值
TreeNode* left; // 保存左孩子节点地址
TreeNode* right; // 保存右孩子节点地址
TreeNode(int x) : val(x), left(nullptr), right(nullptr) // 构造函数，用 x 初始化节点值，并让左右孩子默认为空
{ // 构造函数开始
} // 构造函数结束
}; // TreeNode 结构体结束
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
int maxDepth(TreeNode* root) // 定义求二叉树最大深度的函数
{ // maxDepth 函数开始
if (root == nullptr) // 如果当前节点为空
{ // if 语句开始
return 0; // 空树深度是 0
} // if 语句结束
int leftDepth = maxDepth(root->left); // 递归求左子树最大深度
int rightDepth = maxDepth(root->right); // 递归求右子树最大深度
return max(leftDepth, rightDepth) + 1; // 当前树深度等于左右较大深度加上当前节点这一层
} // maxDepth 函数结束
}; // Solution 类结束为什么递归这么自然
因为二叉树本身就是递归结构：
一棵树 = 根节点 + 左子树 + 右子树求整棵树的最大深度，就要先知道左子树和右子树的最大深度。
然后取更深的一边，再加上当前根节点这一层。
层序遍历写法
也可以用队列一层一层遍历。
每遍历完一层，深度 +1。
c
#include <queue> // 引入 queue 容器，用来做层序遍历
using namespace std; // 使用标准命名空间，避免每次写 std::
struct TreeNode // 定义二叉树节点结构体
{ // TreeNode 结构体开始
int val; // 保存当前节点的值
TreeNode* left; // 保存左孩子节点地址
TreeNode* right; // 保存右孩子节点地址
TreeNode(int x) : val(x), left(nullptr), right(nullptr) // 构造函数，用 x 初始化节点值，并让左右孩子默认为空
{ // 构造函数开始
} // 构造函数结束
}; // TreeNode 结构体结束
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
int maxDepth(TreeNode* root) // 定义求二叉树最大深度的函数
{ // maxDepth 函数开始
if (root == nullptr) // 如果根节点为空
{ // if 语句开始
return 0; // 空树深度是 0
} // if 语句结束
queue<TreeNode*> q; // 创建队列，用来保存等待遍历的节点
q.push(root); // 先把根节点放入队列
int depth = 0; // depth 用来记录已经遍历了多少层
while (!q.empty()) // 只要队列不为空，就说明还有层没有遍历
{ // while 循环开始
int levelSize = q.size(); // 记录当前层有多少个节点
for (int i = 0; i < levelSize; i++) // 只处理当前层的节点
{ // for 循环开始
TreeNode* node = q.front(); // 取出队头节点
q.pop(); // 弹出队头节点
if (node->left != nullptr) // 如果当前节点有左孩子
{ // if 语句开始
q.push(node->left); // 把左孩子放入队列，等待下一层处理
} // if 语句结束
if (node->right != nullptr) // 如果当前节点有右孩子
{ // if 语句开始
q.push(node->right); // 把右孩子放入队列，等待下一层处理
} // if 语句结束
} // for 循环结束
depth++; // 当前层处理完，深度加 1
} // while 循环结束
return depth; // 返回最终层数，也就是最大深度
} // maxDepth 函数结束
}; // Solution 类结束复杂度
时间复杂度是：
O(n)因为每个节点都会被访问一次。
递归写法空间复杂度是：
O(h)h 是树的高度，来自递归调用栈。
层序遍历空间复杂度最坏是：
O(n)因为队列可能存下某一层很多节点。
面试高分回答
WARNING
二叉树最大深度可以用递归求解。对于空节点，深度为 0；对于非空节点，它的最大深度等于左子树最大深度和右子树最大深度的较大值，再加上当前节点这一层，也就是 max(leftDepth, rightDepth) + 1。这个方法本质是 DFS，时间复杂度是 O(n)，空间复杂度是 O(h)。也可以用层序遍历 BFS，每遍历完一层就让深度加一。
最近公共祖先
一句话理解
最近公共祖先 LCA，就是两个节点共同的祖先里，离它们最近的那个节点。
先理解什么是祖先
在二叉树里，一个节点往上走能经过的节点，都叫它的祖先。
比如这棵树：
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4节点 6 的祖先路径是：
6 -> 5 -> 3节点 4 的祖先路径是：
4 -> 2 -> 5 -> 3它们的公共祖先有：
5 和 3但 5 离它们更近，所以：
LCA(6, 4) = 5注意：一个节点也可以是自己的祖先。所以如果问 LCA(5, 4)，答案就是 5。
普通二叉树怎么做
普通二叉树没有大小规则，不能像二叉搜索树那样比较大小。
所以常用递归。
递归函数的含义可以这样理解：
在当前 root 这棵树里，寻找 p 或 q。如果当前节点是空：
返回 nullptr如果当前节点就是 p 或 q：
返回当前节点否则分别去左子树和右子树找：
left = 在左子树里找
right = 在右子树里找然后看结果：
如果 left 和 right 都不为空，说明 p 和 q 分别在当前节点两边，当前节点就是最近公共祖先。
如果只有 left 不为空，说明答案在左边，返回 left。
如果只有 right 不为空，说明答案在右边，返回 right。
如果都为空，说明这棵子树里没有目标，返回空。
C++ 普通二叉树写法
c
struct TreeNode // 定义二叉树节点结构体
{ // TreeNode 结构体开始
int val; // 保存当前节点的值
TreeNode* left; // 保存左孩子节点地址
TreeNode* right; // 保存右孩子节点地址
TreeNode(int x) : val(x), left(nullptr), right(nullptr) // 构造函数，用 x 初始化节点值，并让左右孩子默认为空
{ // 构造函数开始
} // 构造函数结束
}; // TreeNode 结构体结束
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) // 定义求最近公共祖先的函数
{ // lowestCommonAncestor 函数开始
if (root == nullptr) // 如果当前节点为空
{ // if 语句开始
return nullptr; // 空树里找不到 p 或 q，返回空
} // if 语句结束
if (root == p || root == q) // 如果当前节点本身就是 p 或 q
{ // if 语句开始
return root; // 直接返回当前节点，因为一个节点可以是自己的祖先
} // if 语句结束
TreeNode* left = lowestCommonAncestor(root->left, p, q); // 去左子树寻找 p 或 q
TreeNode* right = lowestCommonAncestor(root->right, p, q); // 去右子树寻找 p 或 q
if (left != nullptr && right != nullptr) // 如果左右子树都找到了目标节点
{ // if 语句开始
return root; // 说明 p 和 q 分别在两边，当前 root 就是最近公共祖先
} // if 语句结束
if (left != nullptr) // 如果只有左子树找到了目标或答案
{ // if 语句开始
return left; // 把左子树找到的结果继续往上返回
} // if 语句结束
return right; // 否则返回右子树结果，可能是某个目标节点，也可能是空
} // lowestCommonAncestor 函数结束
}; // Solution 类结束为什么左右都不为空时 root 是答案
因为：
c
left != nullptr说明 p 或 q 在左子树里。
c
right != nullptr说明另一个目标在右子树里。
它们一个在左，一个在右，第一次能把它们汇合起来的节点，就是当前 root。
所以当前 root 就是最近公共祖先。
二叉搜索树的更快写法
如果题目明确说是二叉搜索树 BST，可以利用性质：
左子树所有值小于根。
右子树所有值大于根。
如果 p 和 q 都比 root 小，答案在左边。
如果 p 和 q 都比 root 大，答案在右边。
否则说明一个在左、一个在右，或者当前 root 就是其中一个节点，那么 root 就是最近公共祖先。
c
struct TreeNode // 定义二叉树节点结构体
{ // TreeNode 结构体开始
int val; // 保存当前节点的值
TreeNode* left; // 保存左孩子节点地址
TreeNode* right; // 保存右孩子节点地址
TreeNode(int x) : val(x), left(nullptr), right(nullptr) // 构造函数，用 x 初始化节点值，并让左右孩子默认为空
{ // 构造函数开始
} // 构造函数结束
}; // TreeNode 结构体结束
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) // 定义 BST 最近公共祖先函数
{ // lowestCommonAncestor 函数开始
while (root != nullptr) // 只要当前节点不为空，就继续查找
{ // while 循环开始
if (p->val < root->val && q->val < root->val) // 如果 p 和 q 都比 root 小
{ // if 语句开始
root = root->left; // 说明最近公共祖先一定在左子树
} // if 语句结束
else if (p->val > root->val && q->val > root->val) // 如果 p 和 q 都比 root 大
{ // else if 语句开始
root = root->right; // 说明最近公共祖先一定在右子树
} // else if 语句结束
else // 否则说明 p 和 q 分散在 root 两侧，或者 root 就是其中一个节点
{ // else 语句开始
return root; // 当前 root 就是最近公共祖先
} // else 语句结束
} // while 循环结束
return nullptr; // 如果树为空或没有找到，就返回空
} // lowestCommonAncestor 函数结束
}; // Solution 类结束复杂度
普通二叉树递归写法：
时间复杂度是 O(n)，最坏要访问所有节点。
空间复杂度是 O(h)，h 是树高，来自递归调用栈。
二叉搜索树写法：
时间复杂度是 O(h)。
如果树平衡，约等于 O(log n)。
如果树退化成链表，最坏是 O(n)。
面试高分回答
TIP
最近公共祖先是两个节点共同祖先中距离它们最近的那个节点。普通二叉树没有大小关系，常用递归：如果当前节点为空返回空；如果当前节点等于 p 或 q，返回当前节点；然后分别在左右子树查找。如果左右子树都返回非空，说明两个目标分别在当前节点两侧，当前节点就是最近公共祖先；如果只有一边非空，就把那边结果向上返回。这个方法时间复杂度是 O(n)。如果是二叉搜索树，可以利用左小右大的性质，根据 p 和 q 与当前节点值的大小关系决定往左还是往右，复杂度是 O(h)。
岛屿数量
一句话理解
“岛屿数量”就是在二维网格里数有多少块互不连通的陆地。遇到一块新的 1，岛屿数 +1，然后用 DFS/BFS 把和它上下左右连着的所有 1 都标记掉。
题目意思
网格里：
'1' 表示陆地
'0' 表示水如果多个陆地通过“上、下、左、右”连在一起，它们算同一座岛。
注意：斜着连不算。
比如：
1 1 0 0
1 0 0 1
0 0 1 1左上角那几个 1 是一座岛；右边连着的 1 是另一座岛。
核心思路
从左到右、从上到下扫描整个网格。
如果遇到 0，跳过。
如果遇到 1，说明发现了一座新岛：
c
count++然后从这个 1 出发，用 DFS 把这座岛上所有相连的 1 都标记为已访问。
常见做法是直接把访问过的 1 改成 0，可以理解成“把这座岛淹掉”。
这样后面扫描到同一座岛的其他格子时，就不会重复计数。
C++ DFS 写法
c
#include <vector> // 引入 vector 容器，用来保存二维网格
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
int numIslands(vector<vector<char>>& grid) // 定义计算岛屿数量的函数
{ // numIslands 函数开始
if (grid.empty()) // 如果网格为空
{ // if 语句开始
return 0; // 空网格没有岛屿，直接返回 0
} // if 语句结束
int rows = grid.size(); // 保存网格的行数
int cols = grid[0].size(); // 保存网格的列数
int count = 0; // count 用来记录岛屿数量
for (int r = 0; r < rows; r++) // 从第一行遍历到最后一行
{ // 外层 for 循环开始
for (int c = 0; c < cols; c++) // 从当前行第一列遍历到最后一列
{ // 内层 for 循环开始
if (grid[r][c] == '1') // 如果当前格子是还没访问过的陆地
{ // if 语句开始
count++; // 发现一座新岛，岛屿数量加 1
dfs(grid, r, c, rows, cols); // 从当前陆地出发，把整座岛标记掉
} // if 语句结束
} // 内层 for 循环结束
} // 外层 for 循环结束
return count; // 返回最终岛屿数量
} // numIslands 函数结束
private: // private 表示下面函数只在类内部使用
void dfs(vector<vector<char>>& grid, int r, int c, int rows, int cols) // 定义 DFS 函数，用来淹掉一整座岛
{ // dfs 函数开始
if (r < 0 || r >= rows || c < 0 || c >= cols) // 如果当前位置越过网格边界
{ // if 语句开始
return; // 越界位置不能继续搜索，直接返回
} // if 语句结束
if (grid[r][c] == '0') // 如果当前位置是水，或者已经被标记访问过
{ // if 语句开始
return; // 水不能扩展岛屿，直接返回
} // if 语句结束
grid[r][c] = '0'; // 把当前陆地改成水，表示已经访问过
dfs(grid, r - 1, c, rows, cols); // 向上搜索相邻陆地
dfs(grid, r + 1, c, rows, cols); // 向下搜索相邻陆地
dfs(grid, r, c - 1, rows, cols); // 向左搜索相邻陆地
dfs(grid, r, c + 1, rows, cols); // 向右搜索相邻陆地
} // dfs 函数结束
}; // Solution 类结束为什么这样不会重复数
假设扫描到第一块陆地：
c
count++然后 DFS 会把和它连着的所有陆地都改成 0。
后面循环再走到这座岛的其他格子时，看到的已经是 0，所以不会再 count++。
这就是“发现一座，清理一整座”。
复杂度
时间复杂度是 O(m * n)。
因为每个格子最多被访问一次。
空间复杂度最坏是 O(m * n)。
因为如果整张图都是陆地，DFS 递归栈最深可能接近格子总数。
面试高分回答
TIP
岛屿数量可以用 DFS 或 BFS。遍历整个网格，遇到一个未访问过的陆地 1，说明发现一座新岛，岛屿数加一。然后从这个格子出发，向上下左右四个方向搜索，把所有连通的陆地都标记为已访问，常见做法是直接把 1 改成 0。这样同一座岛不会被重复统计。整个过程中每个格子最多访问一次，所以时间复杂度是 O(m*n)。
BFS 最短路径
一句话理解
BFS 最短路径就是：从起点开始一层一层向外扩散，先到达的点距离一定更短。所以在“无权图”或“每一步代价相同”的地图里，BFS 第一次到达终点时，就是最短路径。
核心前提
BFS 能求最短路径，有一个非常重要的前提：
每条边的代价相同比如网格里每走一格都算 1 步，这种就适合 BFS。
如果有的路代价是 1，有的路代价是 5，那 BFS 就不适合了，要用 Dijkstra。
如果是游戏寻路，并且想更快朝目标方向搜索，常见会用 A*。
为什么第一次到终点就是最短
BFS 的访问顺序是：
距离起点 0 步
距离起点 1 步
距离起点 2 步
距离起点 3 步
...它不会先处理远的点，再回头处理近的点。
所以当 BFS 第一次遇到终点时，说明更短距离的所有可能都已经检查过了。
这就是 BFS 能求无权最短路径的根本原因。
网格 BFS 代码
下面代码里，0 表示能走，1 表示障碍。返回从起点到终点的最短步数，走不到就返回 -1。
c
#include <queue> // 引入 queue，用来实现 BFS 的先进先出队列
#include <vector> // 引入 vector，用来保存二维网格和距离数组
#include <utility> // 引入 pair，用来保存格子的行列坐标
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
int shortestPath(vector<vector<int>>& grid, pair<int, int> start, pair<int, int> target) // 定义 BFS 最短路径函数
{ // shortestPath 函数开始
int rows = grid.size(); // 获取网格行数
int cols = grid[0].size(); // 获取网格列数
vector<vector<int>> dist(rows, vector<int>(cols, -1)); // 创建距离数组，-1 表示还没有访问过
queue<pair<int, int>> q; // 创建 BFS 队列，队列里保存待处理格子的坐标
q.push(start); // 把起点放入队列
dist[start.first][start.second] = 0; // 起点到起点的距离是 0
int dr[4] = {-1, 1, 0, 0}; // 四个方向的行变化，分别表示上、下、左、右
int dc[4] = {0, 0, -1, 1}; // 四个方向的列变化，分别表示上、下、左、右
while (!q.empty()) // 只要队列不为空，就继续 BFS
{ // while 循环开始
pair<int, int> current = q.front(); // 取出队头格子
q.pop(); // 弹出队头格子
int r = current.first; // 取出当前格子的行号
int c = current.second; // 取出当前格子的列号
if (current == target) // 如果当前格子就是终点
{ // if 语句开始
return dist[r][c]; // 返回起点到终点的最短距离
} // if 语句结束
for (int i = 0; i < 4; i++) // 遍历上下左右四个方向
{ // for 循环开始
int nr = r + dr[i]; // 计算邻居格子的行号
int nc = c + dc[i]; // 计算邻居格子的列号
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) // 如果邻居越界
{ // if 语句开始
continue; // 越界格子不能走，跳过
} // if 语句结束
if (grid[nr][nc] == 1) // 如果邻居是障碍
{ // if 语句开始
continue; // 障碍不能走，跳过
} // if 语句结束
if (dist[nr][nc] != -1) // 如果邻居已经访问过
{ // if 语句开始
continue; // 已访问格子已经有最短距离，不重复入队
} // if 语句结束
dist[nr][nc] = dist[r][c] + 1; // 邻居距离等于当前距离加 1
q.push({nr, nc}); // 把邻居加入队列，等待后续处理
} // for 循环结束
} // while 循环结束
return -1; // 队列空了还没到终点，说明不可达
} // shortestPath 函数结束
}; // Solution 类结束为什么要 dist 数组
dist[r][c] 有两个作用。
第一个作用：记录起点到当前格子的最短距离。
第二个作用：判断这个格子有没有访问过。
如果 dist[r][c] == -1，说明没访问过。
如果不是 -1，说明已经访问过，而且第一次访问时的距离就是最短距离。
如果要返回路径本身
如果题目不只要步数，还要具体路径，比如：
c
S -> ... -> E那就额外开一个 parent 数组。
每次把邻居入队时，记录：
c
parent[neighbor] = current最后从终点一路通过 parent 倒着走回起点，再反转一下，就是完整路径。
面试高分回答
CAUTION
BFS 求最短路径适用于无权图或所有边权相同的图。它从起点开始按层扩散，先访问距离为 1 的节点，再访问距离为 2 的节点，因此第一次到达终点时，路径长度一定最短。实现上通常使用队列保存待访问节点，并用 visited 或 dist 数组避免重复访问。对于网格题，每次从当前格子向上下左右四个方向扩展；对于普通图，则遍历当前节点的邻接表。时间复杂度是 O(V + E)，网格里就是 O(m*n)。
DFS 回溯
一句话理解
DFS 回溯就是：沿着一条路往深处试，试完以后撤销刚才的选择，再换另一条路继续试。
DFS 和回溯的关系
DFS 是“往深处走”的搜索方式。
回溯 是“走完一条路后，恢复现场，再试下一条路”。
所以回溯常常写成：
做选择
递归
撤销选择比如你在生成全排列：
[1, 2, 3]你先选 1，再选 2，再选 3，得到：
[1, 2, 3]记录答案后，要撤销 3，再尝试别的选择。否则后面的分支会被前面的选择污染。
回溯模板
核心模板可以这样记：
如果满足结束条件：
记录答案
返回
遍历当前可选项：
做选择
递归进入下一层
撤销选择最关键的是最后一步：
撤销选择没有撤销，就不是完整的回溯。
C++ 例子：全排列
下面代码用回溯生成 [1,2,3] 的所有排列。
c
#include <vector> // 引入 vector 容器，用来保存输入数组、路径和答案
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
vector<vector<int>> permute(vector<int>& nums) // 定义全排列函数，输入 nums，返回所有排列
{ // permute 函数开始
vector<vector<int>> result; // 创建结果数组，用来保存所有完整排列
vector<int> path; // 创建路径数组，用来保存当前正在构造的排列
vector<bool> used(nums.size(), false); // 创建 used 数组，用来标记每个数字是否已经被当前路径使用
dfs(nums, used, path, result); // 从空路径开始执行 DFS 回溯
return result; // 返回所有排列结果
} // permute 函数结束
private: // private 表示下面函数只在类内部使用
void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& result) // 定义 DFS 回溯函数
{ // dfs 函数开始
if (path.size() == nums.size()) // 如果当前路径长度已经等于 nums 长度
{ // if 语句开始
result.push_back(path); // 说明得到一个完整排列，把它加入答案
return; // 当前分支结束，返回上一层
} // if 语句结束
for (int i = 0; i < nums.size(); i++) // 遍历每一个可能选择的数字
{ // for 循环开始
if (used[i]) // 如果 nums[i] 已经在当前路径里用过
{ // if 语句开始
continue; // 当前数字不能重复使用，跳过它
} // if 语句结束
used[i] = true; // 做选择：标记 nums[i] 已经被使用
path.push_back(nums[i]); // 做选择：把 nums[i] 放入当前路径
dfs(nums, used, path, result); // 递归：进入下一层，继续选择下一个数字
path.pop_back(); // 撤销选择：把刚才加入路径的 nums[i] 移除
used[i] = false; // 撤销选择：恢复 nums[i] 为未使用状态
} // for 循环结束
} // dfs 函数结束
}; // Solution 类结束为什么要 used 数组
全排列里，每个数字只能用一次。
比如已经选了：
[1, 2]下一层就不能再选 1 或 2。
所以用：
c
used[i] = true表示这个数字已经在当前路径里。
当递归回来后，要恢复：
c
used[i] = false这样别的分支还能正常使用它。
为什么要 path.pop_back()
假设当前路径是：
[1, 2, 3]这条分支结束后，要回到：
[1, 2]然后尝试其他可能。
如果不 pop_back()，路径会一直残留之前的数字，后续答案就乱了。
这就是“回溯”的意义：走完以后恢复现场。
适合哪些题
DFS 回溯常见于这些题：
全排列。
组合。
子集。
括号生成。
电话号码字母组合。
N 皇后。
数独。
单词搜索。
棋盘路径搜索。
只要题目像“从一堆选择里试出所有合法答案”，大概率可以考虑回溯。复杂度怎么说
回溯题复杂度通常和“搜索树大小”有关。
全排列有：
n!种结果，所以时间复杂度大约是：
O(n * n!)这里多出来的 n，通常来自复制路径到答案。
空间复杂度主要是递归深度和路径：
O(n)如果把结果数组也算进去，那会更大，因为要存所有答案。
面试高分回答
NOTE
DFS 回溯是一种试探式搜索。它会在当前层枚举所有可选项，先做一个选择，把它加入当前路径，然后递归进入下一层；当这一条路径搜索完成后，再撤销刚才的选择，恢复现场，继续尝试其他分支。它常用于全排列、组合、子集、N 皇后、数独、路径搜索等需要枚举所有可能解的问题。核心模板就是：终止条件、遍历选择、做选择、递归、撤销选择。回溯的关键是撤销操作，否则前一个分支的状态会影响后一个分支。
全排列
全排列是什么？ 全排列就是：给你一组数字，把它们所有可能的排列顺序都列出来。
比如：
[1, 2, 3]它的全排列有：
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]如果有 n 个不同数字，全排列数量是：
n!也就是：
3 个数：3 * 2 * 1 = 6 种
4 个数：4 * 3 * 2 * 1 = 24 种核心思想：回溯
全排列是非常经典的回溯题。
你可以把它想成：
当前位置要填一个数字
从还没用过的数字里选一个
选完继续往下填
填完一个完整排列后，退回来换另一个数字回溯里有三个关键东西：
path：当前正在拼的排列
used：某个数字是否已经用过
result：保存所有完整排列C++ 代码
c
#include <vector> // 引入 vector 容器，用来保存输入数组、路径和答案
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
vector<vector<int>> permute(vector<int>& nums) // 定义全排列函数，输入 nums，返回所有排列
{ // permute 函数开始
vector<vector<int>> result; // 创建结果数组，用来保存所有完整排列
vector<int> path; // 创建路径数组，用来保存当前正在构造的排列
vector<bool> used(nums.size(), false); // 创建 used 数组，用来标记每个数字是否已经被当前路径使用
dfs(nums, used, path, result); // 从空路径开始执行 DFS 回溯
return result; // 返回所有排列结果
} // permute 函数结束
private: // private 表示下面函数只在类内部使用
void dfs(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& result) // 定义 DFS 回溯函数
{ // dfs 函数开始
if (path.size() == nums.size()) // 如果当前路径长度已经等于 nums 长度
{ // if 语句开始
result.push_back(path); // 说明得到一个完整排列，把它加入答案
return; // 当前分支结束，返回上一层
} // if 语句结束
for (int i = 0; i < nums.size(); i++) // 遍历每一个可能选择的数字
{ // for 循环开始
if (used[i]) // 如果 nums[i] 已经在当前路径里用过
{ // if 语句开始
continue; // 当前数字不能重复使用，跳过它
} // if 语句结束
used[i] = true; // 做选择：标记 nums[i] 已经被使用
path.push_back(nums[i]); // 做选择：把 nums[i] 放入当前路径
dfs(nums, used, path, result); // 递归：进入下一层，继续选择下一个数字
path.pop_back(); // 撤销选择：把刚才加入路径的 nums[i] 移除
used[i] = false; // 撤销选择：恢复 nums[i] 为未使用状态
} // for 循环结束
} // dfs 函数结束
}; // Solution 类结束为什么要 used？
因为全排列里，一个数字在同一个排列中只能出现一次。
比如 [1, 2, 3]，如果当前 path 已经是：
[1, 2]那么下一步就不能再选 1 或 2，只能选 3。
所以 used[i] 的作用就是告诉我们：
nums[i] 当前这条递归路径里用没用过为什么要 pop_back？
因为递归回来之后，要尝试别的选择。
比如先走：
[1, 2, 3]走完之后，要退回到：
[1, 2]再退回到：
[1]然后尝试：
[1, 3, 2]这个“退回来”的动作，就是：
c
path.pop_back();
used[i] = false;复杂度
时间复杂度：
c
O(n * n!)因为一共有 n! 个排列，每个排列复制进答案时长度是 n。
空间复杂度：
c
O(n)这是递归深度、path 和 used 的辅助空间。 如果把结果数组也算进去，就是：
c
O(n * n!)面试高分回答
IMPORTANT
全排列是典型回溯问题。每一层递归表示当前位置要选择一个数字，从所有未使用的数字里选择一个加入 path，然后继续递归下一层。当 path 长度等于输入数组长度时，说明得到一个完整排列，把它加入结果集。递归返回后要撤销选择，也就是 pop_back 并恢复 used 状态，这样才能继续尝试其他分支。关键点是：used 防止同一个排列里重复使用元素，撤销选择防止不同递归分支互相污染。
子集
子集是什么？ 子集就是：给你一个数组，每个元素都可以选择“要”或者“不要”，最后把所有可能的选择结果列出来。
比如：
nums = [1, 2, 3]它的子集有：
c
[]
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]如果有 n 个元素，每个元素都有两种选择：选 / 不选，所以子集数量是：
c
2^n它和全排列的区别
全排列是：
所有数字都要用上，只是顺序不同。子集是：
数字可以不用，重点是选了哪些数字。比如 [1, 2, 3]：
[1, 2, 3] 是一个排列，也是一个子集
[1, 2] 不是全排列，但它是子集
[] 空集也是子集核心思路：回溯
子集题可以这样想：
从当前位置开始
每次选择一个数字加入 path
把当前 path 加入答案
然后继续往后选择
回来之后撤销选择这里最重要的是：
下一层递归从 i + 1 开始为什么？
因为子集不关心顺序。
如果已经选了 1，后面只能继续选 2、3。 不能再回头选 1 前面的东西，否则会出现重复组合。
C++ 代码
c
#include <vector> // 引入 vector 容器，用来保存数组、路径和答案
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面的函数可以被外部调用
vector<vector<int>> subsets(vector<int>& nums) // 定义求子集函数，输入 nums，返回所有子集
{ // subsets 函数开始
vector<vector<int>> result; // 创建结果数组，用来保存所有子集
vector<int> path; // 创建路径数组，用来保存当前正在构造的子集
dfs(nums, 0, path, result); // 从下标 0 开始执行回溯
return result; // 返回所有子集
} // subsets 函数结束
private: // private 表示下面的函数只在类内部使用
void dfs(vector<int>& nums, int startIndex, vector<int>& path, vector<vector<int>>& result) // 定义 DFS 回溯函数
{ // dfs 函数开始
result.push_back(path); // 把当前 path 加入答案，因为每一个 path 都是一个合法子集
for (int i = startIndex; i < nums.size(); i++) // 从 startIndex 开始枚举后面的数字
{ // for 循环开始
path.push_back(nums[i]); // 做选择：把 nums[i] 加入当前子集
dfs(nums, i + 1, path, result); // 递归：下一层只能从 i + 1 开始继续选
path.pop_back(); // 撤销选择：把刚才加入的 nums[i] 移除，尝试其他分支
} // for 循环结束
} // dfs 函数结束
}; // Solution 类结束为什么 result.push_back(path) 放在递归一开始？
因为子集和全排列不一样。
全排列必须等到：
c
path.size() == nums.size()才是一个完整答案。
但子集里：
[]
[1]
[1, 2]
[1, 2, 3]每一个中间状态都是答案。
所以进入每一层递归时，当前 path 都应该被收集。
为什么不需要 used 数组？
全排列需要 used，因为它每一层都可以从头扫描所有数字，要靠 used 防止重复使用。
子集不需要 used，因为我们用 startIndex 控制方向：
只能往后选，不能回头选比如选了 2 之后，下一层只能从 3 开始，不会再选 1 或 2。
复杂度
时间复杂度：
O(n * 2^n)因为一共有 2^n 个子集，每个子集复制进答案时最多需要 O(n)。
空间复杂度：
c
O(n)这是递归深度和 path 的空间。 如果把最终答案也算进去，就是：
c
O(n * 2^n)面试高分回答
子集是典型回溯问题。每个元素本质上都有选和不选两种状态，所以一共有 2^n 个结果。实现时用 path 保存当前子集，用 startIndex 控制下一层从哪里开始选，防止重复组合。每进入一层递归，都先把当前 path 加入结果集，因为子集问题中每个中间状态都是合法答案。然后从 startIndex 开始枚举元素，选择一个元素加入 path，递归处理后面的元素，递归返回后再 pop_back 撤销选择，继续尝试其他分支。
组合总和
组合总和是什么？ 组合总和通常指 LeetCode 39：给你一组候选数字 candidates 和一个目标值 target，找出所有数字和等于 target 的组合。
重点是：
同一个数字可以被重复使用。比如：
candidates = [2, 3, 6, 7]
target = 7答案是：
[2, 2, 3]
[7]因为：
2 + 2 + 3 = 7
7 = 7它和子集有什么区别？
子集是：
每个数字通常只选一次。组合总和是：
同一个数字可以选很多次。比如数字 2 可以这样用：
[2, 2, 3]所以这题的关键不是“选一次就跳过”，而是：
选了 candidates[i] 之后，下一层还可以继续从 i 开始选。也就是：
c
dfs(i, remain - candidates[i])不是：
c
dfs(i + 1, remain - candidates[i])核心思路：回溯
我们用三个核心变量：
path：当前已经选择的组合
remain：距离 target 还差多少
startIndex：当前这一层从哪个位置开始选举个例子：
c
target = 7
path = [2, 2]
remain = 3这表示：
现在已经选了 2 和 2
还差 3 就能凑到 target如果下一步选 3：
c
path = [2, 2, 3]
remain = 0说明找到一个答案。
C++ 代码
c
#include <vector> // 引入 vector 容器，用来保存候选数组、当前组合和所有答案
#include <algorithm> // 引入 algorithm，用来对 candidates 排序，方便剪枝
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面的函数可以被外部调用
vector<vector<int>> combinationSum(vector<int>& candidates, int target) // 定义组合总和函数，输入候选数组和目标值
{ // combinationSum 函数开始
vector<vector<int>> result; // 创建结果数组，用来保存所有满足条件的组合
vector<int> path; // 创建路径数组，用来保存当前正在尝试的组合
sort(candidates.begin(), candidates.end()); // 先排序，方便后面发现超过 remain 时直接剪枝
dfs(candidates, target, 0, path, result); // 从下标 0 开始执行回溯，初始剩余目标就是 target
return result; // 返回所有满足条件的组合
} // combinationSum 函数结束
private: // private 表示下面的函数只在类内部使用
void dfs(vector<int>& candidates, int remain, int startIndex, vector<int>& path, vector<vector<int>>& result) // 定义 DFS 回溯函数
{ // dfs 函数开始
if (remain == 0) // 如果剩余目标为 0，说明当前 path 的数字和刚好等于 target
{ // if 语句开始
result.push_back(path); // 把当前组合加入答案
return; // 当前分支已经找到答案，返回上一层
} // if 语句结束
for (int i = startIndex; i < candidates.size(); i++) // 从 startIndex 开始枚举候选数字，避免组合顺序重复
{ // for 循环开始
if (candidates[i] > remain) // 如果当前数字已经大于剩余目标
{ // if 语句开始
break; // 因为数组已经排序，后面的数字更大，所以直接停止循环
} // if 语句结束
path.push_back(candidates[i]); // 做选择：把当前数字加入组合
dfs(candidates, remain - candidates[i], i, path, result); // 递归：因为数字可以重复使用，所以下一层仍然从 i 开始
path.pop_back(); // 撤销选择：把刚才加入的数字移除，尝试下一个候选数字
} // for 循环结束
} // dfs 函数结束
}; // Solution 类结束为什么递归传 i，不是 i + 1？
因为题目允许：
同一个数字重复使用。比如：
[2, 2, 3]第一个 2 选完之后，下一层还要能继续选 2。
所以写：
c
dfs(candidates, remain - candidates[i], i, path, result)如果写成 i + 1，那每个数字最多只能用一次，就变成另一类题了。
为什么需要 startIndex？
因为组合不关心顺序。
下面两个组合本质一样：
[2, 2, 3]
[2, 3, 2]我们只想保留一种。
所以用 startIndex 控制：
后面只能选当前位置及其后面的数字
不要回头选前面的数字这样就不会产生重复顺序。
为什么可以剪枝？
如果排好序之后：
c
candidates = [2, 3, 6, 7]
remain = 4当你枚举到 6 时：
6 > 4说明 6 不能选。
因为后面的 7 更大，也不可能选。
所以可以直接：
break这就是剪枝，可以减少很多无意义递归。
复杂度
时间复杂度不太好精确写成一个简单公式，因为数字可以重复选择，和 target、候选数字大小都有关系。
面试里可以这样说：
回溯会枚举所有可能组合，最坏情况下搜索树可能很大。更常见的表达是：
时间复杂度和答案数量、target 大小、候选数字分布有关。空间复杂度：
O(target / min(candidates))这是递归最深可能选择多少个数字。 比如最小数字是 2，target = 8，最深可能是：
[2, 2, 2, 2]如果算最终答案空间，就要再加上所有结果占用的空间。
面试高分回答
NOTE
组合总和是典型回溯问题。用 path 保存当前组合，用 remain 表示还差多少凑到目标值，用 startIndex 控制搜索起点，避免出现 [2,3,2] 这种顺序不同但本质相同的重复组合。每次从 startIndex 开始枚举候选数字，选择一个数字加入 path，然后递归搜索剩余目标。由于题目允许同一个数字重复使用，所以递归时传入的是 i，不是 i + 1。当 remain == 0 时说明找到一个合法组合，加入结果。数组排序后，如果当前数字已经大于 remain，后续数字也一定更大，可以直接 break 剪枝。
爬楼梯
爬楼梯是什么题？ 爬楼梯是经典动态规划题。题目一般是：
你要爬到第 n 阶楼梯。
每次可以爬 1 阶或者 2 阶。
问一共有多少种不同爬法？比如：
n = 3有 3 种爬法：
1 + 1 + 1
1 + 2
2 + 1所以答案是：
3核心思想
这题不要真的去模拟人爬楼梯。
面试里要从“最后一步”分析：
如果最后一步爬 1 阶，那么之前一定站在第 n - 1 阶。
如果最后一步爬 2 阶，那么之前一定站在第 n - 2 阶。所以：
到第 n 阶的方法数 = 到第 n - 1 阶的方法数 + 到第 n - 2 阶的方法数也就是：
c
dp[n] = dp[n - 1] + dp[n - 2]这就是斐波那契数列的思想。
举个例子
假设要到第 5 阶。
最后一步只有两种可能：
从第 4 阶走 1 阶到第 5 阶
从第 3 阶走 2 阶到第 5 阶所以：
c
dp[5] = dp[4] + dp[3]如果：
c
dp[4] = 5
dp[3] = 3那么：
c
dp[5] = 5 + 3 = 8为什么不是排列组合硬算？
因为 n 变大之后，所有路径会非常多。
比如：
c
n = 5所有爬法是：
c
1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 2 + 1
1 + 2 + 1 + 1
2 + 1 + 1 + 1
1 + 2 + 2
2 + 1 + 2
2 + 2 + 1一共 8 种。
如果靠枚举，会越来越慢。 动态规划的优势是：
小问题算过之后直接复用。动态规划数组写法
c
#include <vector> // 引入 vector 容器，用来保存动态规划数组
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
int climbStairs(int n) // 定义爬楼梯函数，输入楼梯阶数 n，返回不同爬法数量
{ // climbStairs 函数开始
if (n <= 2) // 如果 n 是 1 或 2，可以直接返回答案
{ // if 语句开始
return n; // n 为 1 时答案是 1，n 为 2 时答案是 2
} // if 语句结束
vector<int> dp(n + 1, 0); // 创建 dp 数组，dp[i] 表示爬到第 i 阶的方法数
dp[1] = 1; // 爬到第 1 阶只有 1 种方法：一次爬 1 阶
dp[2] = 2; // 爬到第 2 阶有 2 种方法：1+1 或 2
for (int i = 3; i <= n; i++) // 从第 3 阶开始，依次计算到第 n 阶
{ // for 循环开始
dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移：最后一步来自 i-1 或 i-2
} // for 循环结束
return dp[n]; // 返回爬到第 n 阶的方法数
} // climbStairs 函数结束
}; // Solution 类结束空间优化写法
上面用了一个 dp 数组，其实没必要保存所有结果。
因为计算：
c
dp[i]只需要：
c
dp[i - 1]
dp[i - 2]所以可以只用两个变量。
c
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面函数可以被外部调用
int climbStairs(int n) // 定义爬楼梯函数，输入楼梯阶数 n，返回不同爬法数量
{ // climbStairs 函数开始
if (n <= 2) // 如果 n 是 1 或 2，可以直接返回答案
{ // if 语句开始
return n; // n 为 1 时答案是 1，n 为 2 时答案是 2
} // if 语句结束
int prev2 = 1; // prev2 表示 dp[i - 2]，初始对应 dp[1]
int prev1 = 2; // prev1 表示 dp[i - 1]，初始对应 dp[2]
int current = 0; // current 表示当前要计算的 dp[i]
for (int i = 3; i <= n; i++) // 从第 3 阶开始计算
{ // for 循环开始
current = prev1 + prev2; // 当前方法数等于前一阶方法数加前两阶方法数
prev2 = prev1; // 更新 prev2，让它变成下一轮的 dp[i - 2]
prev1 = current; // 更新 prev1，让它变成下一轮的 dp[i - 1]
} // for 循环结束
return prev1; // 循环结束后 prev1 就是 dp[n]
} // climbStairs 函数结束
}; // Solution 类结束复杂度
动态规划数组写法：
时间复杂度：O(n)
空间复杂度：O(n)空间优化写法：
时间复杂度：O(n)
空间复杂度：O(1)面试高分回答
爬楼梯是典型动态规划问题。定义 dp[i] 表示爬到第 i 阶的方法数。到第 i 阶的最后一步只有两种情况：从第 i - 1 阶爬 1 阶上来，或者从第 i - 2 阶爬 2 阶上来，所以状态转移方程是 dp[i] = dp[i - 1] + dp[i - 2]。初始条件是 dp[1] = 1，dp[2] = 2。因为每次只依赖前两个状态，所以可以用两个变量做空间优化，把空间复杂度从 O(n) 降到 O(1)。
打家劫舍
打家劫舍是什么题？ 打家劫舍是经典动态规划题。题目大概是：
有一排房子，每间房都有一定金额。
小偷不能偷相邻的两间房。
问最多能偷多少钱？比如：
nums = [2, 7, 9, 3, 1]最佳偷法是：
偷第 0 间、第 2 间、第 4 间金额是：
2 + 9 + 1 = 12核心思想
每到一间房，只有两个选择：
偷当前房
不偷当前房如果偷当前房：
前一间房就不能偷
所以只能加上 dp[i - 2]如果不偷当前房：
答案就是前一间房的最优结果 dp[i - 1]所以状态转移方程是：
c
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])dp[i] 是什么意思？
dp[i] 表示：从第 0 间房到第 i 间房，在不偷相邻房子的前提下，最多能偷多少钱。注意，这句话很重要：
dp[i] 不是一定偷第 i 间房。它表示的是：
考虑到第 i 间房为止的最大收益。举个例子
c
nums = [2, 7, 9, 3, 1]初始化：
c
dp[0] = 2
dp[1] = max(2, 7) = 7算第 2 间房：
c
偷第 2 间：dp[0] + nums[2] = 2 + 9 = 11
不偷第 2 间：dp[1] = 7
dp[2] = max(11, 7) = 11算第 3 间房：
c
偷第 3 间：dp[1] + nums[3] = 7 + 3 = 10
不偷第 3 间：dp[2] = 11
dp[3] = max(10, 11) = 11算第 4 间房：
c
偷第 4 间：dp[2] + nums[4] = 11 + 1 = 12
不偷第 4 间：dp[3] = 11
dp[4] = max(12, 11) = 12最终答案：
12C++ 代码
c
#include <vector> // 引入 vector 容器，用来保存房子金额和动态规划数组
#include <algorithm> // 引入 algorithm，用来使用 max 函数
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面的函数可以被外部调用
int rob(vector<int>& nums) // 定义打家劫舍函数，输入每间房的钱，返回最多能偷的钱
{ // rob 函数开始
int n = nums.size(); // 获取房子的数量
if (n == 0) // 如果没有房子
{ // if 语句开始
return 0; // 没有房子可以偷，所以返回 0
} // if 语句结束
if (n == 1) // 如果只有一间房
{ // if 语句开始
return nums[0]; // 只能偷这一间房，所以返回 nums[0]
} // if 语句结束
vector<int> dp(n, 0); // 创建 dp 数组，dp[i] 表示考虑到第 i 间房时最多能偷多少钱
dp[0] = nums[0]; // 只有第 0 间房时，最多只能偷 nums[0]
dp[1] = max(nums[0], nums[1]); // 只有前两间房时，因为不能相邻偷，所以取金额更大的那一间
for (int i = 2; i < n; i++) // 从第 2 间房开始计算
{ // for 循环开始
int robCurrent = dp[i - 2] + nums[i]; // 偷当前房：当前金额加上 i-2 位置的最优结果
int skipCurrent = dp[i - 1]; // 不偷当前房：结果就是 i-1 位置的最优结果
dp[i] = max(skipCurrent, robCurrent); // 当前最优结果等于偷和不偷两种选择里的最大值
} // for 循环结束
return dp[n - 1]; // 返回考虑到最后一间房时的最大金额
} // rob 函数结束
}; // Solution 类结束为什么不能贪心？
你可能会想：
每次偷金额最大的房子不就行了吗？不行。
比如：
nums = [2, 7, 9, 3, 1]如果先偷最大的 9，还能偷 2 和 1，得到 12，这次刚好对。 但换一个例子：
nums = [2, 1, 1, 2]如果只看局部，可能会错。正确答案是：
2 + 2 = 4这类题要考虑“当前选择对后面选择的影响”，所以更适合动态规划。
空间优化
因为：
c
dp[i] 只依赖 dp[i - 1] 和 dp[i - 2]所以不一定需要完整数组，可以只用两个变量。
c
#include <vector> // 引入 vector 容器，用来保存房子金额
#include <algorithm> // 引入 algorithm，用来使用 max 函数
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面的函数可以被外部调用
int rob(vector<int>& nums) // 定义打家劫舍函数，输入每间房的钱，返回最多能偷的钱
{ // rob 函数开始
int prev2 = 0; // prev2 表示 dp[i - 2]，也就是隔一间之前的最优结果
int prev1 = 0; // prev1 表示 dp[i - 1]，也就是前一间之前的最优结果
for (int money : nums) // 依次遍历每一间房的钱
{ // for 循环开始
int robCurrent = prev2 + money; // 偷当前房：当前金额加上 dp[i - 2]
int skipCurrent = prev1; // 不偷当前房：保持 dp[i - 1]
int current = max(skipCurrent, robCurrent); // 当前最优结果等于偷和不偷两种选择中的最大值
prev2 = prev1; // 更新 prev2，让它变成下一轮的 dp[i - 2]
prev1 = current; // 更新 prev1，让它变成下一轮的 dp[i - 1]
} // for 循环结束
return prev1; // 遍历结束后，prev1 就是最终最大金额
} // rob 函数结束
}; // Solution 类结束复杂度
动态规划数组写法：
时间复杂度：O(n)
空间复杂度：O(n)空间优化写法：
时间复杂度：O(n)
空间复杂度：O(1)面试高分回答
IMPORTANT
打家劫舍是典型动态规划问题。定义 dp[i] 表示考虑到第 i 间房为止，在不能偷相邻房子的限制下，最多能偷多少钱。对于第 i 间房，只有两种选择：不偷它，那么结果是 dp[i - 1]；偷它，那么第 i - 1 间不能偷，结果是 dp[i - 2] + nums[i]。因此状态转移方程是 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])。由于每个状态只依赖前两个状态，所以可以把空间从 O(n) 优化到 O(1)。
最长递增子序列
最长递增子序列是什么？ 最长递增子序列，英文叫 Longest Increasing Subsequence，简称 LIS。
它的意思是：
从数组中挑出一些数字，保持原来的相对顺序不变，让这些数字严格递增，并且长度尽量长。比如：
nums = [10, 9, 2, 5, 3, 7, 101, 18]一个最长递增子序列可以是：
[2, 3, 7, 101]长度是：
4注意，也可以是：
[2, 3, 7, 18]所以答案通常问的是“长度”，不一定要求输出具体是哪一个序列。
子序列和子数组的区别
这个点面试特别容易考。
子数组要求连续：
[2, 5, 3]它在原数组里是连续的一段。
子序列不要求连续：
[2, 3, 7, 101]它可以跳过中间的数字，但原来的相对顺序不能乱。
也就是说：
[2, 3, 7, 101] 可以
[2, 7, 3, 101] 不可以因为 7 在原数组里本来就在 3 后面，顺序不能倒过来。
动态规划怎么想？
我们定义：
dp[i] 表示：以 nums[i] 结尾的最长递增子序列长度。这句话非常关键。
不是说：
前 i 个元素里的最长长度而是：
必须以 nums[i] 这个数字作为结尾为什么要这样定义？
因为如果要把 nums[i] 接到前面的某个序列后面，必须满足：
nums[j] < nums[i]只有前面的数字比当前数字小，才能组成递增序列。
所以状态转移是：
c
如果 nums[j] < nums[i]
dp[i] = max(dp[i], dp[j] + 1)举个例子
c
nums = [10, 9, 2, 5, 3, 7, 101, 18]一开始每个数字自己都能组成长度为 1 的递增子序列：
dp = [1, 1, 1, 1, 1, 1, 1, 1]看到 5 的时候：
前面有 2 比 5 小
所以 [2, 5] 长度是 2
dp[3] = 2看到 7 的时候：
前面有 2、5、3 都比 7 小
可以组成 [2, 5, 7]
也可以组成 [2, 3, 7]
长度是 3
dp[5] = 3看到 101 的时候：
c
可以接在 [2, 3, 7] 后面
得到 [2, 3, 7, 101]
长度是 4
dp[6] = 4最终：
c
dp = [1, 1, 1, 2, 2, 3, 4, 4]答案是：
c
max(dp) = 4O(n²) 动态规划代码
c
#include <vector> // 引入 vector 容器，用来保存输入数组和 dp 数组
#include <algorithm> // 引入 algorithm，用来使用 max 函数
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面的函数可以被外部调用
int lengthOfLIS(vector<int>& nums) // 定义函数，输入数组 nums，返回最长递增子序列长度
{ // lengthOfLIS 函数开始
int n = nums.size(); // 获取数组长度
if (n == 0) // 如果数组为空
{ // if 语句开始
return 0; // 空数组没有递增子序列，所以返回 0
} // if 语句结束
vector<int> dp(n, 1); // 创建 dp 数组，每个位置初始为 1，因为每个数字自己就是长度为 1 的序列
int answer = 1; // 创建答案变量，至少有一个数字时，最长长度至少是 1
for (int i = 0; i < n; i++) // 枚举当前结尾位置 i
{ // 外层 for 循环开始
for (int j = 0; j < i; j++) // 枚举 i 前面的每一个位置 j
{ // 内层 for 循环开始
if (nums[j] < nums[i]) // 如果 nums[j] 小于 nums[i]，说明 nums[i] 可以接在 nums[j] 后面
{ // if 语句开始
dp[i] = max(dp[i], dp[j] + 1); // 更新以 nums[i] 结尾的最长递增子序列长度
} // if 语句结束
} // 内层 for 循环结束
answer = max(answer, dp[i]); // 用当前 dp[i] 更新全局最长长度
} // 外层 for 循环结束
return answer; // 返回最长递增子序列长度
} // lengthOfLIS 函数结束
}; // Solution 类结束为什么 dp[i] 初始是 1？
因为每个数字单独拿出来，都是一个递增子序列。
比如：
nums[i] = 7哪怕前面没有任何数字能接上它，它自己也能形成：
[7]长度就是：
1所以：
dp[i] 初始值是 1为什么判断条件是 < 不是 <=？
因为题目是“递增子序列”，通常指严格递增。
也就是说：
1, 2, 3 可以
1, 2, 2 不可以所以判断条件是：
c
nums[j] < nums[i]如果题目问的是“非递减子序列”，才可能用：
c
nums[j] <= nums[i]O(n log n) 优化思路
面试如果只会 O(n²)，已经能过很多基础场景。 如果想更打动面试官，可以再说优化版本。
我们维护一个数组：
c
tails它的含义是：
tails[k] 表示长度为 k + 1 的递增子序列中，最小可能的结尾值。为什么要让结尾尽量小？
因为结尾越小，后面越容易接上更大的数字。
比如：
c
长度为 2 的递增子序列
[2, 5]
[2, 3]显然 [2, 3] 更好，因为结尾 3 更小，后面更容易接 7、18、101。
O(n log n) 代码
c
#include <vector> // 引入 vector 容器，用来保存输入数组和 tails 数组
#include <algorithm> // 引入 algorithm，用来使用 lower_bound 函数
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面的函数可以被外部调用
int lengthOfLIS(vector<int>& nums) // 定义函数，输入数组 nums，返回最长递增子序列长度
{ // lengthOfLIS 函数开始
vector<int> tails; // 创建 tails 数组，tails[i] 表示长度为 i+1 的递增子序列的最小结尾值
for (int x : nums) // 遍历 nums 中的每一个数字 x
{ // for 循环开始
auto it = lower_bound(tails.begin(), tails.end(), x); // 找到 tails 中第一个大于等于 x 的位置
if (it == tails.end()) // 如果没有找到，说明 x 比所有结尾值都大
{ // if 语句开始
tails.push_back(x); // 把 x 放到 tails 末尾，表示最长长度可以增加 1
} // if 语句结束
else // 如果找到了第一个大于等于 x 的位置
{ // else 语句开始
*it = x; // 用 x 替换这个位置，让相同长度的序列结尾尽量小
} // else 语句结束
} // for 循环结束
return tails.size(); // tails 的长度就是最长递增子序列的长度
} // lengthOfLIS 函数结束
}; // Solution 类结束注意 tails 不一定是真实的 LIS
这一点也很重要。
talls 或 tails 数组主要是为了求长度，它里面的数字不一定能直接组成原数组中的真实最长递增子序列。
它保证的是：
每种长度下，结尾值尽量小。所以它可以高效得到长度。
如果面试官问：
能不能输出具体序列？那就需要额外记录前驱下标，不是这个基础版本的重点。
复杂度
动态规划版本：
时间复杂度：O(n²)
空间复杂度：O(n)二分优化版本：
时间复杂度：O(n log n)
空间复杂度：O(n)面试高分回答
NOTE
最长递增子序列是典型动态规划问题。首先要明确子序列不要求连续，但必须保持原数组中的相对顺序。可以定义 dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。对于每个位置 i，向前枚举所有 j < i，如果 nums[j] < nums[i]，说明 nums[i] 可以接在以 nums[j] 结尾的递增序列后面，因此状态转移为 dp[i] = max(dp[i], dp[j] + 1)。所有 dp[i] 的最大值就是答案。基础写法时间复杂度是 O(n²)，如果要优化，可以维护 tails 数组并用二分查找，把时间复杂度降到 O(n log n)。
最长公共子序列
最长公共子序列是什么？ 最长公共子序列，英文叫 Longest Common Subsequence，简称 LCS。
它的意思是：
在两个字符串中，找一个最长的、两边都能按顺序找到的字符序列。比如：
text1 = "abcde"
text2 = "ace"它们的最长公共子序列是：
"ace"长度是：
3子序列是什么意思？
子序列可以不连续，但是顺序不能乱。
比如：
"abcde"里面可以取出：
"a c e"也就是：
c
"ace"虽然中间跳过了 b 和 d，但是 a、c、e 的顺序没有变。
所以：
c
"ace" 是 "abcde" 的子序列
"aec" 不是 "abcde" 的子序列因为 e 在原字符串里本来在 c 后面，不能倒过来。
它和最长公共子串的区别
这个一定要分清。
最长公共子序列：
可以不连续最长公共子串：
必须连续比如：
c
text1 = "abcde"
text2 = "ace"最长公共子序列是：
"ace"但最长公共子串只能是：
"a" 或 "c" 或 "e"因为 "ace" 在 "abcde" 里不是连续的一段。
动态规划怎么定义？
我们定义：
dp[i][j] 表示 text1 的前 i 个字符 和 text2 的前 j 个字符 的最长公共子序列长度。注意：
前 i 个字符不是下标 i比如：
c
text1 = "abcde"i = 3 表示：
c
"abc"不是只看字符 text1[3]。
最终答案是：
c
dp[text1.size()][text2.size()]状态怎么转移？
假设现在比较：
c
text1[i - 1]
text2[j - 1]为什么是 i - 1 和 j - 1？
因为 dp[i][j] 表示前 i 个字符，而字符串下标从 0 开始。
如果两个字符相等：
c
text1[i - 1] == text2[j - 1]说明这个字符可以加入公共子序列：
c
dp[i][j] = dp[i - 1][j - 1] + 1如果两个字符不相等：
c
text1[i - 1] != text2[j - 1]说明这两个字符不能同时作为公共结尾，只能尝试丢掉其中一个：
c
丢掉 text1 当前字符：dp[i - 1][j]
丢掉 text2 当前字符：dp[i][j - 1]取更大的：
c
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])C++ 代码
c
#include <string> // 引入 string，用来表示两个输入字符串
#include <vector> // 引入 vector，用来创建二维 dp 数组
#include <algorithm> // 引入 algorithm，用来使用 max 函数
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面的函数可以被外部调用
int longestCommonSubsequence(string text1, string text2) // 定义最长公共子序列函数，输入两个字符串，返回 LCS 长度
{ // longestCommonSubsequence 函数开始
int m = text1.size(); // 获取 text1 的长度
int n = text2.size(); // 获取 text2 的长度
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 创建二维 dp 数组，多开一行一列用来表示空字符串
for (int i = 1; i <= m; i++) // 从 text1 的第 1 个字符开始枚举
{ // 外层 for 循环开始
for (int j = 1; j <= n; j++) // 从 text2 的第 1 个字符开始枚举
{ // 内层 for 循环开始
if (text1[i - 1] == text2[j - 1]) // 如果当前两个字符相等
{ // if 语句开始
dp[i][j] = dp[i - 1][j - 1] + 1; // 当前字符可以加入公共子序列，所以从左上角状态加 1
} // if 语句结束
else // 如果当前两个字符不相等
{ // else 语句开始
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 当前字符不能同时选，取上方和左方的最大值
} // else 语句结束
} // 内层 for 循环结束
} // 外层 for 循环结束
return dp[m][n]; // 右下角就是两个完整字符串的最长公共子序列长度
} // longestCommonSubsequence 函数结束
}; // Solution 类结束为什么 dp 要多开一行一列？
因为我们需要处理空字符串情况。
比如：
text1 前 0 个字符
text2 前 j 个字符这时公共子序列长度一定是：
0所以：
c
dp[0][j] = 0
dp[i][0] = 0多开一行一列之后，代码不用单独处理边界，直接从 1 开始循环就行。
以 "abcde" 和 "ace" 举例
c
text1 = "abcde"
text2 = "ace"匹配过程大概是：
a 和 a 匹配，长度变成 1
c 和 c 匹配，长度变成 2
e 和 e 匹配，长度变成 3所以最后：
c
dp[5][3] = 3答案就是：
3空间优化写法
二维数组更好理解。 但如果面试官问优化空间，可以用一维数组。
c
#include <string> // 引入 string，用来表示两个输入字符串
#include <vector> // 引入 vector，用来创建一维 dp 数组
#include <algorithm> // 引入 algorithm，用来使用 max 函数
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义 LeetCode 常见的 Solution 类
{ // Solution 类开始
public: // public 表示下面的函数可以被外部调用
int longestCommonSubsequence(string text1, string text2) // 定义最长公共子序列函数，输入两个字符串，返回 LCS 长度
{ // longestCommonSubsequence 函数开始
int m = text1.size(); // 获取 text1 的长度
int n = text2.size(); // 获取 text2 的长度
vector<int> dp(n + 1, 0); // 创建一维 dp 数组，dp[j] 表示当前行算到 j 时的 LCS 长度
for (int i = 1; i <= m; i++) // 枚举 text1 的前 i 个字符
{ // 外层 for 循环开始
int leftTop = 0; // leftTop 用来保存二维 dp 中的 dp[i - 1][j - 1]
for (int j = 1; j <= n; j++) // 枚举 text2 的前 j 个字符
{ // 内层 for 循环开始
int oldTop = dp[j]; // oldTop 保存更新前的 dp[j]，也就是二维 dp 中的 dp[i - 1][j]
if (text1[i - 1] == text2[j - 1]) // 如果当前两个字符相等
{ // if 语句开始
dp[j] = leftTop + 1; // 当前字符可以加入公共子序列，所以使用左上角值加 1
} // if 语句结束
else // 如果当前两个字符不相等
{ // else 语句开始
dp[j] = max(dp[j], dp[j - 1]); // 取上方 dp[j] 和左方 dp[j - 1] 的最大值
} // else 语句结束
leftTop = oldTop; // 更新 leftTop，供下一列使用
} // 内层 for 循环结束
} // 外层 for 循环结束
return dp[n]; // dp[n] 就是最终的最长公共子序列长度
} // longestCommonSubsequence 函数结束
}; // Solution 类结束复杂度
二维 DP 写法：
时间复杂度：O(m * n)
空间复杂度：O(m * n)一维优化写法：
时间复杂度：O(m * n)
空间复杂度：O(n)其中：
c
m 是 text1 的长度
n 是 text2 的长度面试高分回答
NOTE
最长公共子序列是经典二维动态规划问题。子序列可以不连续，但字符相对顺序不能改变。定义 dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列长度。如果 text1[i - 1] == text2[j - 1]，说明当前字符可以作为公共子序列的一部分，状态转移为 dp[i][j] = dp[i - 1][j - 1] + 1。如果两个字符不相等，就只能舍弃其中一个当前字符，状态转移为 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。初始化时第 0 行和第 0 列表示空字符串，值都是 0。最终答案是 dp[m][n]。
背包问题
背包问题是什么？ 背包问题是一类经典动态规划题。最常见的是 0/1 背包：
有 n 个物品。
每个物品有重量 weight 和价值 value。
背包容量有限。
每个物品只能选一次。
问：在不超过背包容量的情况下，最多能装多少价值？比如：
weights = [1, 3, 4]
values = [15, 20, 30]
capacity = 4最优选择是：
选重量 1、价值 15 的物品
选重量 3、价值 20 的物品总重量：
1 + 3 = 4总价值：
15 + 20 = 35为什么叫 0/1 背包？
因为每个物品只有两种状态：
0：不选
1：选也就是说：
每个物品最多只能拿一次。这就是 0/1 背包。
如果题目说：
每个物品可以无限次选择那就是：
完全背包动态规划怎么定义？
先讲最好理解的二维 DP。
定义：
dp[i][j] 表示：只看前 i 个物品，背包容量为 j 时，能获得的最大价值。比如：
c
dp[2][4]表示：
只看前 2 个物品，背包容量是 4，最多能拿多少价值。状态怎么转移？
对于第 i 个物品，有两种选择。
第一种：不选当前物品。
c
dp[i][j] = dp[i - 1][j]意思是：
当前物品不拿，那答案就等于只看前 i - 1 个物品时的答案。第二种：选当前物品。
前提是：
当前容量 j 能装得下这个物品也就是：
j >= weight[i - 1]如果选当前物品：
dp[i][j] = dp[i - 1][j - weight[i - 1]] + value[i - 1]意思是：
先给当前物品腾出重量
再加上当前物品的价值所以最终：
dp[i][j] = max(不选当前物品, 选当前物品)也就是：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1])二维 DP 代码
c
#include <vector> // 引入 vector 容器，用来保存重量数组、价值数组和 dp 数组
#include <algorithm> // 引入 algorithm，用来使用 max 函数
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义一个 Solution 类，方便面试或 LeetCode 风格调用
{ // Solution 类开始
public: // public 表示下面的函数可以被外部调用
int knapsack01(vector<int>& weights, vector<int>& values, int capacity) // 定义 0/1 背包函数，输入重量、价值和背包容量
{ // knapsack01 函数开始
int n = weights.size(); // 获取物品数量
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0)); // 创建二维 dp 数组，多开一行表示没有物品的情况
for (int i = 1; i <= n; i++) // 枚举前 i 个物品
{ // 外层 for 循环开始
for (int j = 0; j <= capacity; j++) // 枚举当前背包容量 j
{ // 内层 for 循环开始
dp[i][j] = dp[i - 1][j]; // 默认不选当前物品，继承上一行的最优结果
if (j >= weights[i - 1]) // 如果当前容量 j 能装下第 i 个物品
{ // if 语句开始
int take = dp[i - 1][j - weights[i - 1]] + values[i - 1]; // 计算选择当前物品时能获得的价值
dp[i][j] = max(dp[i][j], take); // 在选和不选之间取最大值
} // if 语句结束
} // 内层 for 循环结束
} // 外层 for 循环结束
return dp[n][capacity]; // 返回看完所有物品且容量为 capacity 时的最大价值
} // knapsack01 函数结束
}; // Solution 类结束为什么数组下标是 i - 1？
因为：
dp 的 i 表示前 i 个物品但数组下标从 0 开始。
所以第 i 个物品对应数组下标：
i - 1比如：
i = 1表示第 1 个物品，它在数组中的下标是：
0一维 DP 优化
二维 DP 好理解，但空间可以优化。
因为：
c
dp[i][j] 只依赖上一行 dp[i - 1][...]所以可以用一维数组：
c
dp[j] 表示容量为 j 时的最大价值0/1 背包一维代码
c
#include <vector> // 引入 vector 容器，用来保存重量数组、价值数组和 dp 数组
#include <algorithm> // 引入 algorithm，用来使用 max 函数
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义一个 Solution 类，方便面试或 LeetCode 风格调用
{ // Solution 类开始
public: // public 表示下面的函数可以被外部调用
int knapsack01(vector<int>& weights, vector<int>& values, int capacity) // 定义 0/1 背包函数，输入重量、价值和背包容量
{ // knapsack01 函数开始
int n = weights.size(); // 获取物品数量
vector<int> dp(capacity + 1, 0); // 创建一维 dp 数组，dp[j] 表示容量为 j 时的最大价值
for (int i = 0; i < n; i++) // 枚举每一个物品
{ // 外层 for 循环开始
for (int j = capacity; j >= weights[i]; j--) // 倒序枚举容量，避免同一个物品被重复使用
{ // 内层 for 循环开始
int take = dp[j - weights[i]] + values[i]; // 计算选择当前物品时能获得的价值
dp[j] = max(dp[j], take); // 在选当前物品和不选当前物品之间取最大值
} // 内层 for 循环结束
} // 外层 for 循环结束
return dp[capacity]; // 返回容量为 capacity 时的最大价值
} // knapsack01 函数结束
}; // Solution 类结束为什么 0/1 背包一维 DP 要倒序？
这是背包问题最容易考的点。
0/1 背包中：
每个物品只能用一次。如果容量正序遍历：
for j 从小到大那么当前物品刚更新过的 dp[j]，可能马上又被后面的容量拿去用。 这样就等于：
同一个物品被用了多次这就错了。
所以 0/1 背包必须倒序：
c
for j 从 capacity 到 weight[i]这样可以保证：
c
dp[j - weight[i]]还是上一轮物品的状态，不会重复使用当前物品。
完全背包和 0/1 背包区别
完全背包是：
每个物品可以无限次使用。所以它的一维 DP 容量循环要正序。
0/1 背包：倒序
完全背包：正序对比一下：
c
0/1 背包：for j = capacity 到 weight[i]
完全背包：for j = weight[i] 到 capacity一句话记忆：
只能用一次，倒序防止重复用。
可以重复用，正序允许重复用。复杂度
二维 DP：
c
时间复杂度：O(n * capacity)
空间复杂度：O(n * capacity)一维优化：
c
时间复杂度：O(n * capacity)
空间复杂度：O(capacity)其中：
c
n 是物品数量
capacity 是背包容量面试高分回答
NOTE
背包问题是一类动态规划问题，最常见的是 0/1 背包。每个物品只有选和不选两种状态，目标是在容量限制内获得最大价值。可以定义 dp[i][j] 表示只看前 i 个物品、背包容量为 j 时的最大价值。对于第 i 个物品，如果不选它，状态来自 dp[i - 1][j]；如果选它，前提是容量足够，状态来自 dp[i - 1][j - weight[i - 1]] + value[i - 1]。因此状态转移方程是两者取最大值。空间上可以从二维数组优化成一维数组，0/1 背包一维写法必须倒序遍历容量，防止同一个物品在同一轮被重复使用；完全背包则因为允许重复使用物品，所以容量要正序遍历。
最短路径 Dijkstra
Dijkstra 是什么？ Dijkstra 是一种求最短路径的算法，常见问题是：
给你一张带权图。
给你一个起点 source。
求 source 到其他所有点的最短距离。比如地图导航里：
点：城市 / 路口
边：道路
权重：距离 / 时间 / 消耗Dijkstra 可以求：
从起点到每个点的最短距离
Dijkstra 适合什么图？
它适合：
边权非负的图也就是每条边的权重都要满足：
weight >= 0比如：
c
A -> B 距离 5
B -> C 距离 3
A -> C 距离 10这些都可以。
但如果有负权边：
c
A -> B 权重 -2就不适合用 Dijkstra。 负权边一般考虑：
c
Bellman-Ford
SPFA核心思想
Dijkstra 的想法可以理解成：
从起点开始。
每次找当前距离起点最近的点。
用这个点去更新它能到达的邻居。
重复这个过程。它维护一个数组：
c
dist[i]表示：
从起点到 i 号点的当前最短距离。一开始：
c
dist[source] = 0
其他 dist = INFINF 可以理解成：
暂时还不知道怎么到达这个点什么是松弛 relax？
松弛是 Dijkstra 里最重要的动作。
假设现在已经知道：
c
dist[u]并且有一条边：
c
u -> v，权重是 w那么我们可以尝试通过 u 去到 v：
c
newDistance = dist[u] + w如果：
c
newDistance < dist[v]说明找到了一条更短的路，于是更新：
c
dist[v] = newDistance这个过程就叫：
c
松弛 relax为什么要用优先队列？
因为 Dijkstra 每次都要找：
当前 dist 最小的点如果每次都遍历所有点找最小值，会比较慢。
所以常用：
优先队列 / 小根堆它可以快速拿到当前距离最小的点。
C++ 里 priority_queue 默认是大根堆，所以要写成小根堆。
C++ 代码
下面代码默认是有向图。 如果是无向图，就把反向边也加进去。
c
#include <vector> // 引入 vector 容器，用来保存图、边和距离数组
#include <queue> // 引入 queue 头文件，用来使用 priority_queue 优先队列
#include <utility> // 引入 utility 头文件，用来使用 pair
#include <functional> // 引入 functional 头文件，用来使用 greater 比较器
using namespace std; // 使用标准命名空间，避免每次写 std::
class Solution // 定义一个 Solution 类，方便面试或 LeetCode 风格调用
{ // Solution 类开始
public: // public 表示下面的函数可以被外部调用
vector<int> dijkstra(int n, vector<vector<int>>& edges, int source) // 定义 Dijkstra 函数，n 是点数，edges 是边，source 是起点
{ // dijkstra 函数开始
vector<vector<pair<int, int>>> graph(n); // 创建邻接表，graph[u] 里面保存 u 能到达的点和边权
for (vector<int>& edge : edges) // 遍历每一条边
{ // for 循环开始
int from = edge[0]; // 取出边的起点
int to = edge[1]; // 取出边的终点
int weight = edge[2]; // 取出边的权重
graph[from].push_back({to, weight}); // 加入一条有向边 from -> to，权重是 weight
} // for 循环结束
const int INF = 1000000000; // 定义一个很大的数，表示暂时不可达
vector<int> dist(n, INF); // 创建距离数组，初始都设置为 INF
dist[source] = 0; // 起点到自己的距离是 0
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 创建小根堆，里面保存 {当前距离, 当前点}
pq.push({0, source}); // 把起点加入优先队列
while (!pq.empty()) // 只要优先队列不为空，就继续处理
{ // while 循环开始
int currentDistance = pq.top().first; // 取出当前队列里最小的距离
int currentNode = pq.top().second; // 取出当前距离对应的点
pq.pop(); // 弹出队首元素
if (currentDistance > dist[currentNode]) // 如果这个距离已经不是最新的最短距离
{ // if 语句开始
continue; // 说明这是旧数据，直接跳过
} // if 语句结束
for (pair<int, int>& next : graph[currentNode]) // 遍历当前点能到达的所有邻居
{ // for 循环开始
int nextNode = next.first; // 取出邻居节点编号
int weight = next.second; // 取出当前边的权重
int newDistance = dist[currentNode] + weight; // 计算从起点经过 currentNode 到 nextNode 的新距离
if (newDistance < dist[nextNode]) // 如果新距离比原来的 dist[nextNode] 更短
{ // if 语句开始
dist[nextNode] = newDistance; // 更新 nextNode 的最短距离
pq.push({newDistance, nextNode}); // 把更新后的距离和节点加入优先队列
} // if 语句结束
} // for 循环结束
} // while 循环结束
return dist; // 返回起点到所有点的最短距离
} // dijkstra 函数结束
}; // Solution 类结束无向图怎么改？
如果题目是无向图，一条边：
c
u - v表示：
c
u 可以到 v
v 也可以到 u建图时要加两次：
c
graph[from].push_back({to, weight}); // 加入 from 到 to 的边
graph[to].push_back({from, weight}); // 加入 to 到 from 的边，因为无向图可以反过来走为什么要跳过旧数据？
代码里有这一段：
c
if (currentDistance > dist[currentNode]) // 如果这个距离已经不是最新的最短距离
{ // if 语句开始
continue; // 说明这是旧数据，直接跳过
} // if 语句结束原因是：
c
priority_queue 里可能存在同一个点的多个距离版本。比如一开始发现：
c
A 到 C = 10后来又发现：
c
A 到 B 到 C = 3那么队列里可能同时有：
c
(10, C)
(3, C)显然 (3, C) 才是新的最短距离。 当以后弹出 (10, C) 时，它已经过期了，直接跳过。
为什么 Dijkstra 不能处理负权边？
Dijkstra 有一个核心前提：
每次从优先队列里取出的最小距离节点，它的最短距离就已经确定了。这个结论依赖于：
所有边权都是非负数。如果有负权边，可能会出现：
某个点已经被认为最短了
但之后通过一条负权边，又找到更短的路这样 Dijkstra 的逻辑就被破坏了。
和 BFS 的区别
BFS 也能求最短路径，但 BFS 适合：
无权图
或者所有边权都一样的图因为 BFS 默认每走一条边，代价都相同。
Dijkstra 适合：
有权图，并且边权非负比如：
A -> B 权重 2
A -> C 权重 10
B -> C 权重 1这种情况下，不能只看经过几条边少，还要看权重总和。
复杂度
如果使用：
邻接表 + 优先队列时间复杂度通常是：
c
O((V + E) log V)其中：
V 是点的数量
E 是边的数量空间复杂度是：
c
O(V + E)因为要保存图、距离数组和优先队列。
面试高分回答
IMPORTANT
Dijkstra 是用来求非负权图单源最短路径的算法。它维护一个 dist 数组，dist[i] 表示从起点到节点 i 的当前最短距离，初始时起点为 0，其他点为无穷大。算法每次通过小根堆取出当前距离最小的节点，然后用这个节点去松弛它的所有邻居。如果 dist[u] + weight < dist[v]，说明经过 u 到达 v 更短，就更新 dist[v] 并把新状态加入优先队列。由于优先队列中可能存在旧距离，所以弹出时要判断当前距离是否已经过期。Dijkstra 的前提是边权非负，因为它依赖“当前弹出的最小距离节点已经确定最短”的性质。邻接表加优先队列实现时，时间复杂度通常是 O((V + E) log V)。
A* 寻路基础
A* 寻路是什么？ A* 是游戏开发里非常常见的寻路算法，通常用来解决：
从起点走到终点，怎样走总代价最小？比如：
角色从当前位置走到目标点
怪物追踪玩家
战棋角色在格子地图中移动
RTS 单位绕开障碍物A* 可以理解成：
Dijkstra + 方向感Dijkstra 会稳稳地向四周扩散。 A* 会更倾向于朝终点方向搜索，所以很多场景下更快。
A* 的三个核心值
A* 里每个节点都会计算三个值：
g：从起点走到当前点，已经花了多少代价
h：从当前点走到终点，预计还要花多少代价
f：当前点的总评分公式是：
f = g + h意思是：
已经走过的代价 + 预计还要走的代价 = 这条路看起来的总代价A* 每次优先选择：
f 最小的节点因为它看起来最有希望到达终点。
g、h、f 举例
假设角色从 S 走到某个格子 A：
S -> A 已经走了 5 格那么：
g = 5如果从 A 到终点 G，用估算方式觉得还要走 7 格：
h = 7那么：
c
f = g + h = 5 + 7 = 12A* 会比较不同格子的 f，优先扩展更小的。
Open List 和 Closed Set
A* 通常维护两个集合。
Open List：
待检查的节点可以理解成：
候选路线每次从里面取出 f 最小的节点。
Closed Set：
已经检查过的节点可以理解成：
不用重复处理的节点一个常见流程是：
1. 把起点加入 Open List
2. 每次取出 f 最小的点 current
3. 如果 current 是终点，寻路结束
4. 否则检查 current 的邻居
5. 如果邻居能走，并且找到更短路径，就更新它
6. 把 current 放入 Closed Set什么是启发函数 h？
h 是 A* 的“预估距离”。
在四方向网格里，也就是只能：
上、下、左、右移动常用：
曼哈顿距离公式：
c
h = abs(x1 - x2) + abs(y1 - y2)比如当前点是：
c
(1, 2)终点是：
c
(5, 4)那么：
c
h = abs(1 - 5) + abs(2 - 4)
h = 4 + 2
h = 6如果是八方向移动，也就是可以斜着走，常用：
对角线距离
欧几里得距离为什么 h 不能乱写？
如果 h 估得太大，A* 可能会错过真正的最短路径。
理想情况下，h 应该是：
乐观估计也就是：
估计值不要超过真实最短距离比如真实最短还要走 10，你的 h 最好不要估成 20。 否则算法可能被误导。
面试里可以说：
如果启发函数不高估真实代价，A* 可以保证找到最短路径。A* 和 Dijkstra 的区别
Dijkstra：
只看 g也就是：
谁离起点最近，就先处理谁A*：
看 g + h也就是：
既看已经走了多远，也看离终点大概还有多远如果：
c
h = 0那么：
A* 就退化成 Dijkstra所以可以记：
Dijkstra 是没有方向感的 A*
A* 是加了启发函数的 DijkstraC++ 网格版 A* 代码
下面是一个基础版，适合面试讲思路。 设定：
c
0 表示可走
1 表示障碍
只能上下左右移动
每走一格代价为 1
#include <vector> // 引入 vector 容器，用来保存地图、距离和父节点
#include <queue> // 引入 queue 头文件，用来使用 priority_queue 优先队列
#include <cmath> // 引入 cmath 头文件，用来使用 abs 函数
#include <algorithm> // 引入 algorithm 头文件，用来使用 reverse 函数
using namespace std; // 使用标准命名空间，避免每次写 std::
struct Node // 定义节点结构体，用来放进优先队列
{ // Node 结构体开始
int x; // 当前节点的行坐标
int y; // 当前节点的列坐标
int g; // 从起点走到当前节点的真实代价
int h; // 从当前节点到终点的预估代价
int f; // 当前节点的综合评分，f = g + h
}; // Node 结构体结束
struct Compare // 定义比较器，让 priority_queue 变成按 f 较小优先
{ // Compare 结构体开始
bool operator()(const Node& a, const Node& b) // 重载括号运算符，用来比较两个节点
{ // operator 函数开始
return a.f > b.f; // f 更小的节点优先级更高，所以这里写大于号形成小根堆效果
} // operator 函数结束
}; // Compare 结构体结束
class Solution // 定义一个 Solution 类，方便面试或项目中调用
{ // Solution 类开始
public: // public 表示下面的函数可以被外部调用
vector<pair<int, int>> astar(vector<vector<int>>& grid, pair<int, int> start, pair<int, int> goal) // 定义 A* 函数，输入地图、起点和终点
{ // astar 函数开始
int rows = grid.size(); // 获取地图行数
int cols = grid[0].size(); // 获取地图列数
const int INF = 1000000000; // 定义一个很大的数，表示暂时不可达
vector<vector<int>> gScore(rows, vector<int>(cols, INF)); // gScore[x][y] 表示从起点到这个格子的当前最小真实代价
vector<vector<bool>> closed(rows, vector<bool>(cols, false)); // closed[x][y] 表示这个格子是否已经处理过
vector<vector<pair<int, int>>> parent(rows, vector<pair<int, int>>(cols, {-1, -1})); // parent 用来记录路径从哪里来
priority_queue<Node, vector<Node>, Compare> open; // 创建 Open List，小根堆按 f 从小到大弹出
gScore[start.first][start.second] = 0; // 起点到起点的真实代价是 0
int startH = heuristic(start.first, start.second, goal.first, goal.second); // 计算起点到终点的预估代价
open.push({start.first, start.second, 0, startH, startH}); // 把起点加入 Open List
vector<int> dx = {-1, 1, 0, 0}; // 定义四方向移动的行变化：上、下、左、右
vector<int> dy = {0, 0, -1, 1}; // 定义四方向移动的列变化：上、下、左、右
while (!open.empty()) // 只要 Open List 里还有待检查节点
{ // while 循环开始
Node current = open.top(); // 取出 f 最小的节点
open.pop(); // 从 Open List 中弹出这个节点
if (closed[current.x][current.y]) // 如果这个节点已经处理过
{ // if 语句开始
continue; // 跳过旧节点，避免重复处理
} // if 语句结束
closed[current.x][current.y] = true; // 标记当前节点已经处理过
if (current.x == goal.first && current.y == goal.second) // 如果当前节点就是终点
{ // if 语句开始
return buildPath(parent, start, goal); // 根据 parent 反向还原路径并返回
} // if 语句结束
for (int dir = 0; dir < 4; dir++) // 遍历四个移动方向
{ // for 循环开始
int nx = current.x + dx[dir]; // 计算邻居节点的行坐标
int ny = current.y + dy[dir]; // 计算邻居节点的列坐标
if (!inBounds(nx, ny, rows, cols)) // 如果邻居节点越界
{ // if 语句开始
continue; // 越界格子不能走，直接跳过
} // if 语句结束
if (grid[nx][ny] == 1) // 如果邻居节点是障碍
{ // if 语句开始
continue; // 障碍格子不能走，直接跳过
} // if 语句结束
if (closed[nx][ny]) // 如果邻居节点已经处理过
{ // if 语句开始
continue; // 已处理节点不再重复处理
} // if 语句结束
int newG = gScore[current.x][current.y] + 1; // 计算从当前节点走到邻居节点的新 g 值
if (newG < gScore[nx][ny]) // 如果这条路径比之前记录的路径更短
{ // if 语句开始
gScore[nx][ny] = newG; // 更新邻居节点的最小真实代价
parent[nx][ny] = {current.x, current.y}; // 记录邻居节点是从当前节点走过来的
int h = heuristic(nx, ny, goal.first, goal.second); // 计算邻居节点到终点的预估代价
int f = newG + h; // 计算邻居节点的综合评分
open.push({nx, ny, newG, h, f}); // 把邻居节点加入 Open List，等待后续处理
} // if 语句结束
} // for 循环结束
} // while 循环结束
return {}; // 如果 Open List 空了还没找到终点，说明不存在路径，返回空数组
} // astar 函数结束
private: // private 表示下面的辅助函数只在类内部使用
int heuristic(int x1, int y1, int x2, int y2) // 定义启发函数，计算两个格子的曼哈顿距离
{ // heuristic 函数开始
return abs(x1 - x2) + abs(y1 - y2); // 返回四方向网格常用的曼哈顿距离
} // heuristic 函数结束
bool inBounds(int x, int y, int rows, int cols) // 定义边界判断函数
{ // inBounds 函数开始
return x >= 0 && x < rows && y >= 0 && y < cols; // 判断坐标是否在地图范围内
} // inBounds 函数结束
vector<pair<int, int>> buildPath(vector<vector<pair<int, int>>>& parent, pair<int, int> start, pair<int, int> goal) // 定义路径还原函数
{ // buildPath 函数开始
vector<pair<int, int>> path; // 创建 path 数组，用来保存最终路径
pair<int, int> current = goal; // 从终点开始往父节点倒推
while (current != make_pair(-1, -1)) // 只要当前节点不是无效节点
{ // while 循环开始
path.push_back(current); // 把当前节点加入路径
if (current == start) // 如果已经倒推到起点
{ // if 语句开始
break; // 路径还原完成，退出循环
} // if 语句结束
current = parent[current.first][current.second]; // 沿着 parent 继续往前找
} // while 循环结束
reverse(path.begin(), path.end()); // 因为刚才是从终点往起点找，所以反转成起点到终点
return path; // 返回最终路径
} // buildPath 函数结束
}; // Solution 类结束A* 的完整流程
可以按这个顺序记：
c
1. 起点加入 Open List
2. 从 Open List 取 f 最小的节点 current
3. 如果 current 是终点，路径找到
4. 把 current 放入 Closed Set
5. 遍历 current 的邻居
6. 跳过障碍、越界、已经关闭的节点
7. 计算 newG
8. 如果 newG 更小，就更新 g、h、f、parent
9. 把邻居加入 Open List
10. 重复直到找到终点或 Open List 为空为什么要记录 parent？
A* 搜索时只是在找路。
但最后要返回路径，比如：
c
S -> A -> B -> C -> G就必须知道：
每个节点是从哪个节点走过来的所以每次发现更短路径时，要记录：
c
parent[neighbor] = current找到终点后，从终点一路沿着 parent 倒推：
c
G -> C -> B -> A -> S然后反转，就得到最终路径：
c
S -> A -> B -> C -> G复杂度
如果用网格图，格子数量是：
c
V = rows * cols边数量大约是：
c
E ≈ 4V使用优先队列时：
c
时间复杂度：O(E log V)
空间复杂度：O(V)在普通四方向网格中，也可以理解为：
c
时间复杂度：O(rows * cols * log(rows * cols))
空间复杂度：O(rows * cols)面试高分回答
TIP
A* 是一种常用的启发式最短路径算法，适合游戏中的网格寻路或导航点寻路。它维护 g、h、f 三个值，其中 g 是从起点到当前点的真实代价，h 是当前点到终点的预估代价，f = g + h。算法每次从 Open List 中取出 f 最小的节点进行扩展，然后检查它的邻居，如果通过当前节点到达邻居的 g 更小，就更新邻居的 g、h、f 和父节点。Closed Set 用来避免重复处理已经确定的节点。最后找到终点后，通过 parent 从终点反向还原路径。A* 和 Dijkstra 的区别是多了启发函数 h，当 h = 0 时，A* 就退化成 Dijkstra。对于四方向网格，常用曼哈顿距离作为启发函数。