01. 数据结构与算法面试基础（深挖版）¶

算法题在 C++ 面试里经常被误解成"刷题速度赛"。其实真正拉开差距的，往往不是你背了多少题型，而是你能不能在面试里把一个问题讲清楚：

数据规模多大

复杂度为什么这样选

还有没有别的方案

常数、内存、局部性会不会影响实际表现

所以这一章不只是列算法名词，而是把高频数据结构和解题思路放回"工程化表达"里讲。

本章建议按“先理解知识主线，再练问答表达，最后吃透边界条件”的顺序阅读：

先把复杂度分析、排序对比、栈/队列/链表

再展开哈希表、堆、二叉树、动态规划、BFS/DFS

最后把TopK 问题、红黑树 vs AVL、工程化选择

先把这一章的知识骨架搭起来¶

算法题虽然经常以“写代码”形式出现，但真正稳定拿分靠的是 建模能力、复杂度意识和表达能力。数组、链表、栈、队列、堆、树、图、哈希、并查集、DP、回溯、双指针，这些不是一堆散题型，而是不同问题结构对应的通用解法工具。

建议把算法题按“如何识别问题特征”来学：有序和区间问题常联想到双指针或二分，最优子结构联想到 DP，层次遍历联想到 BFS，关系合并联想到并查集。面试时别急着上代码，先把输入规模、时间空间约束和候选方案讲清楚。

这样你即使题没见过，也能靠方法论往前推进。

第一部分：先把概念和主线讲清楚¶

进入问答前，先把最小前置知识补齐¶

算法题看起来在考编码，其实更稳定的拿分方式是先建立建模框架：这题的数据规模多大、核心约束是什么、最像哪类已知结构、能接受的时间空间复杂度在哪个级别。

数组、链表、栈、队列、堆、树、图、哈希、并查集、DP、回溯、双指针，不是一堆散技能，而是对不同问题结构的通用回应。先从“问题像什么”去想，再落到具体实现，面试里会更稳。

1. 常见时间复杂度有哪些？¶

O(1)
O(logN)
O(N)
O(NlogN)
O(N^2)
O(2^N)

面试注意¶

不仅要会背复杂度，还要能说清：

最好 / 平均 / 最坏情况
额外空间复杂度
实际常数因子

为什么这题基础但很重要？¶

因为很多方案看上去复杂度更优，但如果：

常数太大
内存爆炸
实现复杂度过高

实际未必更适合。

一句总结¶

复杂度不是唯一指标，它是解题筛选的第一层，不是最终工程结论。

2. 数组和链表区别？¶

数组¶

连续内存
随机访问快
中间插删慢

链表¶

非连续内存
插删灵活（已知节点位置时）
随机访问慢
cache locality 差

为什么这题不能只答"插删和访问"？¶

因为现代机器上，数组的连续内存优势往往非常大：

cache 友好
预取效果好
指针追逐少

高分点¶

链表理论上插删灵活，但现代 CPU 下，连续内存带来的局部性收益常常让数组在真实场景里表现更好。

3. 栈和队列区别？¶

栈：后进先出（LIFO）
队列：先进先出（FIFO）

为什么这题还会被问？¶

因为很多算法本质上就是在考"你有没有看出它背后的访问顺序模型"：

DFS 常配栈
BFS 常配队列
单调栈、滑动窗口队列更是高频经典题型

4. 堆是什么？¶

标准回答¶

这里算法里的"堆"是特殊完全二叉树，不是内存管理里的 heap。

常见用途¶

优先队列
TopK
中位数维护
调度系统

为什么堆高频？¶

因为它特别适合处理：

动态维护最值
只关心部分有序结果
海量数据流中的 TopK 问题

面试高分点¶

堆的价值不在于"整体有序"，而在于它能用较低成本维护局部最值结构。

第二部分：围绕高频追问继续展开¶

5. 快排为什么快？最坏情况是什么？¶

标准回答¶

快速排序平均复杂度 O(NlogN)，常数因子小、局部性较好，所以实践中很快。

最坏情况¶

划分极不均衡时退化为 O(N^2)。

为什么平均快但最坏危险？¶

