Appearance
题海扩展：算法强化
求数组中第 K 大元素
一句话定义： “数组中第 K 大元素”就是把数组按降序排好后，下标 k - 1 位置的元素，但面试里通常不建议真的全排序，而是用 Quickselect 快速选择。
核心思路： Quickselect 和快排一样做分区，但它只继续处理目标元素所在的一边。比如找第 2 大，目标下标就是 1。每次选一个 pivot，把比它大的放左边，比它小的放右边，如果 pivot 最终下标刚好是 k - 1，它就是答案。
复杂度： 平均时间复杂度：O(n) 最坏时间复杂度：O(n^2)，但随机 pivot 可以降低概率 空间复杂度：O(1)，原地分区 如果用小根堆：时间 O(n log k)，空间 O(k)，适合数据流或稳定求 Top K。
c
#include <iostream> // 引入输入输出库，用来打印结果。
#include <random> // 引入随机数库，用来随机选择 pivot。
#include <stdexcept> // 引入异常库，用来处理非法 k。
#include <utility> // 引入 swap，用来交换数组元素。
#include <vector> // 引入 vector，用来存储数组。
class Solution // 定义解题类。
{ // 类开始。
private: // 私有区域开始。
std::mt19937 rng_; // 随机数引擎，用来降低 Quickselect 退化概率。
int Partition(std::vector<int>& nums, int left, int right) // 对 nums[left, right] 做降序分区。
{ // 分区函数开始。
std::uniform_int_distribution<int> dist(left, right); // 创建范围为 [left, right] 的随机数分布。
int pivotIndex = dist(rng_); // 随机选择一个 pivot 下标。
int pivotValue = nums[pivotIndex]; // 记录 pivot 的值。
std::swap(nums[pivotIndex], nums[right]); // 把 pivot 临时放到最右边，方便分区。
int storeIndex = left; // storeIndex 表示下一个“大于 pivot”的元素应该放的位置。
for (int i = left; i < right; ++i) // 遍历 left 到 right - 1 的所有元素。
{ // for 循环开始。
if (nums[i] > pivotValue) // 因为找第 K 大，所以比 pivot 大的元素放左边。
{ // if 开始。
std::swap(nums[i], nums[storeIndex]); // 把当前较大元素换到左侧区域。
++storeIndex; // 左侧较大区域向右扩展一格。
} // if 结束。
} // for 循环结束。
std::swap(nums[storeIndex], nums[right]); // 把 pivot 放回它最终应该在的位置。
return storeIndex; // 返回 pivot 的最终下标。
} // 分区函数结束。
public: // 公有区域开始。
Solution() // 构造函数。
: rng_(std::random_device{}()) // 用随机设备初始化随机数引擎。
{ // 构造函数体开始。
} // 构造函数体结束。
int FindKthLargest(std::vector<int> nums, int k) // 查找第 k 大元素，nums 按值传入避免修改外部数组。
{ // 查找函数开始。
if (k < 1 || k > static_cast<int>(nums.size())) // 判断 k 是否越界。
{ // if 开始。
throw std::invalid_argument("k is out of range"); // k 非法时抛出异常。
} // if 结束。
int target = k - 1; // 第 k 大元素对应降序排列后的下标 k - 1。
int left = 0; // 初始化搜索区间左边界。
int right = static_cast<int>(nums.size()) - 1; // 初始化搜索区间右边界。
while (left <= right) // 只要搜索区间有效，就继续选择。
{ // while 开始。
int pivot = Partition(nums, left, right); // 对当前区间做一次降序分区。
if (pivot == target) // 如果 pivot 下标正好等于目标下标。
{ // if 开始。
return nums[pivot]; // 当前 pivot 值就是第 k 大元素。
} // if 结束。
if (pivot > target) // 如果 pivot 在目标右边，说明目标在左半区。
{ // if 开始。
right = pivot - 1; // 缩小到左半区继续找。
} // if 结束。
else // 如果 pivot 在目标左边，说明目标在右半区。
{ // else 开始。
left = pivot + 1; // 缩小到右半区继续找。
} // else 结束。
} // while 结束。
throw std::logic_error("unreachable"); // 正常逻辑不会走到这里。
} // 查找函数结束。
}; // 类结束。
int main() // 程序入口。
{ // main 开始。
std::vector<int> nums = {3, 2, 1, 5, 6, 4}; // 准备测试数组。
Solution solution; // 创建 Solution 对象。
std::cout << solution.FindKthLargest(nums, 2) << std::endl; // 输出第 2 大元素，结果是 5。
return 0; // 程序正常结束。
} // main 结束。面试容易加分的说法： 如果只问一次，第 K 大可以用 Quickselect，平均 O(n)。如果要维护实时排行榜、伤害榜、Top K 掉落记录，可以用大小为 k 的小根堆，稳定维护当前最大的 k 个元素。
求滑动窗口最大值
标准答案： 滑动窗口最大值最经典解法是 单调队列。队列里不存值，而是存数组下标，并且让这些下标对应的值从队头到队尾保持递减。这样每个窗口的最大值就是 nums[deque.front()]。
底层原理： 窗口往右移动时，有两件事：
- 队头下标如果已经离开窗口，就弹出。
- 当前元素进队前，把队尾所有小于等于当前值的元素弹出，因为它们以后不可能再成为最大值。
每个元素最多进队一次、出队一次，所以总时间复杂度是 O(n)。
C++ 实现：
c
#include <deque> // 引入双端队列，用来维护单调队列。
#include <iostream> // 引入输入输出库，用来打印结果。
#include <stdexcept> // 引入异常库，用来处理非法参数。
#include <vector> // 引入 vector，用来存储数组和答案。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有区域开始。
std::vector<int> MaxSlidingWindow(const std::vector<int>& nums, int k) // 定义函数，返回每个滑动窗口的最大值。
{ // 函数开始。
if (k <= 0 || k > static_cast<int>(nums.size())) // 判断窗口大小是否合法。
{ // if 开始。
throw std::invalid_argument("k is out of range"); // k 不合法时抛出异常。
} // if 结束。
std::vector<int> result; // 创建结果数组，用来保存每个窗口最大值。
std::deque<int> monoQueue; // 创建单调队列，里面存数组下标，不直接存值。
for (int i = 0; i < static_cast<int>(nums.size()); ++i) // 从左到右遍历数组。
{ // for 循环开始。
while (!monoQueue.empty() && monoQueue.front() <= i - k) // 如果队头下标已经不在当前窗口内。
{ // while 开始。
monoQueue.pop_front(); // 弹出过期下标。
} // while 结束。
while (!monoQueue.empty() && nums[monoQueue.back()] <= nums[i]) // 如果队尾元素小于等于当前元素。
{ // while 开始。
monoQueue.pop_back(); // 弹出队尾，因为它以后不可能成为最大值。
} // while 结束。
monoQueue.push_back(i); // 把当前元素下标加入队尾。
if (i >= k - 1) // 当窗口已经形成时，才开始记录答案。
{ // if 开始。
result.push_back(nums[monoQueue.front()]); // 队头下标对应的值就是当前窗口最大值。
} // if 结束。
} // for 循环结束。
return result; // 返回所有窗口最大值。
} // 函数结束。
}; // 类结束。
int main() // 程序入口。
{ // main 开始。
std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7}; // 准备测试数组。
int k = 3; // 设置窗口大小为 3。
Solution solution; // 创建解题对象。
std::vector<int> answer = solution.MaxSlidingWindow(nums, k); // 调用函数求滑动窗口最大值。
for (int value : answer) // 遍历答案数组。
{ // for 循环开始。
std::cout << value << " "; // 输出当前窗口最大值。
} // for 循环结束。
return 0; // 程序正常结束。
} // main 结束。复杂度： 时间复杂度：O(n) 空间复杂度：O(k)，队列最多保存一个窗口内的下标。
面试关键点： 一定要说清楚“队列存的是下标”，因为只有下标才能判断元素是否已经滑出窗口。不要说成“维护一个最大值变量”，因为最大值离开窗口后，你无法快速知道新的最大值是谁。
求两个有序数组中位数
标准答案： 两个有序数组中位数，最优解不是合并数组，而是用 二分分割线。我们在较短数组上二分切一刀，同时在另一个数组上切一刀，让左半边元素数量等于右半边，且满足：
c
Aleft <= Bright
Bleft <= Aright满足后，中位数就在切口旁边。
核心思路： 假设两个数组总长度是 m + n，左半边需要放：
c
half = (m + n + 1) / 2在数组 A 中切 i 个元素，那么数组 B 中就要切：
c
j = half - i如果 Aleft > Bright，说明 A 左边切多了，要往左移。 如果 Bleft > Aright，说明 A 左边切少了，要往右移。
C++ 实现：
c
#include <algorithm> // 引入 max 和 min，用来计算切口两侧的最大值和最小值。
#include <climits> // 引入 INT_MIN 和 INT_MAX，用来处理数组边界哨兵。
#include <iostream> // 引入输入输出库，用来打印结果。
#include <stdexcept> // 引入异常库，用来处理非法输入。
#include <vector> // 引入 vector，用来存储数组。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有区域开始。
double FindMedianSortedArrays(const std::vector<int>& nums1, const std::vector<int>& nums2) // 定义函数，返回两个有序数组的中位数。
{ // 函数开始。
if (nums1.empty() && nums2.empty()) // 如果两个数组都为空。
{ // if 开始。
throw std::invalid_argument("both arrays are empty"); // 抛出非法参数异常。
} // if 结束。
if (nums1.size() > nums2.size()) // 如果第一个数组比第二个数组长。
{ // if 开始。
return FindMedianSortedArrays(nums2, nums1); // 交换顺序，保证始终在较短数组上二分。
} // if 结束。
int m = static_cast<int>(nums1.size()); // 记录较短数组 nums1 的长度。
int n = static_cast<int>(nums2.size()); // 记录较长数组 nums2 的长度。
int left = 0; // 二分左边界，表示 nums1 最少切 0 个元素。
int right = m; // 二分右边界，表示 nums1 最多切 m 个元素。
int half = (m + n + 1) / 2; // 计算左半边需要容纳的元素数量，奇数时左边多一个。
while (left <= right) // 当二分区间有效时继续搜索。
{ // while 开始。
int i = left + (right - left) / 2; // 在 nums1 中切 i 个元素。
int j = half - i; // 在 nums2 中切 j 个元素，保证左半边总数为 half。
int nums1Left = (i == 0) ? INT_MIN : nums1[i - 1]; // nums1 切口左侧最大值，左侧为空时用负无穷。
int nums1Right = (i == m) ? INT_MAX : nums1[i]; // nums1 切口右侧最小值，右侧为空时用正无穷。
int nums2Left = (j == 0) ? INT_MIN : nums2[j - 1]; // nums2 切口左侧最大值，左侧为空时用负无穷。
int nums2Right = (j == n) ? INT_MAX : nums2[j]; // nums2 切口右侧最小值，右侧为空时用正无穷。
if (nums1Left <= nums2Right && nums2Left <= nums1Right) // 如果左半边所有元素都不大于右半边所有元素。
{ // if 开始。
int leftMax = std::max(nums1Left, nums2Left); // 计算左半边最大值。
int rightMin = std::min(nums1Right, nums2Right); // 计算右半边最小值。
if (((m + n) % 2) == 1) // 如果总长度是奇数。
{ // if 开始。
return static_cast<double>(leftMax); // 中位数就是左半边最大值。
} // if 结束。
return (static_cast<double>(leftMax) + static_cast<double>(rightMin)) / 2.0; // 总长度是偶数时，返回中间两个数的平均值。
} // if 结束。
if (nums1Left > nums2Right) // 如果 nums1 左边最大值太大，说明 nums1 切多了。
{ // if 开始。
right = i - 1; // 向左缩小二分范围。
} // if 结束。
else // 否则说明 nums2 左边最大值太大，也就是 nums1 切少了。
{ // else 开始。
left = i + 1; // 向右扩大 nums1 的切割数量。
} // else 结束。
} // while 结束。
throw std::logic_error("invalid sorted input"); // 如果输入不是有序数组，可能无法找到合法分割。
} // 函数结束。
}; // 类结束。
int main() // 程序入口。
{ // main 开始。
std::vector<int> nums1 = {1, 3, 8, 9, 15}; // 定义第一个有序数组。
std::vector<int> nums2 = {7, 11, 18, 19, 21, 25}; // 定义第二个有序数组。
Solution solution; // 创建解题对象。
std::cout << solution.FindMedianSortedArrays(nums1, nums2) << std::endl; // 输出中位数，结果是 11。
return 0; // 程序正常结束。
} // main 结束。复杂度： 时间复杂度：O(log min(m, n)) 空间复杂度：O(1)
面试关键点： 一定要说“在较短数组上二分”，否则复杂度可能写成 O(log(m+n)) 但实现容易越界。切口两侧要用 INT_MIN 和 INT_MAX 做哨兵，避免数组为空或切在边界时访问越界。
求最长连续序列
标准答案： 最长连续序列用 HashSet 做最合适。先把所有数字放进集合，然后只从“没有前驱”的数字开始扩展。比如 1 没有 0，所以它是一段序列的起点，然后依次查 2、3、4 是否存在。
核心点： 这题不是找“原数组里连续的一段”，而是找“数值连续”。 例如 [100, 4, 200, 1, 3, 2]，最长连续序列是 [1, 2, 3, 4]，答案是 4。
c
#include <algorithm> // 引入 std::max，用来更新最大长度。
#include <climits> // 引入 INT_MIN 和 INT_MAX，用来处理整数边界。
#include <iostream> // 引入输入输出库，用来打印结果。
#include <unordered_set> // 引入哈希集合，用来快速判断数字是否存在。
#include <vector> // 引入 vector，用来存储数组。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有区域开始。
int LongestConsecutive(const std::vector<int>& nums) // 定义函数，返回最长连续序列长度。
{ // 函数开始。
std::unordered_set<int> values(nums.begin(), nums.end()); // 把数组元素放入哈希集合，同时自动去重。
int best = 0; // 记录当前找到的最长连续序列长度。
for (int value : values) // 遍历哈希集合中的每个数字。
{ // for 循环开始。
if (value != INT_MIN && values.find(value - 1) != values.end()) // 如果 value 有前驱 value - 1，说明它不是序列起点。
{ // if 开始。
continue; // 跳过非起点，避免重复向右扩展。
} // if 结束。
int current = value; // current 表示当前扩展到的数字。
int length = 1; // length 表示从当前起点开始的连续序列长度。
while (current != INT_MAX && values.find(current + 1) != values.end()) // 如果下一个连续数字存在，就继续扩展。
{ // while 循环开始。
++current; // 当前数字向右移动一位。
++length; // 当前连续序列长度加一。
} // while 循环结束。
best = std::max(best, length); // 用当前序列长度更新最大答案。
} // for 循环结束。
return best; // 返回最长连续序列长度。
} // 函数结束。
}; // 类结束。
int main() // 程序入口。
{ // main 开始。
std::vector<int> nums = {100, 4, 200, 1, 3, 2}; // 准备测试数组。
Solution solution; // 创建解题对象。
std::cout << solution.LongestConsecutive(nums) << std::endl; // 输出最长连续序列长度，结果是 4。
return 0; // 程序正常结束。
} // main 结束。复杂度： 平均时间复杂度：O(n) 空间复杂度：O(n)
面试关键点： 不要对每个数字都向右扩展，否则会退化成重复计算。只从 x - 1 不存在的数字开始扩展，才能保证每段连续序列只被完整扫描一次。
求缺失数字
标准答案： 缺失数字通常指：数组长度为 n，里面包含 0..n 中的 n 个不同数字，缺了一个，要求找出缺失的那个。
最推荐用 异或法：完整范围 0..n 异或一遍，数组元素再异或一遍。相同数字会抵消，最后剩下的就是缺失数字。
底层原理：
c
x ^ x = 0
x ^ 0 = x比如：
c
nums = [3, 0, 1]
完整范围 = [0, 1, 2, 3]
0、1、3 都出现两次，会抵消
只剩下 2C++ 实现：
c
#include <iostream> // 引入输入输出库，用来打印结果。
#include <vector> // 引入 vector，用来存储数组。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有区域开始。
int MissingNumber(const std::vector<int>& nums) // 定义函数，返回缺失的数字。
{ // 函数开始。
int answer = static_cast<int>(nums.size()); // 先把 n 放进异或结果，因为完整范围包含 0 到 n。
for (int i = 0; i < static_cast<int>(nums.size()); ++i) // 遍历数组下标 0 到 n - 1。
{ // for 循环开始。
answer ^= i; // 异或当前下标，相当于加入完整范围中的一个数字。
answer ^= nums[i]; // 异或当前数组值，用来和完整范围里的相同数字抵消。
} // for 循环结束。
return answer; // 返回最后没有被抵消掉的数字，也就是缺失数字。
} // 函数结束。
}; // 类结束。
int main() // 程序入口。
{ // main 开始。
std::vector<int> nums = {3, 0, 1}; // 准备测试数组，完整范围是 0 到 3。
Solution solution; // 创建解题对象。
std::cout << solution.MissingNumber(nums) << std::endl; // 输出缺失数字，结果是 2。
return 0; // 程序正常结束。
} // main 结束。复杂度： 时间复杂度：O(n) 空间复杂度：O(1)
面试关键点： 求和法也可以做：n * (n + 1) / 2 - sum(nums)，但异或法不会有整数溢出的风险。还要注意范围是 0..n，所以缺失数字可能是 0，也可能是 n。
求多数元素
标准答案： 多数元素是指在数组中出现次数 超过 n / 2 的元素。最优解是 Boyer-Moore 投票法，时间 O(n)，空间 O(1)。
核心原理： 把多数元素和非多数元素两两抵消。因为多数元素数量超过一半，所以它和所有其他元素抵消完之后，最后剩下的候选人一定是多数元素。
c
#include <iostream> // 引入输入输出库，用来打印结果。
#include <stdexcept> // 引入异常库，用来在没有多数元素时抛异常。
#include <vector> // 引入 vector，用来存储数组。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有区域开始。
int MajorityElement(const std::vector<int>& nums) // 定义函数，返回多数元素。
{ // 函数开始。
int candidate = 0; // candidate 表示当前候选的多数元素。
int count = 0; // count 表示当前候选人的票数。
for (int value : nums) // 遍历数组中的每个元素。
{ // for 循环开始。
if (count == 0) // 如果当前票数为 0，说明之前的候选人已经被抵消完。
{ // if 开始。
candidate = value; // 把当前元素设置为新的候选人。
} // if 结束。
if (value == candidate) // 如果当前元素等于候选人。
{ // if 开始。
++count; // 候选人票数加一。
} // if 结束。
else // 如果当前元素不等于候选人。
{ // else 开始。
--count; // 当前元素和候选人互相抵消，票数减一。
} // else 结束。
} // for 循环结束。
int realCount = 0; // realCount 用来二次验证候选人真实出现次数。
for (int value : nums) // 再遍历一次数组。
{ // for 循环开始。
if (value == candidate) // 如果当前元素等于候选人。
{ // if 开始。
++realCount; // 候选人真实次数加一。
} // if 结束。
} // for 循环结束。
if (realCount <= static_cast<int>(nums.size()) / 2) // 如果候选人没有超过数组长度一半。
{ // if 开始。
throw std::logic_error("majority element does not exist"); // 抛出异常，说明不存在多数元素。
} // if 结束。
return candidate; // 返回真正的多数元素。
} // 函数结束。
}; // 类结束。
int main() // 程序入口。
{ // main 开始。
std::vector<int> nums = {2, 2, 1, 1, 1, 2, 2}; // 准备测试数组。
Solution solution; // 创建解题对象。
std::cout << solution.MajorityElement(nums) << std::endl; // 输出多数元素，结果是 2。
return 0; // 程序正常结束。
} // main 结束。复杂度： 时间复杂度：O(n) 空间复杂度：O(1)
面试关键点： 如果题目保证多数元素一定存在，可以不用二次验证；如果不保证存在，投票法只能得到“候选人”，必须再扫一遍确认它是否真的超过 n / 2。
求数组中的逆序对
标准答案： 数组中的逆序对是指满足：
c
i < j 且 nums[i] > nums[j]的元素对。比如 [7, 5, 6, 4] 里面有：
c
(7,5), (7,6), (7,4), (5,4), (6,4)所以答案是 5。
核心思路： 暴力枚举两层循环是 O(n²)。更好的做法是用 归并排序，在合并两个已经有序的区间时统计逆序对。
关键点是： 如果左区间当前值 nums[i] > nums[j]，因为左区间已经有序，所以 nums[i] 到 nums[mid] 都大于 nums[j]，可以一次加：
c
mid - i + 1C++ 实现：
c
#include <iostream> // 引入输入输出库，用来打印结果。
#include <vector> // 引入 vector，用来存储数组和辅助数组。
class Solution // 定义解题类。
{ // 类开始。
private: // 私有区域开始。
long long Merge(std::vector<int>& nums, std::vector<int>& temp, int left, int mid, int right) // 合并两个有序区间并统计跨区间逆序对。
{ // Merge 函数开始。
int i = left; // i 指向左半区间的起点。
int j = mid + 1; // j 指向右半区间的起点。
int k = left; // k 指向辅助数组当前要写入的位置。
long long count = 0; // count 记录当前合并过程中产生的逆序对数量。
while (i <= mid && j <= right) // 当左右两个区间都还有元素时继续合并。
{ // while 开始。
if (nums[i] <= nums[j]) // 如果左边元素不大于右边元素，不构成逆序对。
{ // if 开始。
temp[k] = nums[i]; // 把较小的左边元素放入辅助数组。
++i; // 左半区间指针右移。
++k; // 辅助数组写入位置右移。
} // if 结束。
else // 如果 nums[i] > nums[j]，说明出现跨区间逆序对。
{ // else 开始。
count += static_cast<long long>(mid - i + 1); // 左区间从 i 到 mid 的元素都大于 nums[j]，一次性计数。
temp[k] = nums[j]; // 把较小的右边元素放入辅助数组。
++j; // 右半区间指针右移。
++k; // 辅助数组写入位置右移。
} // else 结束。
} // 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 index = left; index <= right; ++index) // 遍历本次合并覆盖的区间。
{ // for 开始。
nums[index] = temp[index]; // 把辅助数组中的有序结果拷回原数组。
} // for 结束。
return count; // 返回本次合并统计出的逆序对数量。
} // Merge 函数结束。
long long MergeSort(std::vector<int>& nums, std::vector<int>& temp, int left, int right) // 归并排序并统计逆序对。
{ // MergeSort 函数开始。
if (left >= right) // 如果区间里只有一个元素或没有元素。
{ // if 开始。
return 0; // 单个元素不可能形成逆序对。
} // if 结束。
int mid = left + (right - left) / 2; // 计算中点，避免 left + right 溢出。
long long count = 0; // count 记录当前区间的逆序对数量。
count += MergeSort(nums, temp, left, mid); // 统计左半区间内部的逆序对。
count += MergeSort(nums, temp, mid + 1, right); // 统计右半区间内部的逆序对。
count += Merge(nums, temp, left, mid, right); // 统计跨左右区间的逆序对。
return count; // 返回当前区间总逆序对数量。
} // MergeSort 函数结束。
public: // 公有区域开始。
long long ReversePairs(std::vector<int> nums) // 定义函数，返回数组中的逆序对数量。
{ // ReversePairs 函数开始。
if (nums.empty()) // 如果数组为空。
{ // if 开始。
return 0; // 空数组没有逆序对。
} // if 结束。
std::vector<int> temp(nums.size()); // 创建辅助数组，用于归并过程。
return MergeSort(nums, temp, 0, static_cast<int>(nums.size()) - 1); // 从整个数组范围开始归并统计。
} // ReversePairs 函数结束。
}; // 类结束。
int main() // 程序入口。
{ // main 开始。
std::vector<int> nums = {7, 5, 6, 4}; // 准备测试数组。
Solution solution; // 创建解题对象。
std::cout << solution.ReversePairs(nums) << std::endl; // 输出逆序对数量，结果是 5。
return 0; // 程序正常结束。
} // main 结束。复杂度： 时间复杂度：O(n log n) 空间复杂度：O(n) 逆序对数量可能很大，建议用 long long 保存。
面试关键点： 普通逆序对是 nums[i] > nums[j]，不要和“重要翻转对”混淆，后者条件是 nums[i] > 2 * nums[j]。
合并 K 个有序数组
标准答案： 合并 K 个有序数组，最常用做法是 小根堆多路归并。每个数组先放入第一个元素，堆顶永远是当前所有数组指针里最小的元素。弹出堆顶加入结果后，再把它所在数组的下一个元素放入堆。
核心思路： 堆里不能只存 value，还要存：
value：当前值
arrayIndex：来自第几个数组
elementIndex：在该数组中的下标否则弹出一个元素后，你不知道应该推进哪个数组。
c
#include <iostream> // 引入输入输出库，用来打印合并结果。
#include <queue> // 引入优先队列，用来实现小根堆。
#include <vector> // 引入 vector，用来存储多个数组和结果数组。
class Solution // 定义解题类。
{ // 类开始。
private: // 私有区域开始。
struct Node // 定义堆节点，表示某个数组中的一个元素。
{ // Node 结构体开始。
int value; // value 表示当前元素的值。
int arrayIndex; // arrayIndex 表示当前元素来自第几个数组。
int elementIndex; // elementIndex 表示当前元素在它所属数组中的下标。
}; // Node 结构体结束。
struct Greater // 定义比较器，用来让 priority_queue 变成小根堆。
{ // Greater 结构体开始。
bool operator()(const Node& left, const Node& right) const // 重载比较函数。
{ // 比较函数开始。
return left.value > right.value; // 值更大的优先级更低，所以堆顶会是最小值。
} // 比较函数结束。
}; // Greater 结构体结束。
public: // 公有区域开始。
std::vector<int> MergeKSortedArrays(const std::vector<std::vector<int>>& arrays) // 合并 K 个有序数组。
{ // 函数开始。
std::priority_queue<Node, std::vector<Node>, Greater> minHeap; // 创建小根堆，堆里最多放 K 个候选元素。
std::vector<int> result; // 创建结果数组，用来保存最终合并后的升序序列。
for (int i = 0; i < static_cast<int>(arrays.size()); ++i) // 遍历每一个数组。
{ // for 循环开始。
if (!arrays[i].empty()) // 如果当前数组不是空数组。
{ // if 开始。
minHeap.push(Node{arrays[i][0], i, 0}); // 把当前数组的第一个元素放入小根堆。
} // if 结束。
} // for 循环结束。
while (!minHeap.empty()) // 只要堆里还有候选元素，就继续合并。
{ // while 循环开始。
Node current = minHeap.top(); // 取出当前所有候选元素中的最小值。
minHeap.pop(); // 从堆中删除这个最小节点。
result.push_back(current.value); // 把最小值加入结果数组。
int nextIndex = current.elementIndex + 1; // 计算当前元素所在数组的下一个下标。
if (nextIndex < static_cast<int>(arrays[current.arrayIndex].size())) // 如果该数组还有下一个元素。
{ // if 开始。
minHeap.push(Node{arrays[current.arrayIndex][nextIndex], current.arrayIndex, nextIndex}); // 把下一个元素放入堆。
} // if 结束。
} // while 循环结束。
return result; // 返回合并后的升序数组。
} // 函数结束。
}; // 类结束。
int main() // 程序入口。
{ // main 开始。
std::vector<std::vector<int>> arrays = {{1, 4, 7}, {2, 5, 8}, {0, 3, 9}}; // 准备 K 个有序数组。
Solution solution; // 创建解题对象。
std::vector<int> answer = solution.MergeKSortedArrays(arrays); // 调用函数合并 K 个有序数组。
for (int value : answer) // 遍历合并结果。
{ // for 循环开始。
std::cout << value << " "; // 输出当前元素。
} // for 循环结束。
return 0; // 程序正常结束。
} // main 结束。复杂度： 设总元素个数是 N，数组个数是 K。 时间复杂度：O(N log K) 空间复杂度：O(K)，小根堆最多保存每个数组的一个候选元素。
面试关键点： 小根堆不是把所有元素一次性放进去，那样空间会变成 O(N)。多路归并只维护每个数组当前指针指向的元素，所以空间更省。
实现 Trie
标准答案： Trie 又叫前缀树，适合做字符串集合、前缀匹配、自动补全、敏感词过滤、字典搜索。它不是把整个字符串存在一个节点里，而是把字符串拆成一条“字符路径”。
比如插入：
c
app
apple
batapp 和 apple 会共享 a -> p -> p 这段路径，区别在于 app 的最后一个 p 节点 isEnd = true，而 apple 还会继续往下走 l -> e。
C++ 实现：
c
#include <array> // 引入 array，用来保存 26 个子节点指针。
#include <iostream> // 引入输入输出库，用来打印测试结果。
#include <memory> // 引入 unique_ptr，用 RAII 自动管理 Trie 节点内存。
#include <stdexcept> // 引入异常库，用来处理非法字符。
#include <string> // 引入 string，用来表示单词和前缀。
class Trie // 定义 Trie 前缀树类。
{ // 类开始。
private: // 私有区域开始。
struct TrieNode // 定义 Trie 节点结构。
{ // TrieNode 开始。
std::array<std::unique_ptr<TrieNode>, 26> children{}; // children[i] 表示第 i 个小写字母对应的子节点。
bool isEnd = false; // isEnd 表示从根到当前节点是否构成一个完整单词。
}; // TrieNode 结束。
std::unique_ptr<TrieNode> root_; // root_ 是 Trie 的根节点，本身不代表任何字符。
const TrieNode* FindNode(const std::string& text) const // 根据字符串路径查找最后一个节点。
{ // FindNode 开始。
const TrieNode* node = root_.get(); // 从根节点开始查找。
for (char ch : text) // 逐字符遍历字符串。
{ // for 开始。
if (ch < 'a' || ch > 'z') // 如果字符不是小写字母。
{ // if 开始。
return nullptr; // 返回空，表示路径非法或不存在。
} // if 结束。
int index = ch - 'a'; // 把字符映射到 0 到 25 的数组下标。
if (!node->children[index]) // 如果当前字符对应的子节点不存在。
{ // if 开始。
return nullptr; // 路径断了，说明字符串或前缀不存在。
} // if 结束。
node = node->children[index].get(); // 继续走到下一个字符节点。
} // for 结束。
return node; // 返回路径最后一个节点。
} // FindNode 结束。
public: // 公有区域开始。
Trie() // Trie 构造函数。
: root_(std::make_unique<TrieNode>()) // 创建根节点。
{ // 构造函数体开始。
} // 构造函数体结束。
void Insert(const std::string& word) // 插入一个单词。
{ // Insert 开始。
TrieNode* node = root_.get(); // 从根节点开始插入。
for (char ch : word) // 逐字符处理单词。
{ // for 开始。
if (ch < 'a' || ch > 'z') // 如果字符不是小写字母。
{ // if 开始。
throw std::invalid_argument("only lowercase letters are supported"); // 抛出异常，说明当前实现只支持 a 到 z。
} // if 结束。
int index = ch - 'a'; // 把字符转换成 children 数组下标。
if (!node->children[index]) // 如果当前字符路径还不存在。
{ // if 开始。
node->children[index] = std::make_unique<TrieNode>(); // 创建新的 Trie 节点。
} // if 结束。
node = node->children[index].get(); // 移动到当前字符对应的节点。
} // for 结束。
node->isEnd = true; // 单词插入完成，把最后节点标记为完整单词结尾。
} // Insert 结束。
bool Search(const std::string& word) const // 判断完整单词是否存在。
{ // Search 开始。
const TrieNode* node = FindNode(word); // 查找单词路径的最后节点。
return node != nullptr && node->isEnd; // 路径存在且最后节点是单词结尾，才说明单词存在。
} // Search 结束。
bool StartsWith(const std::string& prefix) const // 判断是否存在某个前缀。
{ // StartsWith 开始。
return FindNode(prefix) != nullptr; // 只要前缀路径存在，就返回 true。
} // StartsWith 结束。
}; // Trie 类结束。
int main() // 程序入口。
{ // main 开始。
Trie trie; // 创建 Trie 对象。
trie.Insert("app"); // 插入单词 app。
trie.Insert("apple"); // 插入单词 apple。
trie.Insert("bat"); // 插入单词 bat。
std::cout << trie.Search("app") << std::endl; // 输出 1，表示 app 是完整单词。
std::cout << trie.Search("ap") << std::endl; // 输出 0，表示 ap 只是前缀，不是完整单词。
std::cout << trie.StartsWith("ap") << std::endl; // 输出 1，表示存在以 ap 开头的单词。
return 0; // 程序正常结束。
} // main 结束。复杂度： 设字符串长度为 L。 Insert 时间复杂度：O(L)Search 时间复杂度：O(L)StartsWith 时间复杂度：O(L) 空间复杂度取决于总字符节点数量，最坏接近所有单词长度之和。
面试关键点：Search("ap") 和 StartsWith("ap") 不一样。ap 的路径存在，只能说明它是前缀；只有最后节点 isEnd = true，才说明它是完整单词。
实现并查集
标准答案： 并查集是一种维护“若干个不相交集合”的数据结构，主要支持两个操作：
Find(x)：找到 x 所在集合的代表节点
Union(a, b)：把 a 和 b 所在的集合合并常用来判断连通性，比如图里两个点是否连通、好友圈数量、岛屿合并、最小生成树 Kruskal。
核心原理： 用 parent[x] 表示 x 的父节点。 如果 parent[x] == x，说明 x 是这个集合的根节点，也就是集合代表。
优化有两个：
路径压缩：Find 时把沿途节点直接挂到根上
按大小合并：Union 时让小集合挂到大集合下面C++ 实现：
c
#include <iostream> // 引入输入输出库，用来打印测试结果。
#include <stdexcept> // 引入异常库，用来处理非法下标。
#include <vector> // 引入 vector，用来保存 parent 和 size 数组。
class UnionFind // 定义并查集类。
{ // 类开始。
private: // 私有区域开始。
std::vector<int> parent_; // parent_[x] 表示 x 的父节点。
std::vector<int> size_; // size_[root] 表示以 root 为根的集合大小。
int setCount_; // setCount_ 表示当前还有多少个集合。
void CheckIndex(int x) const // 检查下标是否合法。
{ // CheckIndex 函数开始。
if (x < 0 || x >= static_cast<int>(parent_.size())) // 如果 x 不在合法范围内。
{ // if 开始。
throw std::out_of_range("index is out of range"); // 抛出越界异常。
} // if 结束。
} // CheckIndex 函数结束。
public: // 公有区域开始。
explicit UnionFind(int n) // 构造函数，创建 n 个独立集合。
: parent_() // 初始化 parent_ 为空数组。
, size_() // 初始化 size_ 为空数组。
, setCount_(0) // 初始化集合数量为 0。
{ // 构造函数开始。
if (n < 0) // 如果元素数量为负数。
{ // if 开始。
throw std::invalid_argument("n must be non-negative"); // 抛出非法参数异常。
} // if 结束。
parent_.resize(n); // 把 parent_ 数组大小设置为 n。
size_.assign(n, 1); // 把每个集合的初始大小设置为 1。
setCount_ = n; // 初始时每个元素都是一个独立集合。
for (int i = 0; i < n; ++i) // 遍历所有元素。
{ // for 开始。
parent_[i] = i; // 初始化时每个元素的父节点都是自己。
} // for 结束。
} // 构造函数结束。
int Find(int x) // 查找 x 所在集合的根节点。
{ // Find 函数开始。
CheckIndex(x); // 先检查 x 是否越界。
if (parent_[x] != x) // 如果 x 不是根节点。
{ // if 开始。
parent_[x] = Find(parent_[x]); // 路径压缩，把 x 直接挂到根节点下面。
} // if 结束。
return parent_[x]; // 返回 x 所在集合的根节点。
} // Find 函数结束。
bool Unite(int a, int b) // 合并 a 和 b 所在的集合。
{ // Unite 函数开始。
int rootA = Find(a); // 找到 a 所在集合的根。
int rootB = Find(b); // 找到 b 所在集合的根。
if (rootA == rootB) // 如果两个元素已经属于同一个集合。
{ // if 开始。
return false; // 不需要合并，返回 false。
} // if 结束。
if (size_[rootA] < size_[rootB]) // 如果 A 集合比 B 集合小。
{ // if 开始。
std::swap(rootA, rootB); // 交换两个根，保证 rootA 是较大的集合。
} // if 结束。
parent_[rootB] = rootA; // 把小集合的根挂到大集合的根下面。
size_[rootA] += size_[rootB]; // 更新合并后集合的大小。
--setCount_; // 两个集合合并成一个，集合数量减一。
return true; // 合并成功，返回 true。
} // Unite 函数结束。
bool Connected(int a, int b) // 判断 a 和 b 是否属于同一个集合。
{ // Connected 函数开始。
return Find(a) == Find(b); // 如果两个元素根节点相同，说明连通。
} // Connected 函数结束。
int SetCount() const // 获取当前集合数量。
{ // SetCount 函数开始。
return setCount_; // 返回当前集合数量。
} // SetCount 函数结束。
}; // UnionFind 类结束。
int main() // 程序入口。
{ // main 开始。
UnionFind uf(6); // 创建包含 0 到 5 的并查集。
uf.Unite(0, 1); // 合并 0 和 1。
uf.Unite(1, 2); // 合并 1 和 2，此时 0、1、2 连通。
uf.Unite(3, 4); // 合并 3 和 4。
std::cout << uf.Connected(0, 2) << std::endl; // 输出 1，表示 0 和 2 连通。
std::cout << uf.Connected(0, 4) << std::endl; // 输出 0，表示 0 和 4 不连通。
std::cout << uf.SetCount() << std::endl; // 输出当前集合数量。
return 0; // 程序正常结束。
} // main 结束。复杂度： 路径压缩 + 按大小合并后，Find 和 Union 的摊还复杂度接近 O(1)，更严谨地说是 O(α(n))，这里的 α(n) 增长极慢。
面试关键点：Union(a, b) 不能直接写 parent[a] = b，必须先 Find(a) 和 Find(b) 找到两个集合的根，再合并根节点。
判断图是否有环
标准答案： 判断图是否有环，首先要问清楚：这是 有向图 还是 无向图。
有向图常用 三色 DFS： 0 = 未访问，1 = 正在访问，2 = 已完成。 如果 DFS 过程中遇到 color[v] == 1 的节点，说明指回了当前递归栈，有环。
无向图常用 并查集： 遍历每条边 (u, v)，如果 u 和 v 已经在同一个集合里，再连这条边就会形成环。
c
#include <iostream> // 引入输入输出库，用来打印测试结果。
#include <numeric> // 引入 iota，用来初始化并查集 parent 数组。
#include <utility> // 引入 pair，用来表示图中的边。
#include <vector> // 引入 vector，用来存储邻接表、边和并查集数组。
class DirectedCycleDetector // 定义有向图判环类。
{ // 类开始。
private: // 私有区域开始。
bool Dfs(int node, const std::vector<std::vector<int>>& graph, std::vector<int>& color) // DFS 判断从 node 出发是否能找到环。
{ // Dfs 函数开始。
color[node] = 1; // 把当前节点标记为灰色，表示正在递归栈中。
for (int next : graph[node]) // 遍历当前节点指向的所有邻居。
{ // for 开始。
if (color[next] == 1) // 如果邻居是灰色，说明指回了当前递归栈。
{ // if 开始。
return true; // 找到有向环。
} // if 结束。
if (color[next] == 0 && Dfs(next, graph, color)) // 如果邻居未访问，就继续 DFS。
{ // if 开始。
return true; // 子递归中找到环，直接返回 true。
} // if 结束。
} // for 结束。
color[node] = 2; // 当前节点所有后继都处理完，标记为黑色。
return false; // 从当前节点出发没有找到环。
} // Dfs 函数结束。
public: // 公有区域开始。
bool HasCycle(int n, const std::vector<std::pair<int, int>>& edges) // 判断有向图是否有环。
{ // HasCycle 函数开始。
std::vector<std::vector<int>> graph(n); // 创建邻接表。
for (const auto& edge : edges) // 遍历所有有向边。
{ // for 开始。
graph[edge.first].push_back(edge.second); // 加入有向边 edge.first -> edge.second。
} // for 结束。
std::vector<int> color(n, 0); // 初始化所有节点为白色，也就是未访问。
for (int i = 0; i < n; ++i) // 遍历每个节点，防止图不连通。
{ // for 开始。
if (color[i] == 0 && Dfs(i, graph, color)) // 如果当前节点未访问，就从它开始 DFS。
{ // if 开始。
return true; // 找到环。
} // if 结束。
} // for 结束。
return false; // 所有节点都检查完，没有环。
} // HasCycle 函数结束。
}; // DirectedCycleDetector 类结束。
class UnionFind // 定义并查集类，用于无向图判环。
{ // 类开始。
private: // 私有区域开始。
std::vector<int> parent_; // parent_[x] 表示 x 的父节点。
std::vector<int> size_; // size_[x] 表示以 x 为根的集合大小。
public: // 公有区域开始。
explicit UnionFind(int n) // 构造函数，初始化 n 个独立集合。
: parent_(n) // 创建 parent_ 数组。
, size_(n, 1) // 创建 size_ 数组，并把每个集合大小初始化为 1。
{ // 构造函数开始。
std::iota(parent_.begin(), parent_.end(), 0); // 初始化 parent_[i] = i。
} // 构造函数结束。
int Find(int x) // 查找 x 所在集合的根节点。
{ // Find 函数开始。
if (parent_[x] != x) // 如果 x 不是根节点。
{ // if 开始。
parent_[x] = Find(parent_[x]); // 路径压缩，把 x 直接挂到根节点。
} // if 结束。
return parent_[x]; // 返回 x 的根节点。
} // Find 函数结束。
bool Unite(int a, int b) // 合并 a 和 b 所在集合。
{ // Unite 函数开始。
int rootA = Find(a); // 找到 a 的根节点。
int rootB = Find(b); // 找到 b 的根节点。
if (rootA == rootB) // 如果两个点已经在同一个集合。
{ // if 开始。
return false; // 合并失败，说明这条边会形成环。
} // if 结束。
if (size_[rootA] < size_[rootB]) // 如果 A 集合比 B 集合小。
{ // if 开始。
std::swap(rootA, rootB); // 交换根节点，让 rootA 始终代表较大集合。
} // if 结束。
parent_[rootB] = rootA; // 把小集合挂到大集合下面。
size_[rootA] += size_[rootB]; // 更新合并后的集合大小。
return true; // 合并成功。
} // Unite 函数结束。
}; // UnionFind 类结束。
bool UndirectedHasCycle(int n, const std::vector<std::pair<int, int>>& edges) // 判断无向图是否有环。
{ // 函数开始。
UnionFind uf(n); // 创建并查集。
for (const auto& edge : edges) // 遍历无向图的每条边。
{ // for 开始。
if (!uf.Unite(edge.first, edge.second)) // 如果两个端点已经同属一个集合。
{ // if 开始。
return true; // 再连这条边就形成环。
} // if 结束。
} // for 结束。
return false; // 所有边处理完都没有形成环。
} // 函数结束。
int main() // 程序入口。
{ // main 开始。
DirectedCycleDetector detector; // 创建有向图判环对象。
std::vector<std::pair<int, int>> directedEdges = {{0, 1}, {1, 2}, {2, 0}}; // 定义有向图边，0 -> 1 -> 2 -> 0。
std::vector<std::pair<int, int>> undirectedEdges = {{0, 1}, {1, 2}, {2, 0}}; // 定义无向图边，形成三角形。
std::cout << detector.HasCycle(3, directedEdges) << std::endl; // 输出 1，表示有向图有环。
std::cout << UndirectedHasCycle(3, undirectedEdges) << std::endl; // 输出 1，表示无向图有环。
return 0; // 程序正常结束。
} // main 结束。复杂度： 有向图 DFS：O(V + E) 无向图并查集：接近 O(E) 空间复杂度：O(V + E) 或 O(V)
面试关键点： 有向图不能只用一个 visited，因为访问过的黑色节点不代表有环，只有遇到“当前递归栈里的灰色节点”才是环。无向图 DFS 判环时也要排除父节点，否则从子节点走回父节点会被误判。
求拓扑排序
标准答案： 拓扑排序是把一个 有向无环图 DAG 排成线性顺序，使得每条边 u -> v 都满足：u 一定排在 v 前面。
常见解法是 Kahn 入度队列算法：
1. 统计每个点的入度
2. 把所有入度为 0 的点放进队列
3. 每次弹出队头加入结果
4. 删除它的出边，也就是让后继节点入度减一
5. 如果后继入度变成 0，就加入队列
6. 最后如果结果数量小于节点数，说明图中有环C++ 实现：
c
#include <iostream> // 引入输入输出库，用来打印拓扑排序结果。
#include <queue> // 引入 queue，用来保存当前所有入度为 0 的节点。
#include <stdexcept> // 引入异常库，用来在图中有环或边非法时抛异常。
#include <utility> // 引入 pair，用来表示有向边。
#include <vector> // 引入 vector，用来保存邻接表、入度数组和结果数组。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有区域开始。
std::vector<int> TopologicalSort(int n, const std::vector<std::pair<int, int>>& edges) // 定义拓扑排序函数，n 是节点数量，edges 是有向边。
{ // 函数开始。
std::vector<std::vector<int>> graph(n); // 创建邻接表，graph[u] 保存 u 指向的所有节点。
std::vector<int> indegree(n, 0); // 创建入度数组，indegree[v] 表示有多少条边指向 v。
for (const auto& edge : edges) // 遍历所有有向边。
{ // for 开始。
int from = edge.first; // from 表示边的起点。
int to = edge.second; // to 表示边的终点。
if (from < 0 || from >= n || to < 0 || to >= n) // 判断边的端点是否合法。
{ // if 开始。
throw std::invalid_argument("edge node is out of range"); // 如果端点越界，就抛出异常。
} // if 结束。
graph[from].push_back(to); // 在邻接表中加入有向边 from -> to。
++indegree[to]; // 终点 to 的入度加一。
} // for 结束。
std::queue<int> zeroQueue; // 创建队列，保存当前所有入度为 0 的节点。
for (int node = 0; node < n; ++node) // 遍历所有节点。
{ // for 开始。
if (indegree[node] == 0) // 如果当前节点没有前置依赖。
{ // if 开始。
zeroQueue.push(node); // 把当前节点加入队列。
} // if 结束。
} // for 结束。
std::vector<int> order; // 创建结果数组，用来保存拓扑序。
while (!zeroQueue.empty()) // 只要还有入度为 0 的节点，就继续处理。
{ // while 开始。
int current = zeroQueue.front(); // 取出当前可以执行的节点。
zeroQueue.pop(); // 从队列中移除当前节点。
order.push_back(current); // 把当前节点加入拓扑排序结果。
for (int next : graph[current]) // 遍历当前节点指向的所有后继节点。
{ // for 开始。
--indegree[next]; // 删除 current -> next 这条边，所以 next 的入度减一。
if (indegree[next] == 0) // 如果 next 的所有前置依赖都已经处理完。
{ // if 开始。
zeroQueue.push(next); // 把 next 加入队列，等待后续处理。
} // if 结束。
} // for 结束。
} // while 结束。
if (static_cast<int>(order.size()) != n) // 如果没有输出全部节点。
{ // if 开始。
throw std::logic_error("graph has cycle"); // 说明图中有环，无法完成拓扑排序。
} // if 结束。
return order; // 返回拓扑排序结果。
} // 函数结束。
}; // 类结束。
int main() // 程序入口。
{ // main 开始。
int n = 6; // 定义节点数量，节点编号是 0 到 5。
std::vector<std::pair<int, int>> edges = {{5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}}; // 定义有向边集合。
Solution solution; // 创建解题对象。
std::vector<int> order = solution.TopologicalSort(n, edges); // 调用拓扑排序函数。
for (int node : order) // 遍历拓扑排序结果。
{ // for 开始。
std::cout << node << " "; // 输出当前节点。
} // for 结束。
return 0; // 程序正常结束。
} // main 结束。复杂度： 时间复杂度：O(V + E) 空间复杂度：O(V + E)
面试关键点： 拓扑排序结果不一定唯一，只要满足所有依赖顺序就是合法答案。 如果最后结果数量不足 n，说明有些节点永远等不到入度变成 0，也就是图中存在环。
求最短路径
标准答案： 求最短路径要先看边权：
无权图 / 所有边权相同：BFS
非负权图：Dijkstra
有负权边：Bellman-Ford
有负权环：不存在稳定最短路径面试里最常考的是 Dijkstra。它用 dist[x] 表示从起点到 x 的当前最短距离，每次从小根堆里取出距离最小的点，再用它去更新邻居，这个过程叫“松弛”。
c
#include <algorithm> // 引入 reverse，用来反转路径。
#include <functional> // 引入 greater，用来创建小根堆。
#include <iostream> // 引入输入输出库，用来打印结果。
#include <limits> // 引入 numeric_limits，用来表示无穷大距离。
#include <queue> // 引入 priority_queue，用来实现 Dijkstra 的小根堆。
#include <stdexcept> // 引入异常库，用来处理非法参数。
#include <utility> // 引入 pair，用来存储邻接边和堆节点。
#include <vector> // 引入 vector，用来存储图、距离、前驱和路径。
class DijkstraSolver // 定义 Dijkstra 最短路径求解类。
{ // 类开始。
private: // 私有区域开始。
struct Edge // 定义边结构。
{ // Edge 结构体开始。
int to; // to 表示边的终点。
int weight; // weight 表示边权。
}; // Edge 结构体结束。
std::vector<std::vector<Edge>> graph_; // graph_[u] 保存从 u 出发的所有边。
public: // 公有区域开始。
explicit DijkstraSolver(int nodeCount) // 构造函数，传入节点数量。
: graph_(nodeCount) // 初始化邻接表大小。
{ // 构造函数开始。
} // 构造函数结束。
void AddEdge(int from, int to, int weight) // 添加一条有向边。
{ // AddEdge 函数开始。
if (from < 0 || from >= static_cast<int>(graph_.size()) || to < 0 || to >= static_cast<int>(graph_.size())) // 检查边的端点是否合法。
{ // if 开始。
throw std::out_of_range("node index is out of range"); // 如果端点越界，抛出异常。
} // if 结束。
if (weight < 0) // 检查边权是否为负数。
{ // if 开始。
throw std::invalid_argument("Dijkstra does not support negative weight"); // Dijkstra 不支持负权边。
} // if 结束。
graph_[from].push_back(Edge{to, weight}); // 把边 from -> to 加入邻接表。
} // AddEdge 函数结束。
std::vector<int> ShortestPath(int source, int target) // 求 source 到 target 的最短路径。
{ // ShortestPath 函数开始。
int n = static_cast<int>(graph_.size()); // 获取图中的节点数量。
int inf = std::numeric_limits<int>::max() / 4; // 定义一个足够大的值表示无穷远。
std::vector<int> dist(n, inf); // dist[x] 表示从 source 到 x 的当前最短距离。
std::vector<int> previous(n, -1); // previous[x] 表示最短路径上 x 的前驱节点。
using HeapNode = std::pair<int, int>; // HeapNode 的 first 是距离，second 是节点编号。
std::priority_queue<HeapNode, std::vector<HeapNode>, std::greater<HeapNode>> minHeap; // 创建小根堆，优先弹出距离最小的节点。
dist[source] = 0; // 起点到自己的距离是 0。
minHeap.push({0, source}); // 把起点加入小根堆。
while (!minHeap.empty()) // 只要堆不为空，就继续处理。
{ // while 开始。
HeapNode current = minHeap.top(); // 取出当前距离最小的堆节点。
minHeap.pop(); // 从堆中移除这个节点。
int currentDistance = current.first; // 取出当前堆节点记录的距离。
int currentNode = current.second; // 取出当前堆节点记录的节点编号。
if (currentDistance != dist[currentNode]) // 如果这是过期的旧距离。
{ // if 开始。
continue; // 跳过旧数据，避免重复处理。
} // if 结束。
if (currentNode == target) // 如果已经取出了目标点。
{ // if 开始。
break; // 在非负权图中，此时目标距离已经确定。
} // if 结束。
for (const Edge& edge : graph_[currentNode]) // 遍历当前节点的所有邻接边。
{ // for 开始。
int nextNode = edge.to; // 获取邻居节点。
int newDistance = dist[currentNode] + edge.weight; // 计算经过 currentNode 到达 nextNode 的新距离。
if (newDistance < dist[nextNode]) // 如果新路径更短。
{ // if 开始。
dist[nextNode] = newDistance; // 更新 nextNode 的最短距离。
previous[nextNode] = currentNode; // 记录 nextNode 的前驱节点。
minHeap.push({newDistance, nextNode}); // 把新的距离状态放入小根堆。
} // if 结束。
} // for 结束。
} // while 结束。
if (dist[target] == inf) // 如果目标点仍然是无穷远。
{ // if 开始。
return {}; // 返回空路径，表示不可达。
} // if 结束。
std::vector<int> path; // 创建路径数组。
for (int node = target; node != -1; node = previous[node]) // 从目标点沿前驱链往回走。
{ // for 开始。
path.push_back(node); // 把当前节点加入路径。
} // for 结束。
std::reverse(path.begin(), path.end()); // 反转路径，使其从 source 到 target。
return path; // 返回最终最短路径。
} // ShortestPath 函数结束。
}; // DijkstraSolver 类结束。
int main() // 程序入口。
{ // main 开始。
DijkstraSolver solver(5); // 创建 5 个节点的图，节点 0 到 4 分别表示 A 到 E。
solver.AddEdge(0, 1, 2); // 添加边 A -> B，权重 2。
solver.AddEdge(0, 2, 5); // 添加边 A -> C，权重 5。
solver.AddEdge(1, 3, 3); // 添加边 B -> D，权重 3。
solver.AddEdge(2, 3, 2); // 添加边 C -> D，权重 2。
solver.AddEdge(1, 4, 10); // 添加边 B -> E，权重 10。
solver.AddEdge(3, 4, 1); // 添加边 D -> E，权重 1。
std::vector<int> path = solver.ShortestPath(0, 4); // 求 A 到 E 的最短路径。
for (int node : path) // 遍历路径中的每个节点。
{ // for 开始。
std::cout << node << " "; // 输出节点编号。
} // for 结束。
return 0; // 程序正常结束。
} // main 结束。复杂度： 邻接表 + 小根堆实现的 Dijkstra： 时间复杂度：O((V + E) log V) 空间复杂度：O(V + E)
面试关键点： Dijkstra 不能处理负权边。小根堆里可能存在旧距离，所以弹出时要判断 currentDistance != dist[currentNode]，旧数据直接跳过。
求最小生成树
标准答案： 最小生成树 MST 是在 无向连通带权图 中，选出 n - 1 条边，把所有点连起来，并且让边权总和最小。
常见算法有两个：
Kruskal：按边权从小到大选边，用并查集判断是否成环
Prim：从一个点开始扩展，每次选连接外部点的最小边面试手写更常用 Kruskal。
c
#include <algorithm> // 引入 sort，用来按边权排序。
#include <iostream> // 引入输入输出库，用来打印结果。
#include <numeric> // 引入 iota，用来初始化并查集 parent。
#include <stdexcept> // 引入异常库，用来处理图不连通。
#include <vector> // 引入 vector，用来保存边、并查集数组和结果边。
struct Edge // 定义边结构。
{ // Edge 结构体开始。
int from; // from 表示边的一个端点。
int to; // to 表示边的另一个端点。
int weight; // weight 表示边权。
}; // Edge 结构体结束。
class UnionFind // 定义并查集类。
{ // UnionFind 类开始。
private: // 私有区域开始。
std::vector<int> parent_; // parent_[x] 表示 x 的父节点。
std::vector<int> size_; // size_[x] 表示以 x 为根的集合大小。
public: // 公有区域开始。
explicit UnionFind(int n) // 构造函数，初始化 n 个独立集合。
: parent_(n) // 创建 parent_ 数组。
, size_(n, 1) // 创建 size_ 数组，每个集合初始大小为 1。
{ // 构造函数开始。
std::iota(parent_.begin(), parent_.end(), 0); // 初始化 parent_[i] = i。
} // 构造函数结束。
int Find(int x) // 查找 x 所在集合的根。
{ // Find 函数开始。
if (parent_[x] != x) // 如果 x 不是根节点。
{ // if 开始。
parent_[x] = Find(parent_[x]); // 路径压缩，把 x 直接挂到根节点。
} // if 结束。
return parent_[x]; // 返回 x 的根节点。
} // Find 函数结束。
bool Unite(int a, int b) // 合并 a 和 b 所在集合。
{ // Unite 函数开始。
int rootA = Find(a); // 找到 a 的根节点。
int rootB = Find(b); // 找到 b 的根节点。
if (rootA == rootB) // 如果两个点已经连通。
{ // if 开始。
return false; // 不能合并，否则会成环。
} // if 结束。
if (size_[rootA] < size_[rootB]) // 如果 A 集合比 B 集合小。
{ // if 开始。
std::swap(rootA, rootB); // 交换根，让 rootA 表示更大的集合。
} // if 结束。
parent_[rootB] = rootA; // 把小集合挂到大集合下面。
size_[rootA] += size_[rootB]; // 更新合并后的集合大小。
return true; // 合并成功。
} // Unite 函数结束。
}; // UnionFind 类结束。
class Solution // 定义解题类。
{ // Solution 类开始。
public: // 公有区域开始。
std::pair<int, std::vector<Edge>> Kruskal(int n, std::vector<Edge> edges) // 返回最小生成树总权重和选中的边。
{ // Kruskal 函数开始。
std::sort(edges.begin(), edges.end(), [](const Edge& left, const Edge& right) // 按边权从小到大排序。
{ // lambda 开始。
return left.weight < right.weight; // 边权小的排在前面。
}); // sort 调用结束。
UnionFind uf(n); // 创建并查集，用来判断选边是否会成环。
int totalWeight = 0; // totalWeight 记录最小生成树总权重。
std::vector<Edge> mstEdges; // mstEdges 记录被选入最小生成树的边。
for (const Edge& edge : edges) // 按边权从小到大遍历每条边。
{ // for 开始。
if (uf.Unite(edge.from, edge.to)) // 如果这条边连接的是两个不同集合。
{ // if 开始。
mstEdges.push_back(edge); // 把这条边加入最小生成树。
totalWeight += edge.weight; // 累加边权。
if (static_cast<int>(mstEdges.size()) == n - 1) // 如果已经选够 n - 1 条边。
{ // if 开始。
break; // 最小生成树已经完成。
} // if 结束。
} // if 结束。
} // for 结束。
if (static_cast<int>(mstEdges.size()) != n - 1) // 如果最终没有选够 n - 1 条边。
{ // if 开始。
throw std::logic_error("graph is not connected"); // 图不连通，无法形成最小生成树。
} // if 结束。
return {totalWeight, mstEdges}; // 返回总权重和最小生成树边集。
} // Kruskal 函数结束。
}; // Solution 类结束。
int main() // 程序入口。
{ // main 开始。
int n = 5; // 定义顶点数量，0 到 4 分别表示 A 到 E。
std::vector<Edge> edges = {{0, 1, 1}, {1, 3, 2}, {1, 2, 3}, {0, 2, 4}, {2, 4, 5}, {3, 4, 6}, {1, 4, 7}}; // 定义无向图边集。
Solution solution; // 创建解题对象。
auto result = solution.Kruskal(n, edges); // 调用 Kruskal 求最小生成树。
std::cout << result.first << std::endl; // 输出最小生成树总权重，结果是 11。
for (const Edge& edge : result.second) // 遍历最小生成树中的每条边。
{ // for 开始。
std::cout << edge.from << "-" << edge.to << ":" << edge.weight << std::endl; // 输出边的两个端点和权重。
} // for 结束。
return 0; // 程序正常结束。
} // main 结束。复杂度： Kruskal 的主要成本是排序：O(E log E) 并查集合并查询接近 O(1)。
面试关键点： 最小生成树不是最短路径。最短路径关心“两点之间最短”，最小生成树关心“连通所有点的总成本最小”。如果图不连通，得到的不是生成树，而是最小生成森林。
求岛屿最大面积
标准答案： 岛屿最大面积就是在 0/1 网格里，找到最大的一片四方向连通陆地。1 是陆地，0 是水，面积就是这一片陆地包含的格子数量。
核心思路： 扫描整个网格，遇到 1 就从这里开始 DFS，把这片岛屿全部走完，并统计面积。访问过的陆地直接改成 0，表示“沉岛”，避免重复统计。
c
#include <algorithm> // 引入 std::max，用来更新最大岛屿面积。
#include <iostream> // 引入输入输出库，用来打印结果。
#include <vector> // 引入 vector，用来存储二维网格。
class Solution // 定义解题类。
{ // 类开始。
private: // 私有区域开始。
int rows_ = 0; // rows_ 保存网格行数。
int cols_ = 0; // cols_ 保存网格列数。
int Dfs(std::vector<std::vector<int>>& grid, int row, int col) // 从 grid[row][col] 开始 DFS，返回当前岛屿面积。
{ // Dfs 函数开始。
if (row < 0 || row >= rows_ || col < 0 || col >= cols_) // 如果当前位置越界。
{ // if 开始。
return 0; // 越界不算陆地面积。
} // if 结束。
if (grid[row][col] == 0) // 如果当前位置是水，或者已经访问过。
{ // if 开始。
return 0; // 水不贡献面积。
} // if 结束。
grid[row][col] = 0; // 把当前陆地沉成水，表示已经访问过。
int area = 1; // 当前格子本身贡献 1 个面积。
area += Dfs(grid, row - 1, col); // 向上搜索相邻陆地。
area += Dfs(grid, row + 1, col); // 向下搜索相邻陆地。
area += Dfs(grid, row, col - 1); // 向左搜索相邻陆地。
area += Dfs(grid, row, col + 1); // 向右搜索相邻陆地。
return area; // 返回这一整片岛屿的面积。
} // Dfs 函数结束。
public: // 公有区域开始。
int MaxAreaOfIsland(std::vector<std::vector<int>>& grid) // 求网格中的最大岛屿面积。
{ // MaxAreaOfIsland 函数开始。
if (grid.empty() || grid[0].empty()) // 如果网格为空。
{ // if 开始。
return 0; // 空网格没有岛屿。
} // if 结束。
rows_ = static_cast<int>(grid.size()); // 记录网格行数。
cols_ = static_cast<int>(grid[0].size()); // 记录网格列数。
int answer = 0; // answer 保存当前最大岛屿面积。
for (int row = 0; row < rows_; ++row) // 遍历每一行。
{ // 外层 for 开始。
for (int col = 0; col < cols_; ++col) // 遍历每一列。
{ // 内层 for 开始。
if (grid[row][col] == 1) // 如果当前位置是未访问陆地。
{ // if 开始。
answer = std::max(answer, Dfs(grid, row, col)); // 计算这一片岛屿面积，并更新最大值。
} // if 结束。
} // 内层 for 结束。
} // 外层 for 结束。
return answer; // 返回最大岛屿面积。
} // MaxAreaOfIsland 函数结束。
}; // 类结束。
int main() // 程序入口。
{ // main 开始。
std::vector<std::vector<int>> grid = {{0, 1, 1, 0, 1}, {0, 1, 1, 1, 0}, {1, 0, 1, 0, 0}, {1, 1, 0, 0, 1}}; // 准备测试网格。
Solution solution; // 创建解题对象。
std::cout << solution.MaxAreaOfIsland(grid) << std::endl; // 输出最大岛屿面积，结果是 6。
return 0; // 程序正常结束。
} // main 结束。复杂度： 时间复杂度：O(mn)，每个格子最多访问一次。 空间复杂度：递归栈最坏 O(mn)。如果地图非常大，可以改成显式栈或 BFS 队列，避免递归栈过深。
面试关键点： 四方向连通只算上下左右，斜对角不算。题目问的是“最大面积”，不是“岛屿数量”。
求矩阵最短路径
标准答案： 矩阵最短路径一般用 BFS。因为矩阵里每走一格代价相同，BFS 是按“距离一层层扩展”的，所以第一次到达终点时，步数一定最少。
这里假设：
c
0 表示可走
1 表示障碍
只能上下左右四方向移动
从左上角走到右下角
#include <array> // 引入 array，用来保存四个移动方向。
#include <iostream> // 引入输入输出库，用来打印结果。
#include <queue> // 引入 queue，用来做 BFS 队列。
#include <utility> // 引入 pair，用来保存格子坐标。
#include <vector> // 引入 vector，用来存储矩阵和距离数组。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有区域开始。
int ShortestPath(std::vector<std::vector<int>>& grid) // 定义函数，返回左上角到右下角的最短步数。
{ // 函数开始。
if (grid.empty() || grid[0].empty()) // 如果矩阵为空。
{ // if 开始。
return -1; // 空矩阵无法到达终点。
} // if 结束。
int rows = static_cast<int>(grid.size()); // 记录矩阵行数。
int cols = static_cast<int>(grid[0].size()); // 记录矩阵列数。
if (grid[0][0] == 1 || grid[rows - 1][cols - 1] == 1) // 如果起点或终点是障碍。
{ // if 开始。
return -1; // 起点或终点不能走，直接返回不可达。
} // if 结束。
std::vector<std::vector<int>> dist(rows, std::vector<int>(cols, -1)); // dist[r][c] 表示起点到该格子的最短步数，-1 表示未访问。
std::queue<std::pair<int, int>> queue; // 创建 BFS 队列，保存待扩展的格子坐标。
std::array<std::pair<int, int>, 4> dirs = {{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}}; // 定义上下左右四个方向。
dist[0][0] = 0; // 起点到自己的步数是 0。
queue.push({0, 0}); // 把起点加入队列。
while (!queue.empty()) // 只要队列不为空，就继续 BFS。
{ // while 开始。
std::pair<int, int> current = queue.front(); // 取出当前队头格子。
queue.pop(); // 弹出当前格子。
int row = current.first; // 取出当前格子的行号。
int col = current.second; // 取出当前格子的列号。
if (row == rows - 1 && col == cols - 1) // 如果当前格子就是终点。
{ // if 开始。
return dist[row][col]; // 第一次到达终点，步数就是最短步数。
} // if 结束。
for (const auto& dir : dirs) // 遍历四个移动方向。
{ // for 开始。
int nextRow = row + dir.first; // 计算下一格行号。
int nextCol = col + dir.second; // 计算下一格列号。
if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols) // 如果下一格越界。
{ // if 开始。
continue; // 越界格子不能走。
} // if 结束。
if (grid[nextRow][nextCol] == 1) // 如果下一格是障碍。
{ // if 开始。
continue; // 障碍格子不能走。
} // if 结束。
if (dist[nextRow][nextCol] != -1) // 如果下一格已经访问过。
{ // if 开始。
continue; // BFS 第一次访问就是最短距离，不需要重复入队。
} // if 结束。
dist[nextRow][nextCol] = dist[row][col] + 1; // 更新下一格的最短步数。
queue.push({nextRow, nextCol}); // 把下一格加入队列，等待继续扩展。
} // for 结束。
} // while 结束。
return -1; // 队列空了还没到终点，说明不可达。
} // 函数结束。
}; // 类结束。复杂度： 时间复杂度：O(mn)，每个格子最多访问一次。 空间复杂度：O(mn)，用于 dist 和 BFS 队列。
面试关键点： 如果每个格子移动代价一样，用 BFS；如果不同格子的代价不同，就要用 Dijkstra；如果要更像游戏寻路并且有启发函数，可以用 A*。
求机器人运动范围
标准答案： 机器人运动范围是求“从 (0,0) 出发，最多能到达多少个格子”。格子能不能进入，取决于：
c
digitSum(row) + digitSum(col) <= k注意：这题不是最短路径，也不是统计所有“数位和合法”的格子，而是统计 从起点真正连通可达 的格子。
C++ 实现：
c
#include <array> // 引入 array，用来保存四个移动方向。
#include <iostream> // 引入输入输出库，用来打印结果。
#include <queue> // 引入 queue，用来做 BFS。
#include <utility> // 引入 pair，用来保存格子坐标。
#include <vector> // 引入 vector，用来保存 visited 数组。
class Solution // 定义解题类。
{ // 类开始。
private: // 私有区域开始。
int DigitSum(int value) const // 计算一个整数的数位和。
{ // DigitSum 函数开始。
int sum = 0; // sum 用来累加每一位数字。
while (value > 0) // 当 value 还有数字位时继续循环。
{ // while 开始。
sum += value % 10; // 取出个位数字并累加。
value /= 10; // 去掉当前个位数字。
} // while 结束。
return sum; // 返回数位和。
} // DigitSum 函数结束。
bool CanEnter(int row, int col, int k) const // 判断机器人能不能进入某个格子。
{ // CanEnter 函数开始。
return DigitSum(row) + DigitSum(col) <= k; // 行号数位和加列号数位和不超过 k 才能进入。
} // CanEnter 函数结束。
public: // 公有区域开始。
int MovingCount(int m, int n, int k) // 计算机器人在 m 行 n 列网格中能到达多少格。
{ // MovingCount 函数开始。
if (m <= 0 || n <= 0 || k < 0) // 如果网格尺寸非法或者 k 为负数。
{ // if 开始。
return 0; // 没有任何格子可达。
} // if 结束。
std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false)); // visited[row][col] 表示格子是否已经访问过。
std::queue<std::pair<int, int>> pending; // pending 是 BFS 队列，保存待扩展格子。
std::array<std::pair<int, int>, 4> dirs = {{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}}; // 定义上下左右四个方向。
int answer = 0; // answer 记录最终可达格子数量。
visited[0][0] = true; // 起点标记为已访问。
pending.push({0, 0}); // 把起点加入 BFS 队列。
while (!pending.empty()) // 队列不为空时继续扩展。
{ // while 开始。
std::pair<int, int> current = pending.front(); // 取出当前队头格子。
pending.pop(); // 从队列中移除当前格子。
++answer; // 当前格子可达，所以答案加一。
for (const auto& dir : dirs) // 遍历四个方向。
{ // for 开始。
int nextRow = current.first + dir.first; // 计算下一格行号。
int nextCol = current.second + dir.second; // 计算下一格列号。
if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n) // 如果下一格越界。
{ // if 开始。
continue; // 越界格子不能进入。
} // if 结束。
if (visited[nextRow][nextCol]) // 如果下一格已经访问过。
{ // if 开始。
continue; // 已访问格子不能重复统计。
} // if 结束。
if (!CanEnter(nextRow, nextCol, k)) // 如果下一格不满足数位和限制。
{ // if 开始。
continue; // 不合法格子不能进入。
} // if 结束。
visited[nextRow][nextCol] = true; // 标记下一格已经访问。
pending.push({nextRow, nextCol}); // 把下一格加入 BFS 队列。
} // for 结束。
} // while 结束。
return answer; // 返回机器人能到达的格子数量。
} // MovingCount 函数结束。
}; // 类结束。
int main() // 程序入口。
{ // main 开始。
Solution solution; // 创建解题对象。
std::cout << solution.MovingCount(4, 5, 3) << std::endl; // 输出示例结果，答案是 10。
return 0; // 程序正常结束。
} // main 结束。复杂度： 时间复杂度：O(mn)，每个格子最多访问一次。 空间复杂度：O(mn)，主要是 visited 和 BFS 队列。
面试关键点： 数位和不是 row + col，比如 (12, 3) 的限制值是 1 + 2 + 3 = 6。而且格子满足限制不代表一定可达，必须能从 (0,0) 连通走过去。
求单词搜索
单词搜索一句话定义
在一个二维字符矩阵里，判断能不能从某个格子出发，按“上下左右”走出目标单词，并且同一条路径里同一个格子不能重复使用。
核心思路
用 DFS + 回溯。从每个格子当起点开始搜，如果当前格子等于 word[index]，就继续去上下左右找 word[index + 1]。为了防止同一个格子重复使用，进入递归时临时把当前格子标记成 #，递归结束后再恢复原字符。
复杂度：设矩阵大小是 m * n，单词长度是 L。时间复杂度常写 O(mn * 3^L)，因为第一步最多 4 个方向，后面通常不能马上走回头路；面试里写保守一点 O(mn * 4^L) 也能接受。空间复杂度是递归深度 O(L)。
c
#include <iostream> // 引入输入输出库，用来在 main 中打印结果。
#include <string> // 引入 string，用来保存目标单词。
#include <vector> // 引入 vector，用来保存二维字符矩阵。
class Solution // 定义解题类，面试和 LeetCode 常用这种写法。
{ // 类的开始。
private: // 私有区域，只给类内部使用。
int rows_ = 0; // 保存矩阵的行数。
int cols_ = 0; // 保存矩阵的列数。
bool Dfs(std::vector<std::vector<char>>& board, const std::string& word, int index, int row, int col) // 从 row、col 开始匹配 word[index]。
{ // DFS 函数开始。
if (index == static_cast<int>(word.size())) // 如果 index 已经走到单词末尾，说明所有字符都匹配成功。
{ // if 代码块开始。
return true; // 返回 true，表示找到了完整路径。
} // if 代码块结束。
if (row < 0 || row >= rows_ || col < 0 || col >= cols_) // 如果当前位置越界，就不能继续搜索。
{ // if 代码块开始。
return false; // 返回 false，表示这条路失败。
} // if 代码块结束。
if (board[row][col] != word[index]) // 如果当前格子的字符不等于要匹配的字符。
{ // if 代码块开始。
return false; // 返回 false，表示当前路径不匹配。
} // if 代码块结束。
char oldChar = board[row][col]; // 先保存当前字符，方便回溯时恢复。
board[row][col] = '#'; // 临时标记当前格子已经访问过，防止本路径重复使用。
bool found = false; // 记录四个方向里是否有任意一个方向成功。
found = found || Dfs(board, word, index + 1, row - 1, col); // 向上搜索下一个字符。
found = found || Dfs(board, word, index + 1, row + 1, col); // 向下搜索下一个字符。
found = found || Dfs(board, word, index + 1, row, col - 1); // 向左搜索下一个字符。
found = found || Dfs(board, word, index + 1, row, col + 1); // 向右搜索下一个字符。
board[row][col] = oldChar; // 回溯恢复现场，让其他路径还能使用这个格子。
return found; // 返回四个方向的搜索结果。
} // DFS 函数结束。
public: // 公有区域，外部可以调用。
bool Exist(std::vector<std::vector<char>>& board, const std::string& word) // 判断矩阵中是否存在目标单词路径。
{ // Exist 函数开始。
if (word.empty()) // 如果单词为空。
{ // if 代码块开始。
return true; // 空单词默认认为可以匹配成功。
} // if 代码块结束。
if (board.empty() || board[0].empty()) // 如果矩阵为空。
{ // if 代码块开始。
return false; // 矩阵为空时无法匹配非空单词。
} // if 代码块结束。
rows_ = static_cast<int>(board.size()); // 记录矩阵行数。
cols_ = static_cast<int>(board[0].size()); // 记录矩阵列数。
for (int row = 0; row < rows_; ++row) // 枚举每一行。
{ // 外层循环开始。
for (int col = 0; col < cols_; ++col) // 枚举每一列。
{ // 内层循环开始。
if (Dfs(board, word, 0, row, col)) // 尝试从当前格子开始匹配 word[0]。
{ // if 代码块开始。
return true; // 只要有一个起点成功，就返回 true。
} // if 代码块结束。
} // 内层循环结束。
} // 外层循环结束。
return false; // 所有起点都失败，说明不存在这条路径。
} // Exist 函数结束。
}; // Solution 类结束。面试关键句
这题不是简单遍历，而是“路径搜索”。DFS 负责往下试，回溯负责恢复现场；如果不恢复，被标记过的格子会影响其他起点或其他路径，导致本来存在的答案被误判成不存在。
求 N 皇后
标准答案
N 皇后用 回溯 做。核心是“一行一行放皇后”，每一行枚举列，如果当前位置不会和之前的皇后产生列冲突、主对角线冲突、副对角线冲突，就放下去递归下一行；递归结束后再撤销，继续尝试别的位置。
底层思路
因为我们每次只处理一行，所以“同行冲突”天然不存在。剩下只需要判断三个东西：
usedCol[col]：这一列是否已经有皇后。 usedDiag1[row - col + n - 1]：主对角线是否已有皇后。 usedDiag2[row + col]：副对角线是否已有皇后。
时间复杂度粗略是 O(n!)，空间复杂度不算答案是 O(n^2)，因为要保存当前棋盘；递归栈和标记数组是 O(n) 级别。
c
#include <string> // 引入 string，用来表示棋盘中的每一行字符串。
#include <vector> // 引入 vector，用来保存棋盘、标记数组和最终答案。
class Solution // 定义 N 皇后解题类。
{ // 类开始。
private: // 私有成员区域。
int n_ = 0; // 保存棋盘大小 n。
std::vector<std::vector<std::string>> answers_; // 保存所有合法棋盘。
std::vector<std::string> board_; // 保存当前正在尝试的棋盘。
std::vector<int> usedCol_; // 标记某一列是否已经放过皇后。
std::vector<int> usedDiag1_; // 标记主对角线是否已经放过皇后。
std::vector<int> usedDiag2_; // 标记副对角线是否已经放过皇后。
void Dfs(int row) // 从第 row 行开始尝试放皇后。
{ // Dfs 函数开始。
if (row == n_) // 如果 row 等于 n，说明 0 到 n - 1 行都已经放好了。
{ // if 代码块开始。
answers_.push_back(board_); // 把当前棋盘加入答案。
return; // 返回上一层继续搜索其他可能。
} // if 代码块结束。
for (int col = 0; col < n_; ++col) // 枚举当前行的每一列。
{ // for 循环开始。
int diag1 = row - col + n_ - 1; // 计算主对角线编号，并加 n - 1 避免负数下标。
int diag2 = row + col; // 计算副对角线编号。
if (usedCol_[col] || usedDiag1_[diag1] || usedDiag2_[diag2]) // 如果列、主对角线、副对角线任意一个冲突。
{ // if 代码块开始。
continue; // 跳过这个位置，尝试下一列。
} // if 代码块结束。
board_[row][col] = 'Q'; // 在当前位置放置皇后。
usedCol_[col] = 1; // 标记这一列已经被占用。
usedDiag1_[diag1] = 1; // 标记这条主对角线已经被占用。
usedDiag2_[diag2] = 1; // 标记这条副对角线已经被占用。
Dfs(row + 1); // 递归处理下一行。
usedDiag2_[diag2] = 0; // 回溯时撤销副对角线标记。
usedDiag1_[diag1] = 0; // 回溯时撤销主对角线标记。
usedCol_[col] = 0; // 回溯时撤销列标记。
board_[row][col] = '.'; // 回溯时把皇后位置恢复为空位。
} // for 循环结束。
} // Dfs 函数结束。
public: // 公有成员区域。
std::vector<std::vector<std::string>> SolveNQueens(int n) // 求 n 皇后的所有合法解。
{ // SolveNQueens 函数开始。
answers_.clear(); // 清空历史答案，防止复用对象时残留旧结果。
if (n <= 0) // 如果 n 非法。
{ // if 代码块开始。
return answers_; // 返回空答案。
} // if 代码块结束。
n_ = n; // 保存棋盘大小。
board_.assign(n_, std::string(n_, '.')); // 初始化 n 行 n 列的空棋盘。
usedCol_.assign(n_, 0); // 初始化列标记数组。
usedDiag1_.assign(2 * n_ - 1, 0); // 初始化主对角线标记数组。
usedDiag2_.assign(2 * n_ - 1, 0); // 初始化副对角线标记数组。
Dfs(0); // 从第 0 行开始回溯搜索。
return answers_; // 返回所有合法棋盘。
} // SolveNQueens 函数结束。
}; // Solution 类结束。面试关键句
N 皇后的关键不是“怎么放皇后”，而是“如何快速判断当前位置能不能放”。用 列 + 两条对角线 三个标记数组，就能把冲突判断从扫描棋盘优化成 O(1)。
求括号生成
标准答案
括号生成用 回溯。每一步有两个选择：放左括号 ( 或放右括号 )，但不能乱放。左括号数量小于 n 时才能继续放左括号；右括号数量小于左括号数量时才能放右括号。这样生成的每个前缀都是合法的，不需要最后再过滤。
核心思路
维护三个状态：path 表示当前生成的字符串，openCount 表示已经放了几个左括号，closeCount 表示已经放了几个右括号。
当 path.size() == 2 * n，说明一个完整答案生成完了。复杂度和答案数量有关，答案数量是第 n 个卡特兰数，通常写成 O(Cn * n)，其中 n 是括号对数，Cn 是合法括号组合数量。
c
#include <string> // 引入 string，用来保存当前括号字符串。
#include <vector> // 引入 vector，用来保存所有生成结果。
class Solution // 定义解题类。
{ // 类开始。
private: // 私有成员区域。
std::vector<std::string> answers_; // 保存所有合法括号组合。
void Dfs(int n, int openCount, int closeCount, std::string& path) // 回溯函数，openCount 是左括号数量，closeCount 是右括号数量。
{ // Dfs 函数开始。
if (static_cast<int>(path.size()) == 2 * n) // 如果当前字符串长度已经等于 2n。
{ // if 代码块开始。
answers_.push_back(path); // 当前 path 一定合法，加入答案。
return; // 返回上一层继续搜索其他组合。
} // if 代码块结束。
if (openCount < n) // 如果左括号还没有用完。
{ // if 代码块开始。
path.push_back('('); // 选择放一个左括号。
Dfs(n, openCount + 1, closeCount, path); // 递归搜索下一位。
path.pop_back(); // 回溯，撤销刚才放入的左括号。
} // if 代码块结束。
if (closeCount < openCount) // 如果右括号数量小于左括号数量，说明可以放右括号。
{ // if 代码块开始。
path.push_back(')'); // 选择放一个右括号。
Dfs(n, openCount, closeCount + 1, path); // 递归搜索下一位。
path.pop_back(); // 回溯，撤销刚才放入的右括号。
} // if 代码块结束。
} // Dfs 函数结束。
public: // 公有成员区域。
std::vector<std::string> GenerateParenthesis(int n) // 生成 n 对括号的所有合法组合。
{ // GenerateParenthesis 函数开始。
answers_.clear(); // 清空历史答案，避免复用对象时残留旧结果。
std::string path; // 创建当前路径字符串。
Dfs(n, 0, 0, path); // 从 0 个左括号、0 个右括号开始搜索。
return answers_; // 返回所有合法括号组合。
} // GenerateParenthesis 函数结束。
}; // Solution 类结束。面试关键句
这题的重点是“合法前缀”。只要保证任意时刻 closeCount <= openCount，就不会生成 )(、())( 这种非法前缀；再加上 openCount <= n，最终长度到 2n 时就一定是合法答案。
求全排列去重
标准答案
全排列去重用 排序 + 回溯 + 同层剪枝。先把数组排序，让相同数字挨在一起；然后 DFS 枚举每一位选哪个数字，用 used[i] 表示下标 i 是否已经被当前排列使用过。遇到重复数字时，如果前一个相同数字还没被使用，就跳过当前数字，避免同一层生成重复分支。
核心剪枝
关键判断是：
c
i > 0 && nums[i] == nums[i - 1] && !used[i - 1]意思是：当前数字和前一个数字相同，并且前一个相同数字在当前层还没有被选过，那么当前数字也不能作为这一层的新起点，否则会产生重复排列。
c
#include <algorithm> // 引入 sort，用来先对 nums 排序。
#include <vector> // 引入 vector，用来保存数组、路径和答案。
class Solution // 定义全排列去重解题类。
{ // 类开始。
private: // 私有成员区域。
std::vector<std::vector<int>> answers_; // 保存所有不重复的排列结果。
std::vector<int> path_; // 保存当前正在构造的排列。
std::vector<int> used_; // 标记每个下标的数字是否已经被当前 path 使用。
void Dfs(const std::vector<int>& nums) // 回溯函数，用 nums 构造排列。
{ // Dfs 函数开始。
if (path_.size() == nums.size()) // 如果当前 path 长度等于 nums 长度，说明一个排列完成。
{ // if 代码块开始。
answers_.push_back(path_); // 把当前排列加入答案。
return; // 返回上一层继续搜索其他排列。
} // if 代码块结束。
for (int i = 0; i < static_cast<int>(nums.size()); ++i) // 枚举当前位置可以选择的每个下标。
{ // for 循环开始。
if (used_[i] == 1) // 如果这个下标已经在当前排列里用过。
{ // if 代码块开始。
continue; // 跳过这个下标，避免同一个元素重复使用。
} // if 代码块结束。
if (i > 0 && nums[i] == nums[i - 1] && used_[i - 1] == 0) // 如果当前数字和前一个数字相同，并且前一个相同数字在本层还没用过。
{ // if 代码块开始。
continue; // 跳过当前数字，避免同一层重复选择相同数字。
} // if 代码块结束。
used_[i] = 1; // 标记当前下标已经被使用。
path_.push_back(nums[i]); // 把当前数字加入排列路径。
Dfs(nums); // 递归选择下一个位置。
path_.pop_back(); // 回溯，撤销刚才加入的数字。
used_[i] = 0; // 回溯，恢复当前下标为未使用。
} // for 循环结束。
} // Dfs 函数结束。
public: // 公有成员区域。
std::vector<std::vector<int>> PermuteUnique(std::vector<int>& nums) // 返回 nums 的所有不重复全排列。
{ // PermuteUnique 函数开始。
answers_.clear(); // 清空历史答案，避免对象复用时残留旧数据。
path_.clear(); // 清空当前路径。
std::sort(nums.begin(), nums.end()); // 先排序，让相同数字相邻，方便去重。
used_.assign(nums.size(), 0); // 初始化 used 数组，所有下标都未使用。
Dfs(nums); // 从空路径开始回溯搜索。
return answers_; // 返回所有不重复排列。
} // PermuteUnique 函数结束。
}; // Solution 类结束。复杂度
时间复杂度最坏仍然接近 O(n * n!)，因为最多有 n! 个排列，每个排列长度是 n。空间复杂度不算答案是 O(n)，主要是递归深度、path 和 used。
面试关键句
这题的去重不是“看到重复数字就永远跳过”，而是“同一层不能重复选择相同数字”。所以要排序，再用 !used[i - 1] 判断前一个相同数字是否已经作为当前层的选择被处理过。
求组合总和去重
标准答案
组合总和去重一般指 Combination Sum II：候选数组里可能有重复数字，每个数字只能使用一次，要求找出所有和为 target 的不重复组合。做法是 排序 + 回溯 + 同层去重。
核心思路
先排序，让重复数字相邻。DFS 时用 start 控制本层从哪里开始选，选中 candidates[i] 后，下一层从 i + 1 开始，因为每个下标只能用一次。
去重关键是：
c
i > start && candidates[i] == candidates[i - 1]意思是：同一层里，如果当前数字和前一个数字相同，就跳过当前数字，避免生成重复组合。注意必须是 i > start，不是简单的 i > 0，否则会误伤 [1,1,6] 这种合法组合。
c
#include <algorithm> // 引入 sort，用来对候选数组排序。
#include <vector> // 引入 vector，用来保存候选数组、路径和答案。
class Solution // 定义组合总和去重的解题类。
{ // 类开始。
private: // 私有成员区域。
std::vector<std::vector<int>> answers_; // 保存所有不重复的组合答案。
std::vector<int> path_; // 保存当前正在尝试的组合路径。
void Dfs(const std::vector<int>& candidates, int start, int remain) // 从 start 开始搜索，remain 表示还差多少凑到 target。
{ // Dfs 函数开始。
if (remain == 0) // 如果剩余目标为 0，说明当前 path 已经凑成 target。
{ // if 代码块开始。
answers_.push_back(path_); // 把当前组合加入答案。
return; // 返回上一层，继续搜索其他组合。
} // if 代码块结束。
for (int i = start; i < static_cast<int>(candidates.size()); ++i) // 从 start 开始枚举本层可以选择的数字。
{ // for 循环开始。
if (i > start && candidates[i] == candidates[i - 1]) // 如果同一层遇到重复数字。
{ // if 代码块开始。
continue; // 跳过当前数字，避免生成重复组合。
} // if 代码块结束。
if (candidates[i] > remain) // 如果当前数字已经大于剩余目标。
{ // if 代码块开始。
break; // 因为数组已排序，后面的数字更大，可以直接停止本层循环。
} // if 代码块结束。
path_.push_back(candidates[i]); // 选择当前数字，加入路径。
Dfs(candidates, i + 1, remain - candidates[i]); // 递归下一层，并且从 i + 1 开始，保证当前下标只用一次。
path_.pop_back(); // 回溯，撤销刚才选择的数字。
} // for 循环结束。
} // Dfs 函数结束。
public: // 公有成员区域。
std::vector<std::vector<int>> CombinationSum2(std::vector<int>& candidates, int target) // 求所有和为 target 的不重复组合。
{ // CombinationSum2 函数开始。
answers_.clear(); // 清空历史答案，避免对象复用时残留旧数据。
path_.clear(); // 清空当前路径。
std::sort(candidates.begin(), candidates.end()); // 先排序，让重复数字相邻，也方便提前剪枝。
Dfs(candidates, 0, target); // 从下标 0 开始搜索，初始剩余目标是 target。
return answers_; // 返回所有合法组合。
} // CombinationSum2 函数结束。
}; // Solution 类结束。复杂度
最坏情况下会接近遍历所有子集，时间复杂度是 O(2^n * n)，其中乘 n 是因为保存答案时要复制路径。空间复杂度不算答案是 O(n)，主要来自递归深度和当前路径。
面试关键句
这题最容易错在去重条件。组合去重去的是“同一层重复选择”，所以条件是 i > start && candidates[i] == candidates[i - 1]；而每个数只能用一次，所以递归下一层必须传 i + 1。
求子集去重
标准答案
子集去重一般指：输入数组里可能有重复数字，返回所有不重复子集。做法是 排序 + 回溯 + 同层去重。和组合总和不同，子集题里每进入一个递归状态，当前 path 就是一个答案，所以要先收集，再继续往后选。
核心思路
先排序，让重复数字相邻。DFS 时用 start 表示当前层从哪里开始选。去重条件是：
c
i > start && nums[i] == nums[i - 1]意思是：同一层里，如果当前数字和前一个数字相同，就跳过当前数字，避免生成重复子集。注意是 i > start，不是 i > 0，因为下一层允许继续选择重复数字的不同下标，比如 [2,2] 是合法子集。
c
#include <algorithm> // 引入 sort，用来对数组排序。
#include <vector> // 引入 vector，用来保存数组、路径和答案。
class Solution // 定义子集去重解题类。
{ // 类开始。
private: // 私有成员区域。
std::vector<std::vector<int>> answers_; // 保存所有不重复子集。
std::vector<int> path_; // 保存当前正在构造的子集。
void Dfs(const std::vector<int>& nums, int start) // 从 start 下标开始继续选择元素。
{ // Dfs 函数开始。
answers_.push_back(path_); // 当前 path 本身就是一个合法子集，先加入答案。
for (int i = start; i < static_cast<int>(nums.size()); ++i) // 枚举当前层可以选择的每个下标。
{ // for 循环开始。
if (i > start && nums[i] == nums[i - 1]) // 如果同一层遇到重复数字。
{ // if 代码块开始。
continue; // 跳过当前数字，避免生成重复子集。
} // if 代码块结束。
path_.push_back(nums[i]); // 选择当前数字，加入当前子集。
Dfs(nums, i + 1); // 递归下一层，从 i + 1 开始，保证每个下标最多用一次。
path_.pop_back(); // 回溯，撤销刚才选择的数字。
} // for 循环结束。
} // Dfs 函数结束。
public: // 公有成员区域。
std::vector<std::vector<int>> SubsetsWithDup(std::vector<int>& nums) // 返回所有不重复子集。
{ // SubsetsWithDup 函数开始。
answers_.clear(); // 清空历史答案，避免对象复用时残留旧数据。
path_.clear(); // 清空当前路径。
std::sort(nums.begin(), nums.end()); // 先排序，让重复数字相邻，方便同层去重。
Dfs(nums, 0); // 从下标 0 开始搜索。
return answers_; // 返回所有不重复子集。
} // SubsetsWithDup 函数结束。
}; // Solution 类结束。复杂度
时间复杂度是 O(n * 2^n)，因为最多有 2^n 个子集，复制每个子集最多需要 n。空间复杂度不算答案是 O(n)，主要是递归栈和当前路径。
面试关键句
子集去重的关键是“同层去重”。进入每个递归节点先收集 path，然后从 start 往后选；如果同一层遇到相同数字，只允许第一个相同数字进入分支。
求最长公共前缀
标准答案
最长公共前缀就是找一组字符串从开头开始都相同的最长部分。最直观的做法是 逐列扫描：以第一个字符串为基准，从第 0 列开始比较所有字符串这一列的字符。如果某个字符串越界，或者这一列字符不一致，就返回前面已经确认的部分。
核心思路
比如 ["flower", "flow", "flight"]：
第 0 列都是 f，继续。 第 1 列都是 l，继续。 第 2 列是 o / o / i，不一致，所以返回 "fl"。
c
#include <string> // 引入 string，用来处理字符串。
#include <vector> // 引入 vector，用来保存字符串数组。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域。
std::string LongestCommonPrefix(std::vector<std::string>& strs) // 求字符串数组的最长公共前缀。
{ // 函数开始。
if (strs.empty()) // 如果数组为空。
{ // if 代码块开始。
return ""; // 空数组没有公共前缀，返回空字符串。
} // if 代码块结束。
for (int col = 0; col < static_cast<int>(strs[0].size()); ++col) // 按列遍历第一个字符串。
{ // 外层循环开始。
char currentChar = strs[0][col]; // 取第一个字符串当前列的字符作为比较基准。
for (int row = 1; row < static_cast<int>(strs.size()); ++row) // 遍历后面的每个字符串。
{ // 内层循环开始。
if (col >= static_cast<int>(strs[row].size())) // 如果当前字符串长度不够，说明前缀到这里结束。
{ // if 代码块开始。
return strs[0].substr(0, col); // 返回第 0 列到 col 前一列组成的前缀。
} // if 代码块结束。
if (strs[row][col] != currentChar) // 如果当前列字符和基准字符不同。
{ // if 代码块开始。
return strs[0].substr(0, col); // 返回前面已经匹配成功的部分。
} // if 代码块结束。
} // 内层循环结束。
} // 外层循环结束。
return strs[0]; // 如果第一个字符串所有字符都匹配，说明它就是最长公共前缀。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度是 O(total chars)，最坏情况会检查所有字符串的所有相关字符。空间复杂度是 O(1)，不算返回字符串本身。
面试关键句
这题本质是“按列确认前缀”。每一列所有字符串都相同，前缀才能继续延长；一旦某个字符串越界或字符不同，就立即返回之前已经确认的部分。
求字符串解码
标准答案
字符串解码通常指把 k[encoded] 这种格式还原成普通字符串，比如 3[a2[c]] 解码后是 "accaccacc"。这题最常用做法是 栈：遇到数字累积重复次数，遇到 [ 保存当前上下文，遇到 ] 弹出上一层并展开当前字符串。
核心思路
维护两个栈：
countStack 保存重复次数。 stringStack 保存进入当前括号前的字符串。
例如 3[a2[c]]：
遇到 3[：保存 count = 3，保存之前字符串 ""。 遇到 a2[：保存 count = 2，保存之前字符串 "a"。 遇到第一个 ]：把 "c" 重复 2 次，拼回 "a"，得到 "acc"。 遇到第二个 ]：把 "acc" 重复 3 次，得到 "accaccacc"。
c
#include <cctype> // 引入字符判断函数，用来判断当前字符是不是数字。
#include <string> // 引入 string，用来保存当前解码字符串。
#include <vector> // 引入 vector，用来模拟栈结构。
class Solution // 定义字符串解码解题类。
{ // 类开始。
public: // 公有成员区域。
std::string DecodeString(const std::string& s) // 解码形如 3[a2[c]] 的字符串。
{ // 函数开始。
std::vector<int> countStack; // 数字栈，保存每一层括号对应的重复次数。
std::vector<std::string> stringStack; // 字符串栈，保存进入当前括号前的字符串。
std::string current; // current 表示当前层正在构造的字符串。
int repeatCount = 0; // repeatCount 表示当前读到的重复次数。
for (char ch : s) // 从左到右扫描每一个字符。
{ // for 循环开始。
if (std::isdigit(static_cast<unsigned char>(ch))) // 如果当前字符是数字。
{ // if 代码块开始。
repeatCount = repeatCount * 10 + (ch - '0'); // 累积数字，支持 12[a] 这种多位数。
} // if 代码块结束。
else if (ch == '[') // 如果遇到左括号，说明要进入新的一层。
{ // else if 代码块开始。
countStack.push_back(repeatCount); // 把当前重复次数压入数字栈。
stringStack.push_back(current); // 把进入括号前的字符串压入字符串栈。
repeatCount = 0; // 清空重复次数，准备处理括号内部。
current.clear(); // 清空当前字符串，开始构造括号内部内容。
} // else if 代码块结束。
else if (ch == ']') // 如果遇到右括号，说明当前层结束。
{ // else if 代码块开始。
int count = countStack.back(); // 取出当前层应该重复的次数。
countStack.pop_back(); // 弹出当前层的重复次数。
std::string previous = stringStack.back(); // 取出进入当前括号前的上一层字符串。
stringStack.pop_back(); // 弹出上一层字符串。
std::string repeated; // 创建 repeated，用来保存 current 重复 count 次的结果。
for (int i = 0; i < count; ++i) // 循环 count 次。
{ // for 循环开始。
repeated += current; // 把当前层字符串追加到 repeated 后面。
} // for 循环结束。
current = previous + repeated; // 回到上一层，把展开结果拼接回上一层字符串。
} // else if 代码块结束。
else // 如果是普通字母。
{ // else 代码块开始。
current.push_back(ch); // 直接追加到当前层字符串。
} // else 代码块结束。
} // for 循环结束。
return current; // 扫描完成后，current 就是最终解码结果。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度是 O(input + output)，输入扫描一遍，但输出字符串可能比输入长很多。空间复杂度是 O(depth + output)，depth 是括号嵌套深度，输出字符串本身也需要空间。
面试关键句
这题的本质是“嵌套上下文恢复”。左括号表示进入新上下文，所以要把旧的 current 和 repeatCount 入栈；右括号表示当前上下文结束，所以弹栈展开并拼回上一层。
求最长有效括号
标准答案
最长有效括号可以用 栈 + 哨兵下标 做。栈里存的是下标，不是括号字符。初始先压入 -1，表示当前合法区间左边界的前一个位置。遇到 ( 就压入下标；遇到 ) 就弹出一个下标尝试匹配。如果弹完栈为空，说明当前 ) 无法匹配，就把它作为新的边界；如果栈不为空，就用 i - st.top() 计算当前有效括号长度。
核心例子
s = ")()())"：
第 0 个 ) 无法匹配，成为边界。 第 1 到第 4 个字符是 "()()"，长度是 4。 第 5 个 ) 又无法继续匹配，成为新边界。
c
#include <algorithm> // 引入 max，用来更新最长长度。
#include <stack> // 引入 stack，用来保存括号下标。
#include <string> // 引入 string，用来接收括号字符串。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域。
int LongestValidParentheses(const std::string& s) // 计算最长有效括号子串长度。
{ // 函数开始。
std::stack<int> indexStack; // 创建下标栈，栈里存放边界或左括号下标。
indexStack.push(-1); // 先放入 -1 作为哨兵边界。
int bestLength = 0; // 保存当前找到的最长有效括号长度。
for (int i = 0; i < static_cast<int>(s.size()); ++i) // 从左到右扫描字符串。
{ // for 循环开始。
if (s[i] == '(') // 如果当前字符是左括号。
{ // if 代码块开始。
indexStack.push(i); // 把左括号下标压入栈中。
} // if 代码块结束。
else // 如果当前字符是右括号。
{ // else 代码块开始。
indexStack.pop(); // 弹出一个下标，尝试和当前右括号匹配。
if (indexStack.empty()) // 如果弹出后栈空，说明当前右括号没有可匹配的左边界。
{ // if 代码块开始。
indexStack.push(i); // 把当前右括号下标作为新的非法边界。
} // if 代码块结束。
else // 如果栈不为空，说明当前右括号成功形成了一个有效区间。
{ // else 代码块开始。
int currentLength = i - indexStack.top(); // 当前有效长度等于当前下标减去栈顶边界。
bestLength = std::max(bestLength, currentLength); // 更新最长有效括号长度。
} // else 代码块结束。
} // else 代码块结束。
} // for 循环结束。
return bestLength; // 返回最长有效括号长度。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度 O(n)，每个字符最多入栈、出栈一次。空间复杂度 O(n)，最坏情况下字符串全是左括号，栈里会存很多下标。
面试关键句
这题的重点是栈里存下标。-1 哨兵负责处理从开头开始的有效区间；遇到无法匹配的右括号，就把它变成新的边界；匹配成功时，当前下标 - 栈顶边界 就是当前连续有效括号长度。
求每日温度
标准答案
每日温度用 单调递减栈。栈里存的是下标，不是温度值。栈中这些下标对应的温度保持递减，表示这些天还没有等到更高温。遍历到当前温度时，如果它比栈顶那天温度高，就说明栈顶那天终于等到了升温，答案就是 当前下标 - 栈顶下标。
核心思路
例如 temperatures = [73,74,75,71,69,72,76,73]：
遇到 72 时，它比前面的 69 和 71 高，所以 69 等了 1 天，71 等了 2 天。 遇到 76 时，它比栈里还没解决的 72、75、74、73 都高，所以批量弹栈并填写答案。 最终结果是 [1,1,4,2,1,1,0,0]。
c
#include <stack> // 引入 stack，用来保存还没等到升温的日期下标。
#include <vector> // 引入 vector，用来保存温度数组和答案数组。
class Solution // 定义每日温度解题类。
{ // 类开始。
public: // 公有成员区域。
std::vector<int> DailyTemperatures(std::vector<int>& temperatures) // 计算每一天要等几天才会升温。
{ // 函数开始。
int n = static_cast<int>(temperatures.size()); // 获取温度数组长度。
std::vector<int> answer(n, 0); // 初始化答案数组，默认都是 0，表示后面没有更高温。
std::stack<int> indexStack; // 创建单调栈，栈里存放日期下标。
for (int i = 0; i < n; ++i) // 从左到右遍历每一天。
{ // for 循环开始。
while (!indexStack.empty() && temperatures[i] > temperatures[indexStack.top()]) // 当前温度比栈顶日期温度更高时。
{ // while 循环开始。
int previousIndex = indexStack.top(); // 取出栈顶日期下标。
indexStack.pop(); // 弹出这个已经找到升温日期的下标。
answer[previousIndex] = i - previousIndex; // 当前日期 i 就是 previousIndex 等到的第一个更高温日期。
} // while 循环结束。
indexStack.push(i); // 当前日期还要等待未来更高温，所以压入栈中。
} // for 循环结束。
return answer; // 返回每一天等待升温的天数。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度是 O(n)，因为每个下标最多入栈一次、出栈一次。空间复杂度是 O(n)，最坏情况下温度一直递减，所有下标都会留在栈里。
面试关键句
这题的关键是栈里存“还没等到更高温的下标”。当前温度一旦比栈顶温度高，就说明当前天是栈顶那天的答案；弹栈后继续比较，可能一次解决多个之前的天数。
求接雨水
标准答案
接雨水的核心公式是：当前位置能接的水量 = min(左边最高墙, 右边最高墙) - 当前高度。如果结果小于 0，就当作 0。面试里最推荐讲 双指针，因为它可以做到 O(n) 时间、O(1) 空间。
核心思路
如果 leftMax < rightMax，说明左边当前位置的水位已经由 leftMax 决定了，因为右边至少有一堵更高的墙兜住它，所以可以先结算左边。反过来，如果 rightMax <= leftMax，就先结算右边。
c
#include <vector> // 引入 vector，用来保存柱子高度数组。
class Solution // 定义接雨水解题类。
{ // 类开始。
public: // 公有成员区域。
int Trap(std::vector<int>& height) // 计算柱子之间最多能接多少雨水。
{ // 函数开始。
int n = static_cast<int>(height.size()); // 获取数组长度。
if (n < 3) // 如果柱子少于 3 根，就无法形成凹槽。
{ // if 代码块开始。
return 0; // 直接返回 0。
} // if 代码块结束。
int left = 0; // 左指针从数组最左侧开始。
int right = n - 1; // 右指针从数组最右侧开始。
int leftMax = 0; // 记录左侧扫描过程中遇到的最高柱子。
int rightMax = 0; // 记录右侧扫描过程中遇到的最高柱子。
int water = 0; // 记录最终接到的总雨水量。
while (left < right) // 当左右指针还没有相遇时继续处理。
{ // while 循环开始。
if (height[left] < height[right]) // 如果左边当前柱子更矮，优先结算左侧。
{ // if 代码块开始。
if (height[left] >= leftMax) // 如果当前左柱子刷新了左侧最高值。
{ // if 代码块开始。
leftMax = height[left]; // 更新 leftMax。
} // if 代码块结束。
else // 如果当前左柱子低于左侧最高值。
{ // else 代码块开始。
water += leftMax - height[left]; // 左侧最高墙减当前高度，就是当前格能接的水。
} // else 代码块结束。
++left; // 左指针向右移动。
} // if 代码块结束。
else // 如果右边当前柱子更矮或两边一样高，优先结算右侧。
{ // else 代码块开始。
if (height[right] >= rightMax) // 如果当前右柱子刷新了右侧最高值。
{ // if 代码块开始。
rightMax = height[right]; // 更新 rightMax。
} // if 代码块结束。
else // 如果当前右柱子低于右侧最高值。
{ // else 代码块开始。
water += rightMax - height[right]; // 右侧最高墙减当前高度，就是当前格能接的水。
} // else 代码块结束。
--right; // 右指针向左移动。
} // else 代码块结束。
} // while 循环结束。
return water; // 返回总雨水量。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度 O(n)，左右指针最多各走一遍数组。空间复杂度 O(1)，只用了几个变量。
面试关键句
接雨水不是看当前柱子本身，而是看它左右两边最高墙的较矮者。双指针的本质是每次结算“边界已经确定的一侧”，所以不需要提前存左右最大数组。
求柱状图最大矩形
标准答案
柱状图最大矩形用 单调递增栈。栈里存下标，并保证这些下标对应的高度递增。遇到一个更矮的柱子时，说明栈顶柱子的右边界已经确定了，就可以弹出栈顶，用它作为矩形高度来计算面积。
核心思路
以 heights = [2,1,5,6,2,3] 为例，扫描到高度 2 时，它比前面的 6 和 5 都矮，所以 6 和 5 的右边界确定了。弹出高度 5 时，左边界是高度 1 的位置，右边界是当前高度 2 的位置，所以宽度是 2，面积是 5 * 2 = 10。
c
#include <algorithm> // 引入 max，用来更新最大矩形面积。
#include <vector> // 引入 vector，用来保存高度数组和模拟栈。
class Solution // 定义柱状图最大矩形解题类。
{ // 类开始。
public: // 公有成员区域。
int LargestRectangleArea(std::vector<int>& heights) // 计算柱状图中的最大矩形面积。
{ // 函数开始。
int n = static_cast<int>(heights.size()); // 获取柱子数量。
std::vector<int> indexStack; // 用 vector 模拟栈，栈里保存柱子的下标。
indexStack.push_back(-1); // 压入 -1 作为哨兵，方便计算宽度。
int bestArea = 0; // 保存当前找到的最大矩形面积。
for (int i = 0; i <= n; ++i) // 多扫一轮 i == n，用高度 0 逼出栈中剩余柱子。
{ // for 循环开始。
int currentHeight = 0; // 默认当前高度为 0，用于最后的哨兵高度。
if (i < n) // 如果 i 还在数组范围内。
{ // if 代码块开始。
currentHeight = heights[i]; // 当前高度就是 heights[i]。
} // if 代码块结束。
while (indexStack.back() != -1 && heights[indexStack.back()] > currentHeight) // 当前柱子更矮时，弹出更高的柱子计算面积。
{ // while 循环开始。
int midIndex = indexStack.back(); // 取出要计算面积的柱子下标。
indexStack.pop_back(); // 弹出这个柱子，因为它的右边界已经确定。
int height = heights[midIndex]; // 被弹出的柱子高度就是当前矩形高度。
int leftLessIndex = indexStack.back(); // 弹出后新的栈顶，就是左边第一个更矮柱子的下标。
int rightLessIndex = i; // 当前 i 就是右边第一个更矮柱子的下标。
int width = rightLessIndex - leftLessIndex - 1; // 矩形宽度是左右更矮柱子之间的距离。
int area = height * width; // 当前矩形面积等于高度乘宽度。
bestArea = std::max(bestArea, area); // 更新最大矩形面积。
} // while 循环结束。
indexStack.push_back(i); // 当前柱子入栈，等待之后找到它的右边界。
} // for 循环结束。
return bestArea; // 返回最大矩形面积。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度是 O(n)，因为每个下标最多入栈一次、出栈一次。空间复杂度是 O(n)，最坏情况下高度一直递增，所有下标都会留在栈里。
面试关键句
这题的关键是：弹出的柱子作为矩形高度，当前下标是它右边第一个更矮的位置，弹出后新的栈顶是它左边第一个更矮的位置，所以宽度是 right - left - 1。
求最大矩形
标准答案
最大矩形指二维 0/1 矩阵里，只由 1 组成的最大矩形面积。核心做法是：把每一行当作矩形底边，把这一行往上连续的 1 统计成柱状图高度，然后对每一行都跑一次“柱状图最大矩形”。
核心思路
比如某一行统计出的高度是 [3,1,3,2,2]，就表示以这一行为底边，每一列向上连续有多少个 1。然后问题就变成：在这组柱状图里求最大矩形面积。
c
#include <algorithm> // 引入 max，用来更新最大面积。
#include <vector> // 引入 vector，用来保存矩阵、高度数组和栈。
class Solution // 定义最大矩形解题类。
{ // 类开始。
private: // 私有成员区域。
int LargestRectangleArea(const std::vector<int>& heights) // 求一行柱状图中的最大矩形面积。
{ // 函数开始。
std::vector<int> indexStack; // 用 vector 模拟栈，栈里保存柱子下标。
indexStack.push_back(-1); // 压入 -1 作为哨兵，方便计算宽度。
int bestArea = 0; // 保存当前柱状图中的最大矩形面积。
int n = static_cast<int>(heights.size()); // 获取柱子数量。
for (int i = 0; i <= n; ++i) // 多遍历一轮，用高度 0 清空栈。
{ // for 循环开始。
int currentHeight = 0; // 默认当前高度为 0，用于最后一轮哨兵。
if (i < n) // 如果 i 还在真实数组范围内。
{ // if 代码块开始。
currentHeight = heights[i]; // 当前高度就是 heights[i]。
} // if 代码块结束。
while (indexStack.back() != -1 && heights[indexStack.back()] > currentHeight) // 当前柱子更矮时，栈顶柱子的右边界确定。
{ // while 循环开始。
int midIndex = indexStack.back(); // 取出要计算面积的柱子下标。
indexStack.pop_back(); // 弹出这个柱子。
int height = heights[midIndex]; // 被弹出的柱子高度就是矩形高度。
int leftLessIndex = indexStack.back(); // 弹出后新的栈顶是左边第一个更矮柱子的下标。
int rightLessIndex = i; // 当前 i 是右边第一个更矮柱子的下标。
int width = rightLessIndex - leftLessIndex - 1; // 左右更矮柱子之间的宽度就是矩形宽度。
int area = height * width; // 当前矩形面积等于高度乘宽度。
bestArea = std::max(bestArea, area); // 更新最大面积。
} // while 循环结束。
indexStack.push_back(i); // 当前下标入栈，等待之后确定右边界。
} // for 循环结束。
return bestArea; // 返回当前柱状图的最大矩形面积。
} // 函数结束。
public: // 公有成员区域。
int MaximalRectangle(std::vector<std::vector<char>>& matrix) // 求 0/1 矩阵中的最大 1 矩形面积。
{ // 函数开始。
if (matrix.empty() || matrix[0].empty()) // 如果矩阵为空。
{ // if 代码块开始。
return 0; // 空矩阵没有矩形，返回 0。
} // if 代码块结束。
int rows = static_cast<int>(matrix.size()); // 获取矩阵行数。
int cols = static_cast<int>(matrix[0].size()); // 获取矩阵列数。
std::vector<int> heights(cols, 0); // heights[col] 表示当前行往上连续 1 的高度。
int bestArea = 0; // 保存全局最大矩形面积。
for (int row = 0; row < rows; ++row) // 枚举每一行，把这一行作为矩形底边。
{ // 外层循环开始。
for (int col = 0; col < cols; ++col) // 枚举当前行的每一列。
{ // 内层循环开始。
if (matrix[row][col] == '1') // 如果当前位置是 1。
{ // if 代码块开始。
heights[col] += 1; // 当前列连续 1 的高度加 1。
} // if 代码块结束。
else // 如果当前位置是 0。
{ // else 代码块开始。
heights[col] = 0; // 连续 1 被打断，高度清零。
} // else 代码块结束。
} // 内层循环结束。
int currentArea = LargestRectangleArea(heights); // 把当前行的 heights 当作柱状图求最大矩形。
bestArea = std::max(bestArea, currentArea); // 更新全局最大矩形面积。
} // 外层循环结束。
return bestArea; // 返回最终最大矩形面积。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度是 O(rows * cols)，因为每一行更新一次高度，并跑一次 O(cols) 的单调栈。空间复杂度是 O(cols)，主要是 heights 和栈。
面试关键句
这题是“柱状图最大矩形”的二维升级版：固定每一行作为底边，把向上连续的 1 转成柱高，然后每一行都求一次柱状图最大矩形，取最大值。
求编辑距离
标准答案
编辑距离就是把 word1 变成 word2 的最少操作次数，每次可以 插入、删除、替换 一个字符。最经典做法是二维 DP。
核心思路
dp[i][j] 表示：把 word1 的前 i 个字符，变成 word2 的前 j 个字符，需要的最少操作数。
如果 word1[i - 1] == word2[j - 1]，当前字符不用操作：
c
dp[i][j] = dp[i - 1][j - 1]如果不同，就从三种操作里选最小：
c
dp[i][j] = 1 + min(删除, 插入, 替换)
#include <algorithm> // 引入 min，用来从三种操作代价中取最小值。
#include <string> // 引入 string，用来表示两个单词。
#include <vector> // 引入 vector，用来创建二维 DP 表。
class Solution // 定义编辑距离解题类。
{ // 类开始。
public: // 公有成员区域。
int MinDistance(const std::string& word1, const std::string& word2) // 计算 word1 变成 word2 的最少操作数。
{ // 函数开始。
int m = static_cast<int>(word1.size()); // 获取 word1 的长度。
int n = static_cast<int>(word2.size()); // 获取 word2 的长度。
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0)); // 创建 dp 表，dp[i][j] 表示两个前缀的编辑距离。
for (int i = 0; i <= m; ++i) // 初始化第一列。
{ // for 循环开始。
dp[i][0] = i; // word1 的前 i 个字符变成空串，需要删除 i 次。
} // for 循环结束。
for (int j = 0; j <= n; ++j) // 初始化第一行。
{ // for 循环开始。
dp[0][j] = j; // 空串变成 word2 的前 j 个字符，需要插入 j 次。
} // for 循环结束。
for (int i = 1; i <= m; ++i) // 枚举 word1 的前缀长度。
{ // 外层循环开始。
for (int j = 1; j <= n; ++j) // 枚举 word2 的前缀长度。
{ // 内层循环开始。
if (word1[i - 1] == word2[j - 1]) // 如果两个前缀的最后一个字符相同。
{ // if 代码块开始。
dp[i][j] = dp[i - 1][j - 1]; // 不需要新增操作，直接继承左上角状态。
} // if 代码块结束。
else // 如果两个前缀的最后一个字符不同。
{ // else 代码块开始。
int deleteCost = dp[i - 1][j] + 1; // 删除 word1[i - 1] 后，把前 i - 1 个字符变成 word2 前 j 个字符。
int insertCost = dp[i][j - 1] + 1; // 在 word1 前 i 个字符后插入 word2[j - 1]。
int replaceCost = dp[i - 1][j - 1] + 1; // 把 word1[i - 1] 替换成 word2[j - 1]。
dp[i][j] = std::min(deleteCost, std::min(insertCost, replaceCost)); // 三种操作里取最小代价。
} // else 代码块结束。
} // 内层循环结束。
} // 外层循环结束。
return dp[m][n]; // 返回整个 word1 变成整个 word2 的编辑距离。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度是 O(mn)，m 和 n 分别是两个字符串长度。空间复杂度是 O(mn)，如果面试追问优化，可以用滚动数组优化到 O(n)。
面试关键句
编辑距离的本质是“两个前缀之间的最优转换”。当前字符相同就继承左上角；当前字符不同，就在删除、插入、替换三种操作里取最小值再加一。
求完全背包
标准答案
完全背包是：背包容量固定，每种物品可以重复选择，求最大价值。它和 0/1 背包 最核心的区别是：0/1 背包容量倒序遍历，完全背包容量 正序遍历。
核心思路
dp[c] 表示容量为 c 的背包能装出的最大价值。
对于一个物品，重量是 w，价值是 v：
c
dp[c] = max(dp[c], dp[c - w] + v)完全背包要正序遍历容量：
c
for c = w 到 capacity因为 dp[c - w] 可以是本轮刚刚更新过的结果，这就表示当前物品可以被重复使用。
c
#include <algorithm> // 引入 max，用来更新最大价值。
#include <vector> // 引入 vector，用来保存重量、价值和 DP 数组。
class Solution // 定义完全背包解题类。
{ // 类开始。
public: // 公有成员区域。
int CompleteKnapsack(const std::vector<int>& weights, const std::vector<int>& values, int capacity) // 求完全背包最大价值。
{ // 函数开始。
int itemCount = static_cast<int>(weights.size()); // 获取物品数量。
std::vector<int> dp(capacity + 1, 0); // dp[c] 表示容量 c 能获得的最大价值。
for (int item = 0; item < itemCount; ++item) // 枚举每一种物品。
{ // 外层循环开始。
int weight = weights[item]; // 当前物品的重量。
int value = values[item]; // 当前物品的价值。
for (int c = weight; c <= capacity; ++c) // 完全背包容量正序遍历，允许重复使用当前物品。
{ // 内层循环开始。
int notChoose = dp[c]; // 不选当前物品时，价值保持 dp[c]。
int choose = dp[c - weight] + value; // 选当前物品一次，再加上剩余容量的最优价值。
dp[c] = std::max(notChoose, choose); // 在选和不选之间取最大值。
} // 内层循环结束。
} // 外层循环结束。
return dp[capacity]; // 返回容量为 capacity 时的最大价值。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度是 O(nW)，n 是物品数量，W 是背包容量。空间复杂度是 O(W)。
面试关键句
完全背包能重复使用当前物品，所以一维 DP 必须正序遍历容量，让 dp[c - weight] 可以来自本轮刚更新过的状态。如果写成倒序，就变成了每个物品最多选一次的 0/1 背包。
求 01 背包
一句话定义
01 背包就是：有 n 个物品，每个物品只能选一次，在背包容量不超过 W 的前提下，让总价值最大。
核心思路
dp[c] 表示：当前已经考虑过的物品里，背包容量为 c 时能拿到的最大价值。
状态转移是：
c
dp[c] = max(dp[c], dp[c - weight] + value)关键点是：01 背包容量必须倒序遍历。 因为每个物品只能用一次，倒序可以保证 dp[c - weight] 还是“上一轮物品”的状态，不会把当前物品重复拿多次。
C++ 代码
c
#include <algorithm> // 引入 std::max，用来比较选和不选的最大价值。
#include <vector> // 引入 std::vector，用来存重量、价值和 DP 数组。
class Solution // 定义一个解题类。
{ // 类开始。
public: // 公有成员区域开始。
int ZeroOneKnapsack(const std::vector<int>& weights, const std::vector<int>& values, int capacity) // 求 01 背包最大价值。
{ // 函数开始。
int itemCount = static_cast<int>(weights.size()); // 获取物品数量。
std::vector<int> dp(capacity + 1, 0); // dp[c] 表示容量为 c 时能获得的最大价值。
for (int item = 0; item < itemCount; ++item) // 逐个枚举每一个物品。
{ // 外层循环开始。
int weight = weights[item]; // 取出当前物品的重量。
int value = values[item]; // 取出当前物品的价值。
for (int c = capacity; c >= weight; --c) // 容量倒序遍历，避免当前物品被重复使用。
{ // 内层循环开始。
int notChoose = dp[c]; // 不选当前物品，价值保持原来的 dp[c]。
int choose = dp[c - weight] + value; // 选当前物品，价值等于剩余容量的最优值加当前价值。
dp[c] = std::max(notChoose, choose); // 在选和不选之间取最大值。
} // 内层循环结束。
} // 外层循环结束。
return dp[capacity]; // 返回容量为 capacity 时的最大价值。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度：O(nW)，n 是物品数量，W 是背包容量。 空间复杂度：O(W)，因为用了一维 DP 数组。
求多重背包
标准答案
多重背包是：每种物品都有数量上限，比如物品 A 最多拿 5 个，物品 B 最多拿 3 个，在容量不超过 W 的情况下求最大价值。
它介于 01 背包和完全背包之间：
01 背包：每个物品最多拿 1 次。 完全背包：每个物品可以拿无限次。 多重背包：每个物品最多拿 count[i] 次。
底层原理
朴素做法是枚举“第几个物品、当前容量、拿几个”，复杂度大概是：
O(n * W * count)更常见的优化是二进制拆分：
5 个 A = 1 个 A + 2 个 A + 2 个 A
13 个 A = 1 个 A + 2 个 A + 4 个 A + 6 个 A这样就把“最多拿 k 个”转换成若干个“只能选一次的组合包”，然后直接套 01 背包。
C++ 代码
c
#include <algorithm> // 引入 std::max 和 std::min，用来比较最大值和拆分数量。
#include <vector> // 引入 std::vector，用来保存重量、价值、数量和 DP 数组。
class Solution // 定义一个解题类。
{ // 类开始。
public: // 公有成员区域开始。
int MultipleKnapsack(const std::vector<int>& weights, const std::vector<int>& values, const std::vector<int>& counts, int capacity) // 求多重背包最大价值。
{ // 函数开始。
int itemCount = static_cast<int>(weights.size()); // 获取物品种类数量。
std::vector<int> dp(capacity + 1, 0); // dp[c] 表示容量为 c 时能获得的最大价值。
for (int item = 0; item < itemCount; ++item) // 枚举每一种物品。
{ // 外层循环开始。
int weight = weights[item]; // 当前物品单个重量。
int value = values[item]; // 当前物品单个价值。
int remain = counts[item]; // 当前物品还剩多少个可以拆分。
int groupSize = 1; // 当前二进制分组大小，先从 1 个开始。
while (remain > 0) // 只要还有剩余数量，就继续拆分。
{ // 拆分循环开始。
int take = std::min(groupSize, remain); // 本组实际拿多少个，不能超过剩余数量。
int groupWeight = weight * take; // 本组组合物品的总重量。
int groupValue = value * take; // 本组组合物品的总价值。
for (int c = capacity; c >= groupWeight; --c) // 拆分后是 01 背包，所以容量必须倒序遍历。
{ // 容量循环开始。
int notChoose = dp[c]; // 不选当前组合包时，价值保持不变。
int choose = dp[c - groupWeight] + groupValue; // 选当前组合包时，用剩余容量价值加本组价值。
dp[c] = std::max(notChoose, choose); // 在选和不选之间取最大值。
} // 容量循环结束。
remain -= take; // 减掉本次已经拆出去的数量。
groupSize *= 2; // 下一组按二进制扩大为 2 倍。
} // 拆分循环结束。
} // 外层循环结束。
return dp[capacity]; // 返回容量为 capacity 时的最大价值。
} // 函数结束。
}; // 类结束。复杂度
朴素多重背包：O(n * W * count)。 二进制优化后：O(W * sum(log count[i]))。 空间复杂度：O(W)。
求最长回文子串
标准答案
最长回文子串是：在字符串里找一个“连续”的最长回文片段。比如 babad 的答案可以是 bab，也可以是 aba。
面试里最稳的写法是中心扩展法：枚举每个位置作为中心，然后向左右扩展。因为回文的本质就是左右对称。
核心思路
每个位置都可能成为回文中心：
奇数长度回文：中心是一个字符，比如 bab 的中心是 a。 偶数长度回文：中心是两个字符中间，比如 abba 的中心在两个 b 中间。
所以每个下标 i 都要尝试：
c
expand(i, i)
expand(i, i + 1)C++ 代码
c
#include <string> // 引入 std::string，用来表示字符串和返回答案。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
std::string LongestPalindrome(const std::string& s) // 定义函数，返回字符串 s 中的最长回文子串。
{ // 函数开始。
if (s.empty()) // 如果字符串为空，就没有回文子串。
{ // if 代码块开始。
return ""; // 返回空字符串。
} // if 代码块结束。
int bestStart = 0; // 记录当前最长回文子串的起始下标。
int bestLength = 1; // 记录当前最长回文子串的长度，单个字符天然是回文。
int n = static_cast<int>(s.size()); // 获取字符串长度并转成 int。
for (int center = 0; center < n; ++center) // 枚举每一个位置作为中心。
{ // for 循环开始。
ExpandFromCenter(s, center, center, bestStart, bestLength); // 处理奇数长度回文，比如 bab。
ExpandFromCenter(s, center, center + 1, bestStart, bestLength); // 处理偶数长度回文，比如 abba。
} // for 循环结束。
return s.substr(bestStart, bestLength); // 根据最优起点和长度截取最长回文子串。
} // 函数结束。
private: // 私有成员区域开始。
void ExpandFromCenter(const std::string& s, int left, int right, int& bestStart, int& bestLength) // 从中心向左右扩展。
{ // 辅助函数开始。
int n = static_cast<int>(s.size()); // 获取字符串长度。
while (left >= 0 && right < n && s[left] == s[right]) // 只要没越界且左右字符相等，就继续扩展。
{ // while 循环开始。
--left; // 左指针向左移动一格。
++right; // 右指针向右移动一格。
} // while 循环结束。
int currentStart = left + 1; // 停止时 left 已经多退了一格，所以真实起点是 left + 1。
int currentLength = right - left - 1; // 停止时 right 也多走了一格，所以长度是 right - left - 1。
if (currentLength > bestLength) // 如果当前回文比历史最长回文更长。
{ // if 代码块开始。
bestStart = currentStart; // 更新最长回文子串的起点。
bestLength = currentLength; // 更新最长回文子串的长度。
} // if 代码块结束。
} // 辅助函数结束。
}; // 类结束。复杂度
时间复杂度：O(n^2)，每个中心最多向外扩展 O(n)。 空间复杂度：O(1)，只记录起点和长度。 更优算法是 Manacher，可以做到 O(n)，但手写难度更高。
求最长回文子序列
标准答案
最长回文子序列是：在字符串中找一个最长的回文序列，字符可以不连续，但相对顺序不能变。
比如：
s = "bbbab"
最长回文子序列 = "bbbb"
答案 = 4它和“最长回文子串”的区别是：子串必须连续，子序列可以跳过字符。
核心思路
用区间 DP：
dp[l][r] 表示 s[l..r] 这个区间里的最长回文子序列长度如果两端字符相等：
c
dp[l][r] = dp[l + 1][r - 1] + 2如果两端字符不相等：
c
dp[l][r] = max(dp[l + 1][r], dp[l][r - 1])C++ 代码
c
#include <algorithm> // 引入 std::max，用来比较两个状态的最大值。
#include <string> // 引入 std::string，用来表示输入字符串。
#include <vector> // 引入 std::vector，用来创建二维 DP 表。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
int LongestPalindromeSubseq(const std::string& s) // 定义函数，返回最长回文子序列长度。
{ // 函数开始。
int n = static_cast<int>(s.size()); // 获取字符串长度。
if (n == 0) // 如果字符串为空。
{ // if 代码块开始。
return 0; // 空字符串的最长回文子序列长度是 0。
} // if 代码块结束。
std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0)); // dp[l][r] 表示 s[l..r] 的最长回文子序列长度。
for (int left = n - 1; left >= 0; --left) // left 倒序遍历，保证 dp[left + 1][...] 已经算过。
{ // 外层循环开始。
dp[left][left] = 1; // 单个字符一定是回文，长度为 1。
for (int right = left + 1; right < n; ++right) // right 正序遍历，逐渐扩大区间。
{ // 内层循环开始。
if (s[left] == s[right]) // 如果区间两端字符相等。
{ // if 代码块开始。
dp[left][right] = dp[left + 1][right - 1] + 2; // 两端字符可以一起加入回文序列。
} // if 代码块结束。
else // 如果区间两端字符不相等。
{ // else 代码块开始。
dp[left][right] = std::max(dp[left + 1][right], dp[left][right - 1]); // 尝试跳过左端或跳过右端，取更大值。
} // else 代码块结束。
} // 内层循环结束。
} // 外层循环结束。
return dp[0][n - 1]; // 返回整个字符串区间的答案。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度：O(n^2)。 空间复杂度：O(n^2)。 因为一共有大约 n * n 个区间状态。
求最小覆盖子串
标准答案
最小覆盖子串是：在 s 中找一个最短的连续子串，使它包含 t 中所有字符，并且字符出现次数也要满足。
比如：
c
s = "ADOBECODEBANC"
t = "ABC"
答案 = "BANC"核心思路
用滑动窗口：
右指针 right：不断扩大窗口，把字符加入窗口。 左指针 left：当窗口已经覆盖 t 后，尽量收缩窗口。 need：记录 t 需要哪些字符、各需要几个。 window：记录当前窗口中各字符出现了几次。 valid：有多少种字符已经满足需求。
C++ 代码
c
#include <climits> // 引入 INT_MAX，用来表示当前还没有找到合法答案。
#include <string> // 引入 std::string，用来处理字符串。
#include <vector> // 引入 std::vector，用来做字符计数表。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
std::string MinWindow(const std::string& s, const std::string& t) // 返回 s 中覆盖 t 的最小子串。
{ // 函数开始。
if (s.empty() || t.empty() || s.size() < t.size()) // 如果 s 或 t 为空，或者 s 比 t 短，就不可能覆盖。
{ // if 代码块开始。
return ""; // 返回空字符串。
} // if 代码块结束。
std::vector<int> need(256, 0); // need[c] 表示字符 c 在 t 中需要出现几次。
std::vector<int> window(256, 0); // window[c] 表示字符 c 在当前窗口中出现几次。
int required = 0; // required 表示 t 中一共有多少种不同字符需要满足。
for (char ch : t) // 遍历 t 中的每一个字符。
{ // for 循环开始。
unsigned char key = static_cast<unsigned char>(ch); // 转成 unsigned char，避免 char 为负数导致数组下标错误。
if (need[key] == 0) // 如果这个字符之前没有出现过。
{ // if 代码块开始。
++required; // 需要满足的字符种类数加一。
} // if 代码块结束。
++need[key]; // 这个字符的需求次数加一。
} // for 循环结束。
int valid = 0; // valid 表示当前窗口中已经满足需求的字符种类数。
int left = 0; // left 表示窗口左边界。
int bestStart = 0; // bestStart 记录最短覆盖子串的起点。
int bestLength = INT_MAX; // bestLength 记录最短覆盖子串的长度。
for (int right = 0; right < static_cast<int>(s.size()); ++right) // right 向右移动，不断扩大窗口。
{ // 外层循环开始。
unsigned char inChar = static_cast<unsigned char>(s[right]); // 获取即将进入窗口的字符。
++window[inChar]; // 把这个字符加入当前窗口。
if (need[inChar] > 0 && window[inChar] == need[inChar]) // 如果这个字符是目标字符，并且数量刚好满足需求。
{ // if 代码块开始。
++valid; // 满足需求的字符种类数加一。
} // if 代码块结束。
while (valid == required) // 当窗口已经覆盖 t 时，尝试收缩左边界。
{ // while 循环开始。
int currentLength = right - left + 1; // 计算当前合法窗口长度。
if (currentLength < bestLength) // 如果当前窗口比历史答案更短。
{ // if 代码块开始。
bestStart = left; // 更新最短窗口起点。
bestLength = currentLength; // 更新最短窗口长度。
} // if 代码块结束。
unsigned char outChar = static_cast<unsigned char>(s[left]); // 获取即将移出窗口的字符。
--window[outChar]; // 把左边界字符移出窗口。
if (need[outChar] > 0 && window[outChar] < need[outChar]) // 如果移出后目标字符数量不够了。
{ // if 代码块开始。
--valid; // 满足需求的字符种类数减一。
} // if 代码块结束。
++left; // 左边界右移，继续尝试缩小窗口。
} // while 循环结束。
} // 外层循环结束。
if (bestLength == INT_MAX) // 如果从头到尾都没有找到合法窗口。
{ // if 代码块开始。
return ""; // 返回空字符串。
} // if 代码块结束。
return s.substr(bestStart, bestLength); // 截取并返回最短覆盖子串。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度：O(n + m)，n 是 s 长度，m 是 t 长度。 空间复杂度：O(1)，因为字符表大小固定为 256。
求股票买卖含手续费
标准答案
股票买卖含手续费，一般指：可以交易多次，但同一时间最多只能持有一股；每次卖出时扣一次手续费 fee，求最大利润。
核心用两个状态：
cash：今天结束后，手里没有股票的最大利润
hold：今天结束后，手里持有一股股票的最大利润状态转移：
cash = max(昨天 cash, 昨天 hold + 今天价格 - fee)
hold = max(昨天 hold, 昨天 cash - 今天价格)C++ 代码
c
#include <algorithm> // 引入 std::max，用来比较两种选择的最大利润。
#include <vector> // 引入 std::vector，用来存储股票价格数组。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
int MaxProfitWithFee(const std::vector<int>& prices, int fee) // 计算含手续费的股票买卖最大利润。
{ // 函数开始。
if (prices.empty()) // 如果价格数组为空，说明没有任何交易机会。
{ // if 代码块开始。
return 0; // 没有价格就没有利润，直接返回 0。
} // if 代码块结束。
int cash = 0; // cash 表示当前不持股时的最大利润。
int hold = -prices[0]; // hold 表示当前持股时的最大利润，相当于第 0 天买入。
for (int day = 1; day < static_cast<int>(prices.size()); ++day) // 从第 1 天开始遍历每天价格。
{ // for 循环开始。
int price = prices[day]; // 取出今天的股票价格。
int oldCash = cash; // 保存昨天不持股状态，避免被本轮更新污染。
int oldHold = hold; // 保存昨天持股状态，避免被本轮更新污染。
cash = std::max(oldCash, oldHold + price - fee); // 今天不持股：要么昨天就不持股，要么今天卖出并扣手续费。
hold = std::max(oldHold, oldCash - price); // 今天持股：要么昨天就持股，要么今天买入。
} // for 循环结束。
return cash; // 最后手里不持股才是最终落袋利润。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度：O(n)，每天只处理一次。 空间复杂度：O(1)，只维护 cash 和 hold 两个状态。
常见坑
手续费只扣一次，通常放在卖出时扣。 更新 cash 和 hold 时要保存旧状态，否则可能用“今天刚更新的状态”继续计算今天的另一个状态。
求股票买卖含冷冻期
标准答案
股票买卖含冷冻期是：可以多次买卖股票，但卖出后的下一天不能买入，也就是要冷冻一天。
这题最清楚的做法是三状态 DP：
hold：今天结束后，手里持有股票
sold：今天刚卖出股票
rest：今天结束后空仓，并且不是今天刚卖，下一天可以买状态转移：
c
hold = max(oldHold, oldRest - price)
sold = oldHold + price
rest = max(oldRest, oldSold)注意：买入只能从 rest 来，不能从 sold 来，这就是冷冻期的体现。
C++ 代码
c
#include <algorithm> // 引入 std::max，用来比较两种状态的最大利润。
#include <vector> // 引入 std::vector，用来存储每天的股票价格。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
int MaxProfitWithCooldown(const std::vector<int>& prices) // 计算含冷冻期的股票买卖最大利润。
{ // 函数开始。
if (prices.empty()) // 如果价格数组为空，说明没有任何交易机会。
{ // if 代码块开始。
return 0; // 没有交易机会，最大利润就是 0。
} // if 代码块结束。
const int NEG_INF = -1000000000; // 定义一个很小的数，表示不可能状态。
int hold = -prices[0]; // hold 表示今天结束后持股的最大利润，第 0 天买入就是 -prices[0]。
int sold = NEG_INF; // sold 表示今天刚卖出的最大利润，第 0 天不可能刚卖出。
int rest = 0; // rest 表示今天结束后空仓且可买的最大利润，初始为 0。
for (int day = 1; day < static_cast<int>(prices.size()); ++day) // 从第 1 天开始遍历价格。
{ // for 循环开始。
int price = prices[day]; // 取出今天的股票价格。
int oldHold = hold; // 保存昨天的 hold，避免被本轮更新污染。
int oldSold = sold; // 保存昨天的 sold，避免被本轮更新污染。
int oldRest = rest; // 保存昨天的 rest，避免被本轮更新污染。
hold = std::max(oldHold, oldRest - price); // 今天持股：要么昨天就持股，要么今天从 rest 状态买入。
sold = oldHold + price; // 今天刚卖：只能来自昨天持股状态，然后今天卖出。
rest = std::max(oldRest, oldSold); // 今天空仓可买：要么昨天就 rest，要么昨天 sold 后今天冷冻结束。
} // for 循环结束。
return std::max(sold, rest); // 最终不能要求手里还持股，所以答案是不持股状态中的最大值。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度：O(n)。 空间复杂度：O(1)。 每天只更新 hold、sold、rest 三个状态。
求打家劫舍树形版本
标准答案
打家劫舍树形版本的核心是：父子节点不能同时偷，所以每个节点都要返回两个状态：
rob：偷当前节点能得到的最大收益
skip：不偷当前节点能得到的最大收益转移公式：
c
rob = node.val + left.skip + right.skip
skip = max(left.rob, left.skip) + max(right.rob, right.skip)最后答案是：
c
max(root.rob, root.skip)C++ 代码
c
#include <algorithm> // 引入 std::max，用来比较偷和不偷的最大收益。
#include <utility> // 引入 std::pair，用来返回 rob 和 skip 两个状态。
struct TreeNode // 定义二叉树节点结构。
{ // 结构体开始。
int val; // 当前节点的金额。
TreeNode* left; // 指向左孩子节点。
TreeNode* right; // 指向右孩子节点。
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造函数，初始化节点值和左右孩子。
}; // 结构体结束。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
int Rob(TreeNode* root) // 求整棵树能偷到的最大金额。
{ // 函数开始。
std::pair<int, int> result = Dfs(root); // 后序遍历整棵树，返回根节点的 rob 和 skip。
return std::max(result.first, result.second); // 根节点偷或不偷都可以，取最大值。
} // 函数结束。
private: // 私有成员区域开始。
std::pair<int, int> Dfs(TreeNode* node) // 返回当前子树的两个状态：first 是 rob，second 是 skip。
{ // 递归函数开始。
if (node == nullptr) // 如果当前节点为空。
{ // if 代码块开始。
return {0, 0}; // 空节点偷和不偷的收益都是 0。
} // if 代码块结束。
std::pair<int, int> left = Dfs(node->left); // 递归计算左子树的 rob 和 skip。
std::pair<int, int> right = Dfs(node->right); // 递归计算右子树的 rob 和 skip。
int robCurrent = node->val + left.second + right.second; // 偷当前节点时，左右孩子都不能偷。
int skipCurrent = std::max(left.first, left.second) + std::max(right.first, right.second); // 不偷当前节点时，左右孩子各自选择最大收益。
return {robCurrent, skipCurrent}; // 返回当前节点偷和不偷两种结果。
} // 递归函数结束。
}; // 类结束。复杂度
时间复杂度：O(n)，每个节点只访问一次。 空间复杂度：O(h)，h 是树高，来自递归调用栈。
求路径总和 III
标准答案
路径总和 III 是：统计二叉树中有多少条路径的节点值之和等于 targetSum。
注意这条路径：
可以从任意节点开始。 可以在任意节点结束。 必须从父节点往子节点方向走，不能向上走，也不能拐弯。
最优做法是 DFS + 前缀和 + 回溯。
核心思路
当前从根走到某个节点的前缀和是 cur。 如果之前出现过某个前缀和 cur - targetSum，说明中间这一段路径的和就是：
c
cur - (cur - targetSum) = targetSum所以每到一个节点，就查：
c
prefixCount[cur - targetSum]查完后，把当前 cur 加入哈希表，递归左右子树。 离开当前节点时，要把当前 cur 撤销，这就是回溯。
C++ 代码
c
#include <unordered_map> // 引入 unordered_map，用来记录每种前缀和出现了几次。
struct TreeNode // 定义二叉树节点结构。
{ // 结构体开始。
int val; // 当前节点的值。
TreeNode* left; // 指向左孩子节点。
TreeNode* right; // 指向右孩子节点。
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造函数，初始化节点值和左右孩子。
}; // 结构体结束。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
int PathSum(TreeNode* root, int targetSum) // 统计路径和等于 targetSum 的路径条数。
{ // 函数开始。
std::unordered_map<long long, int> prefixCount; // prefixCount[sum] 表示当前递归路径上某个前缀和出现的次数。
prefixCount[0] = 1; // 前缀和 0 先出现一次，用来处理从当前路径起点直接满足 target 的情况。
return Dfs(root, 0LL, static_cast<long long>(targetSum), prefixCount); // 从根节点开始 DFS，初始前缀和为 0。
} // 函数结束。
private: // 私有成员区域开始。
int Dfs(TreeNode* node, long long currentSum, long long targetSum, std::unordered_map<long long, int>& prefixCount) // DFS 返回当前子树中满足条件的路径数量。
{ // DFS 函数开始。
if (node == nullptr) // 如果当前节点为空。
{ // if 代码块开始。
return 0; // 空节点没有路径，返回 0。
} // if 代码块结束。
currentSum += node->val; // 把当前节点值加入从根到当前节点的前缀和。
long long needPrefix = currentSum - targetSum; // 如果之前出现过 needPrefix，则中间那段路径和就是 targetSum。
int result = 0; // result 用来统计当前节点及其子树中的合法路径数量。
auto found = prefixCount.find(needPrefix); // 在哈希表中查找需要的历史前缀和。
if (found != prefixCount.end()) // 如果这个历史前缀和出现过。
{ // if 代码块开始。
result += found->second; // 出现几次，就说明有几条路径能以当前节点结尾并满足 targetSum。
} // if 代码块结束。
++prefixCount[currentSum]; // 进入当前节点后，把当前前缀和加入哈希表。
result += Dfs(node->left, currentSum, targetSum, prefixCount); // 递归统计左子树中的合法路径。
result += Dfs(node->right, currentSum, targetSum, prefixCount); // 递归统计右子树中的合法路径。
--prefixCount[currentSum]; // 离开当前节点前撤销当前前缀和，避免影响兄弟分支。
if (prefixCount[currentSum] == 0) // 如果当前前缀和次数已经变成 0。
{ // if 代码块开始。
prefixCount.erase(currentSum); // 从哈希表中删除它，让表保持干净。
} // if 代码块结束。
return result; // 返回当前子树统计到的合法路径数量。
} // DFS 函数结束。
}; // 类结束。复杂度
时间复杂度：O(n)，每个节点访问一次。 空间复杂度：O(h) 到 O(n)，取决于树高和递归路径上的前缀和数量。 代码里用 long long 是为了防止节点值累加时溢出。
求二叉树序列化
标准答案
二叉树序列化就是：把一棵二叉树保存成字符串；反序列化就是：再根据这个字符串还原出原来的树。
最常见做法是：
前序遍历：根、左、右
空节点用 # 表示
节点之间用 , 分隔比如这棵树：
1
/ \
2 3
/ \
4 5可以序列化成：
1,2,#,#,3,4,#,#,5,#,#核心思路
为什么必须写 #？ 因为如果不记录空节点，只写 1,2,3,4,5，树的形状会丢失，反序列化时无法知道谁是谁的左孩子、右孩子。
反序列化时，按前序顺序读 token：
读到数字：创建节点，然后递归创建左子树和右子树。 读到 #：说明这里是空节点，返回 nullptr。
C++ 代码
c
#include <string> // 引入 std::string，用来保存序列化后的字符串。
struct TreeNode // 定义二叉树节点结构。
{ // 结构体开始。
int val; // 当前节点的值。
TreeNode* left; // 当前节点的左孩子指针。
TreeNode* right; // 当前节点的右孩子指针。
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造函数，初始化节点值和左右孩子。
}; // 结构体结束。
class Codec // 定义序列化和反序列化工具类。
{ // 类开始。
public: // 公有成员区域开始。
std::string serialize(TreeNode* root) // 把二叉树序列化成字符串。
{ // serialize 函数开始。
std::string result; // result 用来保存最终序列化结果。
SerializeDfs(root, result); // 用前序遍历把整棵树写入 result。
if (!result.empty()) // 如果结果不为空。
{ // if 代码块开始。
result.pop_back(); // 删除最后多余的逗号。
} // if 代码块结束。
return result; // 返回序列化字符串。
} // serialize 函数结束。
TreeNode* deserialize(const std::string& data) // 把字符串反序列化成二叉树。
{ // deserialize 函数开始。
int index = 0; // index 表示当前读取到字符串的哪个位置。
return DeserializeDfs(data, index); // 从 index 位置开始按前序规则还原二叉树。
} // deserialize 函数结束。
private: // 私有成员区域开始。
void SerializeDfs(TreeNode* node, std::string& result) // 前序遍历序列化当前节点。
{ // SerializeDfs 函数开始。
if (node == nullptr) // 如果当前节点为空。
{ // if 代码块开始。
result += "#,"; // 空节点写成 #，后面加逗号分隔。
return; // 空节点没有左右孩子，直接返回。
} // if 代码块结束。
result += std::to_string(node->val); // 写入当前节点的值。
result += ","; // 写入逗号作为 token 分隔符。
SerializeDfs(node->left, result); // 递归序列化左子树。
SerializeDfs(node->right, result); // 递归序列化右子树。
} // SerializeDfs 函数结束。
TreeNode* DeserializeDfs(const std::string& data, int& index) // 从 data 的 index 位置开始反序列化。
{ // DeserializeDfs 函数开始。
if (index >= static_cast<int>(data.size())) // 如果 index 已经越过字符串末尾。
{ // if 代码块开始。
return nullptr; // 没有 token 可读，返回空节点。
} // if 代码块结束。
int comma = index; // comma 用来寻找当前 token 后面的逗号位置。
while (comma < static_cast<int>(data.size()) && data[comma] != ',') // 只要没到末尾且没遇到逗号。
{ // while 循环开始。
++comma; // comma 向后移动一位。
} // while 循环结束。
std::string token = data.substr(index, comma - index); // 截取当前 token。
index = comma + 1; // index 移动到下一个 token 的起始位置。
if (token == "#") // 如果当前 token 是空节点标记。
{ // if 代码块开始。
return nullptr; // 返回空指针，表示这里没有节点。
} // if 代码块结束。
TreeNode* node = new TreeNode(std::stoi(token)); // 根据 token 数值创建当前节点。
node->left = DeserializeDfs(data, index); // 递归还原当前节点的左子树。
node->right = DeserializeDfs(data, index); // 递归还原当前节点的右子树。
return node; // 返回构建好的当前节点。
} // DeserializeDfs 函数结束。
}; // 类结束。复杂度
时间复杂度：O(n)，每个真实节点和空节点标记都处理一次。 空间复杂度：O(n)，序列化字符串需要保存整棵树的信息，递归栈最坏也是 O(n)。
求二叉树右视图
标准答案
二叉树右视图就是：从树的右侧看过去，每一层能看到的节点值。
最稳的写法是 BFS 层序遍历： 每次固定当前层的节点数量 levelSize，从左到右弹出这一层节点，最后一个弹出的节点就是这一层的右视图节点。
C++ 代码
c
#include <queue> // 引入 std::queue，用来做二叉树层序遍历。
#include <vector> // 引入 std::vector，用来保存右视图答案。
struct TreeNode // 定义二叉树节点结构。
{ // 结构体开始。
int val; // 当前节点的值。
TreeNode* left; // 当前节点的左孩子指针。
TreeNode* right; // 当前节点的右孩子指针。
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造函数，初始化节点值和左右孩子。
}; // 结构体结束。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
std::vector<int> RightSideView(TreeNode* root) // 返回二叉树右视图。
{ // 函数开始。
std::vector<int> result; // result 用来保存每一层最右侧节点的值。
if (root == nullptr) // 如果根节点为空。
{ // if 代码块开始。
return result; // 空树没有右视图，直接返回空数组。
} // if 代码块结束。
std::queue<TreeNode*> queue; // 创建队列，用来进行 BFS 层序遍历。
queue.push(root); // 先把根节点加入队列。
while (!queue.empty()) // 只要队列不为空，就继续处理下一层。
{ // while 循环开始。
int levelSize = static_cast<int>(queue.size()); // 固定当前层节点数量，避免下一层节点混进来。
for (int i = 0; i < levelSize; ++i) // 遍历当前层的每一个节点。
{ // for 循环开始。
TreeNode* node = queue.front(); // 取出当前层队首节点。
queue.pop(); // 把当前节点弹出队列。
if (i == levelSize - 1) // 如果这是当前层最后一个节点。
{ // if 代码块开始。
result.push_back(node->val); // 当前层最后一个节点就是右视图节点。
} // if 代码块结束。
if (node->left != nullptr) // 如果当前节点有左孩子。
{ // if 代码块开始。
queue.push(node->left); // 把左孩子加入队列，供下一层遍历。
} // if 代码块结束。
if (node->right != nullptr) // 如果当前节点有右孩子。
{ // if 代码块开始。
queue.push(node->right); // 把右孩子加入队列，供下一层遍历。
} // if 代码块结束。
} // for 循环结束。
} // while 循环结束。
return result; // 返回右视图结果。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度：O(n)，每个节点入队、出队一次。 空间复杂度：O(w)，w 是树的最大宽度。
常见坑
右视图不是“只沿着右孩子一直走”。 如果某一层没有右孩子，左边的节点也可能成为这一层从右侧能看到的节点。
求二叉树最大路径和
标准答案
二叉树最大路径和是：在树中找一条路径，使路径上所有节点值之和最大。
注意这条路径：
可以从任意节点开始。 可以在任意节点结束。 必须沿父子节点连接。 不能重复经过同一个节点。 不要求经过根节点，也不要求到叶子节点。
核心思路
DFS 每个节点时，分清两个值：
返回给父节点的值：只能选一边，因为路径继续往父节点接时不能分叉。 更新全局答案的值：可以左边 + 当前节点 + 右边，因为路径可以在当前节点拐弯。
公式：
c
leftGain = max(0, 左子树贡献)
rightGain = max(0, 右子树贡献)
经过当前节点的最大路径 = node.val + leftGain + rightGain
返回给父节点的贡献 = node.val + max(leftGain, rightGain)C++ 代码
c
#include <algorithm> // 引入 std::max，用来比较最大路径和。
#include <climits> // 引入 INT_MIN，用来初始化全局答案。
struct TreeNode // 定义二叉树节点结构。
{ // 结构体开始。
int val; // 当前节点的值。
TreeNode* left; // 当前节点的左孩子指针。
TreeNode* right; // 当前节点的右孩子指针。
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造函数，初始化节点值和左右孩子。
}; // 结构体结束。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
int MaxPathSum(TreeNode* root) // 计算二叉树中的最大路径和。
{ // 函数开始。
answer = INT_MIN; // 初始化答案为极小值，保证全负数树也能正确处理。
MaxGain(root); // 从根节点开始 DFS，过程中更新 answer。
return answer; // 返回全局最大路径和。
} // 函数结束。
private: // 私有成员区域开始。
int answer; // answer 用来记录全局最大路径和。
int MaxGain(TreeNode* node) // 返回当前节点能向父节点提供的最大单边贡献。
{ // DFS 函数开始。
if (node == nullptr) // 如果当前节点为空。
{ // if 代码块开始。
return 0; // 空节点没有贡献，返回 0。
} // if 代码块结束。
int leftGain = std::max(0, MaxGain(node->left)); // 计算左子树贡献，如果是负数就不要。
int rightGain = std::max(0, MaxGain(node->right)); // 计算右子树贡献，如果是负数就不要。
int throughNode = node->val + leftGain + rightGain; // 计算经过当前节点并且左右都接上的路径和。
answer = std::max(answer, throughNode); // 用经过当前节点的路径更新全局答案。
int returnGain = node->val + std::max(leftGain, rightGain); // 返回给父节点时，只能选择左边或右边的一条路径。
return returnGain; // 返回当前节点能向上延伸的最大贡献。
} // DFS 函数结束。
}; // 类结束。复杂度
时间复杂度：O(n)，每个节点访问一次。 空间复杂度：O(h)，h 是树高，来自递归调用栈。
求二叉搜索树最近公共祖先
标准答案
二叉搜索树最近公共祖先，核心是利用 BST 的大小关系：
如果 p 和 q 都小于当前节点，说明答案在左子树。
如果 p 和 q 都大于当前节点，说明答案在右子树。
否则当前节点就是最近公共祖先。“否则”包括两种情况： 一种是 p 和 q 分别在当前节点两侧。 另一种是当前节点本身就是 p 或 q。
C++ 代码
c
struct TreeNode // 定义二叉树节点结构。
{ // 结构体开始。
int val; // 当前节点的值。
TreeNode* left; // 当前节点的左孩子指针。
TreeNode* right; // 当前节点的右孩子指针。
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造函数，初始化节点值和左右孩子。
}; // 结构体结束。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
TreeNode* LowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) // 求 BST 中 p 和 q 的最近公共祖先。
{ // 函数开始。
int pValue = p->val; // 取出 p 节点的值。
int qValue = q->val; // 取出 q 节点的值。
TreeNode* current = root; // 从根节点开始向下查找。
while (current != nullptr) // 只要当前节点不为空，就继续判断。
{ // while 循环开始。
int currentValue = current->val; // 取出当前节点的值。
if (pValue < currentValue && qValue < currentValue) // 如果 p 和 q 都比当前节点小。
{ // if 代码块开始。
current = current->left; // 最近公共祖先一定在左子树。
} // if 代码块结束。
else if (pValue > currentValue && qValue > currentValue) // 如果 p 和 q 都比当前节点大。
{ // else if 代码块开始。
current = current->right; // 最近公共祖先一定在右子树。
} // else if 代码块结束。
else // 否则说明 p 和 q 分居两侧，或者当前节点就是 p 或 q。
{ // else 代码块开始。
return current; // 当前节点就是最近公共祖先。
} // else 代码块结束。
} // while 循环结束。
return nullptr; // 如果树为空或节点不存在，就返回空指针。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度：O(h)，h 是树高。 空间复杂度：O(1)，迭代写法不需要递归栈。
求课程表 II
标准答案
课程表 II 本质是拓扑排序： 把课程看成图里的点，把“先修课 → 后续课程”看成有向边。 如果能把所有课程按依赖顺序排出来，就返回这个顺序；如果有环，说明课程互相依赖，返回空数组。
prerequisites[i] = [a, b] 的含义是：想学 a，必须先学 b。 所以边是：
c
b -> aC++ 代码
c
#include <queue> // 引入 std::queue，用来保存当前入度为 0 的课程。
#include <vector> // 引入 std::vector，用来保存图、入度和答案。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
std::vector<int> FindOrder(int numCourses, const std::vector<std::vector<int>>& prerequisites) // 返回一个合法课程学习顺序。
{ // 函数开始。
std::vector<std::vector<int>> graph(numCourses); // graph[x] 表示学完课程 x 后，可以继续学哪些课程。
std::vector<int> indegree(numCourses, 0); // indegree[x] 表示课程 x 还有几门先修课没完成。
for (const std::vector<int>& edge : prerequisites) // 遍历所有先修关系。
{ // for 循环开始。
int course = edge[0]; // course 是后续课程。
int prerequisite = edge[1]; // prerequisite 是先修课程。
graph[prerequisite].push_back(course); // 建边：先修课程指向后续课程。
++indegree[course]; // 后续课程的入度加一。
} // for 循环结束。
std::queue<int> queue; // 创建队列，用来存放当前可以学习的课程。
for (int course = 0; course < numCourses; ++course) // 遍历所有课程。
{ // for 循环开始。
if (indegree[course] == 0) // 如果这门课没有未完成的先修课。
{ // if 代码块开始。
queue.push(course); // 把它加入队列，表示可以先学。
} // if 代码块结束。
} // for 循环结束。
std::vector<int> result; // result 用来保存最终学习顺序。
while (!queue.empty()) // 只要还有可以学习的课程。
{ // while 循环开始。
int current = queue.front(); // 取出当前可以学习的课程。
queue.pop(); // 从队列中移除这门课。
result.push_back(current); // 把这门课加入学习顺序。
for (int next : graph[current]) // 遍历学完 current 后可以解锁的后续课程。
{ // for 循环开始。
--indegree[next]; // 后续课程少了一门未完成的先修课。
if (indegree[next] == 0) // 如果后续课程的所有先修课都完成了。
{ // if 代码块开始。
queue.push(next); // 把后续课程加入队列。
} // if 代码块结束。
} // for 循环结束。
} // while 循环结束。
if (static_cast<int>(result.size()) != numCourses) // 如果最终没有学完所有课程。
{ // if 代码块开始。
return {}; // 说明图中有环，无法完成所有课程。
} // if 代码块结束。
return result; // 返回合法的课程学习顺序。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度：O(V + E)，V 是课程数，E 是先修关系数。 空间复杂度：O(V + E)，主要是图、入度表和队列。
求账户合并
标准答案
账户合并的核心是：同名不代表同一个人，共享邮箱才代表同一个人。 所以最稳的做法是用并查集，把“账户下标”当节点，把“相同邮箱”当合并条件。
流程是：
- 遍历每个账户的邮箱。
- 用
email -> accountIndex记录邮箱第一次出现在哪个账户。 - 如果邮箱再次出现，说明两个账户属于同一个人，执行
Union。 - 最后按并查集根节点收集邮箱。
- 每组邮箱排序，再加上姓名输出。
C++ 实现
c
#include <algorithm> // 引入 sort，用来排序邮箱。
#include <numeric> // 引入 iota，用来初始化并查集父节点。
#include <string> // 引入 string，用来保存姓名和邮箱。
#include <unordered_map> // 引入 unordered_map，用来记录邮箱第一次出现在哪个账户。
#include <vector> // 引入 vector，用来保存账户和答案。
class DSU // 定义并查集类，用来合并属于同一人的账户。
{ // 类开始。
public: // 公有成员区域开始。
std::vector<int> parent; // parent[x] 表示账户 x 的父节点。
DSU(int n) : parent(n) // 构造函数，创建 n 个独立集合。
{ // 构造函数开始。
std::iota(parent.begin(), parent.end(), 0); // 初始时每个账户的父节点都是自己。
} // 构造函数结束。
int Find(int x) // 查找账户 x 所在集合的根节点。
{ // Find 函数开始。
if (parent[x] != x) // 如果 x 不是根节点。
{ // if 代码块开始。
parent[x] = Find(parent[x]); // 路径压缩，把 x 直接挂到根节点。
} // if 代码块结束。
return parent[x]; // 返回根节点。
} // Find 函数结束。
void Union(int a, int b) // 合并账户 a 和账户 b。
{ // Union 函数开始。
int rootA = Find(a); // 找到账户 a 的根节点。
int rootB = Find(b); // 找到账户 b 的根节点。
if (rootA != rootB) // 如果两个账户还不在同一个集合。
{ // if 代码块开始。
parent[rootA] = rootB; // 把 rootA 合并到 rootB 上。
} // if 代码块结束。
} // Union 函数结束。
}; // DSU 类结束。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
std::vector<std::vector<std::string>> accountsMerge(std::vector<std::vector<std::string>>& accounts) // 合并账户主函数。
{ // 函数开始。
int n = static_cast<int>(accounts.size()); // 获取账户数量。
DSU dsu(n); // 创建并查集。
std::unordered_map<std::string, int> emailOwner; // 记录每个邮箱第一次出现在哪个账户。
for (int i = 0; i < n; ++i) // 遍历每个账户。
{ // 外层循环开始。
for (int j = 1; j < static_cast<int>(accounts[i].size()); ++j) // 遍历当前账户的邮箱，跳过姓名。
{ // 内层循环开始。
const std::string& email = accounts[i][j]; // 取出当前邮箱。
if (emailOwner.find(email) == emailOwner.end()) // 如果邮箱第一次出现。
{ // if 代码块开始。
emailOwner[email] = i; // 记录邮箱属于当前账户。
} // if 代码块结束。
else // 如果邮箱之前出现过。
{ // else 代码块开始。
dsu.Union(i, emailOwner[email]); // 共享邮箱，合并两个账户。
} // else 代码块结束。
} // 内层循环结束。
} // 外层循环结束。
std::unordered_map<int, std::vector<std::string>> groups; // 按根节点收集邮箱。
for (const auto& pair : emailOwner) // 遍历所有出现过的邮箱。
{ // for 循环开始。
const std::string& email = pair.first; // 取出邮箱。
int owner = pair.second; // 取出邮箱第一次所属账户。
int root = dsu.Find(owner); // 找到这个账户最终所属集合。
groups[root].push_back(email); // 把邮箱放进对应集合。
} // for 循环结束。
std::vector<std::vector<std::string>> result; // 创建答案数组。
for (auto& group : groups) // 遍历每个合并后的集合。
{ // for 循环开始。
int root = group.first; // 取出集合根节点。
std::vector<std::string>& emails = group.second; // 取出这个集合里的邮箱。
std::sort(emails.begin(), emails.end()); // 按字典序排序邮箱。
std::vector<std::string> merged; // 创建一个合并后的账户。
merged.push_back(accounts[root][0]); // 第一个元素放姓名。
merged.insert(merged.end(), emails.begin(), emails.end()); // 后面追加排序后的邮箱。
result.push_back(merged); // 把当前合并账户加入答案。
} // for 循环结束。
return result; // 返回最终答案。
} // 函数结束。
}; // Solution 类结束。复杂度
总邮箱数量记为 E，账户数量记为 N。并查集合并接近 O(E)，最后排序邮箱通常是主要成本，整体可以看成 O(E log E)。空间复杂度是 O(E + N)。
求单调栈问题
标准答案
单调栈不是某一道题，而是一类题的套路：用栈保存“还没找到答案的下标”，当当前元素能解决栈顶元素的问题时，就弹栈并填写答案。
典型关键词是：
- 右边第一个更大元素
- 右边第一个更小元素
- 每日温度
- 接雨水
- 柱状图最大矩形
核心思路
如果题目问“右边第一个更大元素”，通常维护一个单调递减栈。 栈里放下标，不放值，因为最后要回填答案。
比如 nums = [2, 1, 2, 4, 3]：
当遍历到 4 时，发现它比栈顶的 2 大，也比更前面的 2 大，所以这些元素的“右边第一个更大值”就是 4。
C++ 代码：求每个元素右边第一个更大值
c
#include <stack> // 引入 stack，用来维护单调栈。
#include <vector> // 引入 vector，用来保存输入数组和答案数组。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
std::vector<int> nextGreaterToRight(const std::vector<int>& nums) // 求每个元素右边第一个更大的值。
{ // 函数开始。
int n = static_cast<int>(nums.size()); // 获取数组长度。
std::vector<int> ans(n, -1); // 初始化答案数组，默认没有更大值就是 -1。
std::stack<int> st; // 创建栈，栈里存数组下标，不直接存值。
for (int i = 0; i < n; ++i) // 从左到右遍历数组。
{ // for 循环开始。
while (!st.empty() && nums[i] > nums[st.top()]) // 当前值比栈顶下标对应的值更大，说明栈顶找到答案。
{ // while 循环开始。
int index = st.top(); // 取出栈顶下标。
st.pop(); // 弹出这个已经找到答案的下标。
ans[index] = nums[i]; // 当前 nums[i] 就是 index 右边第一个更大值。
} // while 循环结束。
st.push(i); // 当前下标还没找到右边更大值，先入栈等待。
} // for 循环结束。
return ans; // 返回每个位置右边第一个更大值。
} // 函数结束。
}; // 类结束。复杂度
时间复杂度是 O(n)，因为每个下标最多入栈一次、出栈一次。 空间复杂度是 O(n)，最坏情况下所有元素都在栈里。
面试记忆
单调栈的本质是：栈里存还没结算的人，当前元素一旦足够大或小，就帮栈顶结算答案。
求双指针问题
标准答案
双指针是一种用两个位置一起扫描数组、字符串或链表的技巧。它的核心不是“固定模板”，而是：通过移动两个指针，缩小搜索范围，避免暴力枚举。
常见三类：
- 对撞指针：
left从左走，right从右走，常用于有序数组、回文、盛水问题。 - 快慢指针：
fast扫描，slow写入或定位，常用于移动零、去重、链表找环。 - 滑动窗口：左右指针维护一个区间，常用于子串、子数组问题。
C++ 代码：有序数组两数之和
c
#include <vector> // 引入 vector，用来保存数组和返回结果。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
std::vector<int> twoSumSorted(const std::vector<int>& nums, int target) // 在有序数组中找两个数，使它们的和等于 target。
{ // 函数开始。
int left = 0; // 左指针从数组开头开始。
int right = static_cast<int>(nums.size()) - 1; // 右指针从数组末尾开始。
while (left < right) // 只要左右指针没有相遇，就继续查找。
{ // while 循环开始。
int sum = nums[left] + nums[right]; // 计算当前左右两个数的和。
if (sum == target) // 如果当前和正好等于目标值。
{ // if 代码块开始。
return {left, right}; // 返回两个数的下标，这里使用 0-based 下标。
} // if 代码块结束。
if (sum < target) // 如果当前和小于目标值。
{ // if 代码块开始。
++left; // 左指针右移，让较小的数变大，从而让 sum 变大。
} // if 代码块结束。
else // 如果当前和大于目标值。
{ // else 代码块开始。
--right; // 右指针左移，让较大的数变小，从而让 sum 变小。
} // else 代码块结束。
} // while 循环结束。
return {-1, -1}; // 如果没有找到答案，返回无效下标。
} // 函数结束。
}; // Solution 类结束。复杂度
时间复杂度是 O(n)，因为每个指针最多走完整个数组一次。 空间复杂度是 O(1)，只用了两个指针。
常见坑
无序数组不能直接用对撞指针做两数之和；如果数组无序，通常用哈希表，或者先排序并保留原下标。
求前缀和问题
标准答案
前缀和的核心是：先把从开头到当前位置的和存起来，之后求任意区间和时，只需要两个前缀相减。
基础公式：
c
prefix[i] = nums[0] + nums[1] + ... + nums[i - 1]
sum(l, r) = prefix[r + 1] - prefix[l]比如 nums = [1, 2, 3, -2, 5]：
c
prefix = [0, 1, 3, 6, 4, 9]
区间 [1, 2] 的和 = prefix[3] - prefix[1] = 6 - 1 = 5C++ 代码：子数组和等于 K
c
#include <unordered_map> // 引入 unordered_map，用来统计某个前缀和出现过多少次。
#include <vector> // 引入 vector，用来保存输入数组。
class Solution // 定义解题类。
{ // 类开始。
public: // 公有成员区域开始。
int subarraySum(std::vector<int>& nums, int k) // 统计和等于 k 的连续子数组数量。
{ // 函数开始。
std::unordered_map<int, int> prefixCount; // prefixCount[x] 表示前缀和 x 出现过多少次。
prefixCount[0] = 1; // 空前缀和为 0，先出现 1 次，用来处理从下标 0 开始的子数组。
int prefixSum = 0; // prefixSum 表示当前遍历到的位置之前的累计和。
int answer = 0; // answer 用来记录满足条件的子数组数量。
for (int num : nums) // 依次遍历数组中的每个元素。
{ // for 循环开始。
prefixSum += num; // 更新当前前缀和。
int need = prefixSum - k; // 如果以前出现过 need，那么中间这段子数组的和就是 k。
if (prefixCount.find(need) != prefixCount.end()) // 判断 need 这个前缀和以前是否出现过。
{ // if 代码块开始。
answer += prefixCount[need]; // 出现过几次，就说明有几个子数组以当前位置结尾且和为 k。
} // if 代码块结束。
++prefixCount[prefixSum]; // 把当前前缀和加入哈希表，供后面的元素使用。
} // for 循环结束。
return answer; // 返回满足条件的子数组数量。
} // 函数结束。
}; // Solution 类结束。复杂度
时间复杂度是 O(n)，每个元素只遍历一次。 空间复杂度是 O(n)，哈希表最坏会保存很多不同的前缀和。
常见坑
有负数时，不要硬套滑动窗口，因为窗口扩大不一定让和变大，窗口缩小也不一定让和变小。前缀和 + 哈希表更通用。