📋 摘要
- C++ 基本算法面试高频问答，每题保留回答重点与扩展知识
- 详细原理解析与代码示例见 03-Resources/cpp/C++ 基本算法
- 持续补充中
1. 快速排序的原理和实现？
📋 回答重点
- 分治 + 原地：选 pivot，partition 把小于放左、大于放右，再递归左右区间。
- 核心是 partition：
i指向「第一个 >= pivot」的位置，扫描 j，遇小则交换a[i]、a[j]并i++。 - 平均 O(n log n)，最坏 O(n²)（有序且 pivot 取到极值），空间 O(log n) 递归栈。
- 不稳定（partition 交换破坏相对顺序）。
扩展知识
- 避免最坏情况：随机选 pivot 或三数取中。
std::sort是 introsort：快排 + 插入排序（小规模）+ 堆排序（递归过深）混合。- 详细讲解：03-Resources/cpp/C++ 基本算法
2. 归并排序的原理和实现？
📋 回答重点
- 分治：先递归对半分，再合并两个有序子数组。
- 合并时
a[i] <= a[j]先取左边，<=保证稳定。 - 时间 O(n log n)（任何情况），空间 O(n)（临时数组，非原地）。
- 稳定排序。
扩展知识
- 适合外部排序、求逆序对（合并时统计左>右的数量）。
- 链表归并可 O(1) 额外空间。
- 详细讲解：03-Resources/cpp/C++ 基本算法
3. 堆排序的原理？
📋 回答重点
- 用大顶堆（数组模拟完全二叉树，孩子
2i+1、2i+2）。 - O(n) 建堆后，反复交换堆顶与末尾、缩小堆、下沉，得到升序。
- 时间 O(n log n)，空间 O(1) 原地。
- 不稳定（堆顶与末尾交换破坏顺序）。
扩展知识
- Top-K 用大小为 K 的小顶堆，O(n log K)。
std::priority_queue默认大顶堆，小顶堆用greater<int>。- 详细讲解：03-Resources/cpp/C++ 基本算法
4. 冒泡、插入、选择排序的对比？
📋 回答重点
- 冒泡：相邻比较交换，最好 O(n)（加提前终止）、最坏 O(n²)，稳定。
- 插入：把当前元素插入前面有序区，最好 O(n)、最坏 O(n²)，稳定。
- 选择：每次选最小放到前面，任何情况 O(n²)，不稳定。
- 三者空间都是 O(1)。
扩展知识
- 小规模（几十以内）插入排序常优于快排，是
std::sort底层小规模策略。 - 选择排序不稳定是跨距交换导致。
- 详细讲解：03-Resources/cpp/C++ 基本算法
5. 排序算法的稳定性总结？
📋 回答重点
- 稳定：冒泡、插入、归并、计数、基数、桶（视实现）。
- 不稳定：选择、快速、堆、希尔。
- 稳定 = 相等元素排序后相对顺序不变，用于多关键字依次排序。
- 时间/空间：快排/堆排 O(n log n) O(1) 不稳定；归并 O(n log n) O(n) 稳定。
扩展知识
- C++ 的
std::stable_sort内部用归并实现稳定排序。 - 不稳定原因各不同：快排是 partition 交换、选择是跨距交换、堆是堆顶与末尾交换。
- 详细讲解：03-Resources/cpp/C++ 基本算法
6. 二分查找的实现和边界处理？
📋 回答重点
- 前提：有序数组，每次把区间减半。
- 闭区间
[l,r]用l <= r，mid = l + (r-l)/2防溢出。 a[mid] < target则l = mid+1，否则r = mid-1。- 时间 O(log n)，空间 O(1)。
扩展知识
- 半开区间
[l,r)用l < r，注意两种写法的收缩方向。 std::binary_search/lower_bound/upper_bound是现成接口。- 详细讲解：03-Resources/cpp/C++ 基本算法
7. 二分查找变体（找第一个/最后一个等于 target）？
📋 回答重点
- lower_bound = 第一个
>= target；upper_bound = 第一个> target。 - 找最后一个等于 target =
upper_bound - 1。 - 出现次数 =
upper_bound - lower_bound。 - 半开区间
[l,r)+l<r，收缩方向决定找的是哪个边界。
扩展知识
- STL 的
lower_bound/upper_bound返回迭代器，distance得下标。 - 二分答案类问题也复用这套「找第一个满足条件」模板。
- 详细讲解：03-Resources/cpp/C++ 基本算法
8. 双指针技巧？适用场景？
📋 回答重点
- 两个指针同向或相向移动，把 O(n²) 暴力降到 O(n)。
- 左右指针（相向）：有序数组两数之和、三数之和、接雨水。
- 快慢指针（同向）：链表找中点、判环、原地去重/移动元素。
- 前提常是有序或满足单调性。
扩展知识
- 双指针本质是用指针单调移动代替一层循环。
- 与滑动窗口是同一思想的不同形态。
- 详细讲解：03-Resources/cpp/C++ 基本算法
9. 滑动窗口？适用场景？
📋 回答重点
- 维护
[left,right]窗口，right 扩张、left 收缩。 - 外层 for 扩张 right，内层 while 收缩 left 到满足条件。
- 时间 O(n)（两指针各移动 O(n) 次），非 O(n²)。
- 用于连续子数组/子串满足条件的最长/最短问题。
扩展知识
- 经典题：无重复字符最长子串、和为 target 的最短子数组、异位词匹配。
- 字符计数可用
unordered_map或长度为 256 的数组优化。 - 详细讲解：03-Resources/cpp/C++ 基本算法
10. 贪心算法的思想？适用场景？
📋 回答重点
- 每步做当前局部最优，期望得到全局最优。
- 前提：贪心选择性质 + 最优子结构。
- 无回溯，通常比 DP 快，但不总是最优。
- 经典：活动选择（按结束时间排序）、哈夫曼编码、找零（特殊面额）。
扩展知识
- 0/1 背包、部分找零组合不能用贪心，需 DP。
- Dijkstra、Prim/Kruskal 本质也是贪心。
- 详细讲解：03-Resources/cpp/C++ 基本算法
11. 动态规划的思想？如何写状态转移方程？
📋 回答重点
- 拆成重叠子问题，保存结果避免重复计算。
- 三要素：状态定义、转移方程、边界条件。
- 写方程步骤：定义 dp 含义 → 找更小子问题推导 → 定 base case 与遍历顺序。
- 可滚动数组/一维化优化空间。
扩展知识
- 先用「递归 + 记忆化」想清楚，再转成迭代自底向上。
- 经典：背包、LIS、编辑距离、状态压缩 DP。
- 详细讲解：03-Resources/cpp/C++ 基本算法
12. 经典 DP：01 背包问题？
📋 回答重点
- n 件物品（重量 w、价值 v），容量 W，每件只能选或不选。
dp[j]= 容量 j 的最大价值，dp[j] = max(dp[j], dp[j-w[i]]+v[i])。- 一维数组必须逆序遍历容量，保证每件只用一次。
- 时间 O(nW)，空间 O(W)。
扩展知识
- 完全背包（物品无限）改为正序遍历。
- 二维
dp[i][j]压成一维是因为新值只依赖上一行。 - 详细讲解：03-Resources/cpp/C++ 基本算法
13. 经典 DP：最长递增子序列 LIS？
📋 回答重点
dp[i]= 以 a[i] 结尾的 LIS 长度，dp[i] = max(dp[j]+1)（j<i 且 a[j]<a[i]）。- DP 版 O(n²)；二分优化 O(n log n)。
- 二分版维护
tails：长度 i 的 LIS 的最小末尾，用 lower_bound 替换。 - 空间 O(n)。
扩展知识
- 求长度用二分，求具体序列用 DP 记录前驱。
- 变体：俄罗斯套娃信封、最少划分递增子序列。
- 详细讲解：03-Resources/cpp/C++ 基本算法
14. 回溯算法的思想？全排列问题？
📋 回答重点
- 暴力搜索 + 剪枝，本质是 DFS。
- 三件事：做选择、递归、撤销选择。
- 全排列：固定 start，交换
nums[start]与nums[i]递归再换回。 - 复杂度 O(n·n!)，空间 O(n) 递归栈。
扩展知识
- 框架：
for 选择 in 选择列表 { 做选择; backtrack; 撤销 }。 - 含重复元素先排序，用 used 数组或相邻剪枝去重。
- 详细讲解：03-Resources/cpp/C++ 基本算法
15. 位运算的常用技巧？
📋 回答重点
x & 1判奇偶；x << 1/x >> 1乘除 2。x & (x-1)去掉最低位的 1（可统计 1 的个数、判 2 的幂）。x & -x取最低位的 1（lowbit，树状数组用）。x ^ y ^ y == x，异或法交换两数。
扩展知识
- 状态压缩 DP 用 bitmask 表示集合，
__builtin_popcount数 1。 - 位运算 O(1) 时间，常作常数优化与哈希/权限位。
- 详细讲解：03-Resources/cpp/C++ 基本算法
16. KMP 算法的原理？
📋 回答重点
- 用前缀函数 next（最长相等前后缀）在失配时不回退主串指针。
- 失配时
j = next[j-1]，主串 i 不回退。 - 时间 O(n+m)，空间 O(m)。
- 适用于单模式串匹配。
扩展知识
m - next[m-1]是字符串最小循环节长度。std::string::find内部用更复杂的算法，KMP 是基础。- 详细讲解：03-Resources/cpp/C++ 基本算法
17. BFS 和 DFS 的应用场景？
📋 回答重点
- DFS：走到底再回溯，用栈（递归），找所有解/连通性/判环/拓扑。
- BFS：按层扩散，用队列，求无权图最短路径。
- 两者时间 O(V+E)，空间 O(V)。
- 求最少步数选 BFS，求所有路径选 DFS。
扩展知识
- BFS 经典：层序遍历、岛屿数量、最小步数；DFS 经典：连通分量、回溯类。
- 记忆化搜索 = DFS + DP。
- 详细讲解：03-Resources/cpp/C++ 基本算法
18. Dijkstra 最短路径算法？
📋 回答重点
- 每次选距离最小且未确定的节点，用它的边松弛邻居。
- 堆优化（priority_queue）后 O((V+E) log V)。
- 要求边权非负；有负权用 Bellman-Ford。
- 贪心思想，与 Prim 代码结构几乎相同。
扩展知识
- 堆里可能有重复节点，用
d > dist[u]跳过过期条目。 - BFS 是无权图最短路，Dijkstra 是带权非负图最短路。
- 详细讲解：03-Resources/cpp/C++ 基本算法
19. 拓扑排序？
📋 回答重点
- 对 DAG 排序，使每条边
u->v满足 u 在 v 前。 - Kahn 算法（BFS + 入度）：不断取出入度为 0 的节点。
- 时间 O(V+E)，空间 O(V)。
- 若拓扑序列长度 < V，说明图中有环。
扩展知识
- 另一种实现：DFS 后序遍历取逆序。
- 应用：课程表、任务调度、编译依赖。
- 详细讲解：03-Resources/cpp/C++ 基本算法
20. 最小生成树 Prim 和 Kruskal？
📋 回答重点
- MST：连通加权无向图的边权和最小的生成树。
- Prim：从点出发，每次选连接已选集合与外部的最小边（类似 Dijkstra），稠密图优。
- Kruskal：边排序 + 并查集贪心选不形成环的最小边，稀疏图优。
- Prim O(V²) 或 O(E log V)，Kruskal O(E log E)。
扩展知识
- Kruskal 用并查集判环；Prim 的 dist 是「到集合最小边」而非「到源最短距离」。
- 应用：网络布线、管道铺设最小成本。
- 详细讲解：03-Resources/cpp/C++ 基本算法
21. 单调栈和单调队列的原理？适用场景？
📋 回答重点
- 单调栈：栈内元素值保持单调（递增/递减），新元素入栈前弹出破坏单调性的栈顶，常用于「找左/右边第一个更大或更小的元素」。
- 单调队列：双端队列保持单调，队头是当前窗口的最值，常用于「滑动窗口最值」。
- 两者本质都是「用单调性把暴力 O(n²) 降到 O(n)」：每个元素最多入/出一次。
- 单调栈典型题：每日温度、下一个更大元素、接雨水、柱状图最大矩形。
- 单调队列典型题：滑动窗口最大值、带下标跨度限制的最优子序列。
扩展知识
- 单调栈分「单调递增栈」和「单调递减栈」，取决于求「更大」还是「更小」，比较方向反过来即可。
- 单调队列分两步：队尾弹出维护单调性、队头弹出过期元素（超出窗口范围）。
- 虽然有两层循环，但总复杂度仍是 O(n)，因为每个元素至多被弹出一次。
- 详细讲解：03-Resources/cpp/C++ 基本算法
22. Bellman-Ford 和 Floyd 最短路径算法的原理？
📋 回答重点
- Bellman-Ford：单源最短路，对所有边松弛 n-1 轮，可处理负权边、能检测负环，时间 O(VE)。
- 第 n 轮仍能松弛即说明存在负环（最短路最多 n-1 条边）。
- Floyd：多源最短路，DP 中转点思想
d[i][j] = min(d[i][j], d[i][k] + d[k][j])，O(V³)，可处理负权但不可有负环。 - 对比 Dijkstra：Dijkstra 要求非负权且是贪心；有负权改用 Bellman-Ford（或 SPFA）。
- Floyd 三层循环顺序固定为 k（中转点）、i、j，k 必须放最外层。
扩展知识
- SPFA 是 Bellman-Ford 的队列优化版，平均更快但最坏仍 O(VE)，可能被构造数据卡掉。
- Floyd 可顺带求传递闭包、求最小环；适合小规模图（V ≤ 几百）的任意两点最短路。
- 详细讲解：03-Resources/cpp/C++ 基本算法