因为快排的性能高度依赖 pivot 划分质量：

划分均衡 → 递归树高度较低
划分极差 → 递归接近退化链表

高分点¶

快排在工程里常见，不只是因为复杂度漂亮，更因为它局部性和常数通常都不错；但面试里一定要主动提最坏退化和 pivot 选择问题。

6. 哈希表为什么快？¶

标准回答¶

理想情况下通过哈希函数直接定位桶位置，平均查找复杂度接近 O(1)。

追问点¶

哈希冲突如何解决
拉链法 vs 开放寻址
rehash 代价是什么

为什么不能说"哈希就是 O(1)"？¶

因为：

冲突会拉长查找路径
rehash 会带来整体搬迁代价
哈希质量和负载因子会影响实际性能

一句总结¶

哈希表快在平均访问路径短，但不是无条件稳定 O(1)。

7. 二叉搜索树、AVL、红黑树区别？¶

面试简答¶

普通 BST 可能退化成链表
AVL 更平衡，查询更稳，但旋转更多
红黑树平衡要求较弱，综合插删性能好，工程上更常用

为什么红黑树更常见？¶

因为工程里往往更看重：

综合插删查性能
实现复杂度和旋转成本平衡

而不是单纯追求查询最优高度。

8. 什么是动态规划？¶

标准回答¶

动态规划用于解决具有重叠子问题和最优子结构的问题，通过保存子问题结果避免重复计算。

三步法¶

定义状态
写状态转移
确定初始化与遍历顺序

为什么很多人会 DP 题一看就懵？¶

因为本质难点不是"会不会背模板"，而是：

你能不能找到合适状态
你能不能识别决策之间的依赖关系

面试高分点¶

动态规划真正难的是建模，不是写循环；一旦状态定义不对，后面全都错。

9. BFS 和 DFS 区别？¶

BFS¶

层序搜索
适合最短路（无权图）
通常用队列

DFS¶

深度搜索
适合回溯、连通块、拓扑相关场景
通常用递归或栈

为什么面试喜欢问这题？¶

因为它很适合继续追：

为什么无权最短路用 BFS
什么时候 DFS 更自然
递归深度爆了怎么办

一句总结¶

BFS 和 DFS 不是"两个遍历模板"，而是两种不同的状态扩展顺序。

第三部分：把难点、边界和代价吃透¶

10. TopK 怎么做？¶

常见答案¶

小顶堆：适合海量数据流
快速选择：适合一次性离线求解
桶排序：适合值域较小场景

为什么这题很经典？¶

因为它很适合考"按数据规模选方案"：

在线 / 离线
内存是否够
是否需要有序输出
K 相对 N 是大是小

高分点¶

TopK 没有唯一标准答案，关键是根据输入规模、在线性、是否要求最终排序来选方案。

11. 一组典型追问链¶

复杂度为什么不能只背一个 O？
数组和链表在现代 CPU 上谁更占优势？
堆为什么适合 TopK 和调度？
快排为什么平均快、最坏却会翻车？
哈希表为什么快、什么时候会慢？
AVL 和红黑树为什么工程上更常选后者？
动态规划最难的部分是什么？
BFS / DFS 怎么根据题意选？
TopK 为什么要按在线/离线场景区分？

12. 一份更像面试现场的总结回答¶

算法面试真正考的不是你能不能把题背出来，而是你是否能根据问题规模和数据特征选出合适结构。数组和链表的差异要落到局部性和访问模式，堆和哈希表的优势要落到维护最值与平均访问路径，快排和红黑树要落到工程中的平均性能与稳定性权衡，动态规划则要落到状态建模能力。真正成熟的回答，应该把"复杂度、内存、常数、场景"一起考虑，而不是只报一个 big-O。

13. 复习建议¶

至少做到：

复杂度题会主动补最好/平均/最坏和空间复杂度
数组/链表题会主动提局部性
TopK、哈希、堆题会主动按数据规模选方案
DP 题会先讲状态定义和转移
BFS/DFS 不只会写模板，还会讲适用场景

做到这里，算法题就不再只是刷题模板，而开始像真正的问题求解能力。