主题
数据结构与算法
一、复杂度与选型总表
1. 复杂度速查
Q: 常见复杂度从低到高怎么排?实际性能只看大 O 吗?
大 O 只描述增长趋势,常数和缓存局部性会改变实际胜负——同样是 O(n),
vector往往比list快一个数量级(见 §一.3)。
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)。
2. 各结构操作复杂度总表
| 结构 | 查找 | 插入 | 删除 | 有序 | 典型用途 |
|---|---|---|---|---|---|
| 数组 | O(1) 下标 / O(n) 值 | O(n) | O(n) | 否 | 连续存储、随机访问 |
vector | O(1) 下标 / O(n) 值 | 尾部均摊 O(1),中间 O(n) | 尾部 O(1),中间 O(n) | 否 | 默认容器 |
| 链表 | O(n) | O(1)(已知位置) | O(1)(已知位置) | 否 | 频繁中间插删、引用稳定 |
deque | O(1) | 头尾 O(1),中间 O(n) | 头尾 O(1),中间 O(n) | 否 | 队列、滑动窗口 |
| 栈 / 队列 | 仅顶 / 队首 O(1) | O(1) | O(1) | 否 | LIFO / FIFO |
| 哈希表 | 平均 O(1),最坏 O(n) | 平均 O(1),扩容 O(n) | 平均 O(1) | 否 | 纯查找、去重 |
红黑树 map/set | O(log n) | O(log n) | O(log n) | 是 | 有序、范围查询 |
| 跳表 | 平均 O(log n),最坏 O(n) | 平均 O(log n) | 平均 O(log n) | 是 | Redis zset |
| 堆 | 极值 O(1),任意值 O(n) | O(log n) | O(log n) | 偏序 | TopK、定时器 |
| BST 二叉搜索树 | 平均 O(log n),最坏 O(n) | 平均 O(log n) | 平均 O(log n) | 是 | 有序动态集 |
| AVL / 红黑树 | O(log n) | O(log n) | O(log n) | 是 | 平衡有序集 |
| B+ 树 | O(log_m n) | O(log_m n) | O(log_m n) | 是 | 磁盘索引 |
| Trie | O(L),L 为串长 | O(L) | O(L) | 前缀有序 | 前缀匹配 |
| 并查集 | 近似 O(1)(α(n)) | 近似 O(1) | 近似 O(1) | 否 | 连通性 |
易错点:堆只有堆顶是 O(1),查找任意元素仍是 O(n);红黑树和哈希表都能去重,但只有红黑树能按顺序遍历。
3. 缓存友好性:数组为什么常胜链表
Q: 都说链表插入 O(1),为什么工程里还是优先用
vector?
因为链表的 O(1) 前还有一个隐藏的 O(n) 定位,而定位过程缓存极不友好。
- CPU 按 64 字节缓存行加载数据,数组顺序访问内核会触发设备到内核缓冲区的缓存,一次 cache miss 能摊到十几个元素上。
- 链表节点分散在堆上,每走一步都可能是一次 cache miss(缓存失效需要重新在设备中读)。
- 因此遍历
vector通常比list快 5~10 倍;即使中间插入,vector的大块memmove也常常快过链表的逐个找位置。
选型准则:默认 vector;只有在「已经持有迭代器、频繁中间插删、且需要引用 / 迭代器稳定」时才用 list。
4. 均摊分析
Q:
vector::push_back均摊 O(1) 是怎么来的?某一次为什么可能是 O(n)?
按 2 倍扩容时,插入 n 个元素的总搬运次数为 1 + 2 + 4 + ... + n < 2n,摊到 n 次插入上就是 O(1)。
- 哈希表 rehash 同理:一次迁移 n 个元素,摊到 n 次插入仍是 O(1)。
- 均摊 ≠ 每次:触发扩容的那一次确实要 O(n);对延迟敏感的实时系统应提前
reserve。
二、线性结构
1. 数组 vs 链表
Q: 数组和链表各自适合什么场景?
| 维度 | 数组 / vector | 链表 |
|---|---|---|
| 内存布局 | 连续 | 分散,每个节点额外存指针 |
| 随机访问 | O(1) | O(n) |
| 中间插删 | O(n)(要搬移) | O(1)(已知位置) |
| 缓存友好 | 好 | 差 |
| 迭代器 / 引用稳定性 | 扩容后全失效 | 除被删节点外稳定 |
| 典型场景 | 绝大多数场景 | 频繁 splice、引用稳定 |
链表三大基本功:
- dummy 哨兵:头节点可能被删 / 被换时,用
dummy.next = head统一处理。 - 快慢指针:找中点、判环、找环入口、找倒数第 k 个。
- 三指针:反转链表时
prev / cur / next缺一不可,先存next再改指针。
2. vector 底层与扩容
Q:
vector的底层结构是什么?size和capacity有什么区别?
三个指针:
text
start_ finish_ end_of_storage_
| | |
v v v
+----+----+----+----+----+----+----+----+
| 1 | 2 | 3 | | | | | |
+----+----+----+----+----+----+----+----+
<---- size ----> <---- 未构造 ---->
<-------------- capacity ------------->size() = finish_ - start_:已构造元素个数。capacity() = end_of_storage_ - start_:已申请内存能容纳的个数。- 扩容流程:申请新内存 → 搬移旧元素 → 析构并释放旧内存。libstdc++ 按 2 倍,MSVC 按 1.5 倍,目的都是让均摊 O(1)。
| 操作 | 作用 | 常见坑 |
|---|---|---|
reserve(n) | 只改 capacity,不改变 size | 越界访问仍是 UB |
resize(n) | 改 size,多出的元素值初始化 / 析构 | 会真正构造对象 |
clear() | size 置 0 | 不释放 capacity |
emplace_back(args) | 原地构造,省一次临时对象 | 参数要能直接构造 T |
push_back(v) | 先构造 v 再移动 / 拷贝 | 有移动构造时开销已很小 |
实现见 01_动态数组.cpp。
3. vector 迭代器失效
Q:
vector哪些操作会导致迭代器失效?
| 操作 | 失效范围 | 说明 |
|---|---|---|
push_back / emplace_back | 未扩容:end();扩容:全部 | 扩容后元素地址全变 |
reserve | 重新分配则全部 | capacity 变大也可能搬移 |
insert / erase | 插入 / 删除点及其之后 | 后面的元素整体搬移 |
resize | 扩容则全部 |
准则:修改容器后重新获取迭代器;循环中删除用 it = v.erase(it);需要跨修改保存位置时用下标而不是迭代器。
4. list 与 deque 底层
Q:
list和deque的底层是什么?为什么queue默认用deque?
list:双向链表,节点存 prev / next / value。
- 已知位置的插入 / 删除 O(1)
list::sort用的是归并排序(链表做不到随机访问)。- 除被删除节点外,迭代器和引用都稳定;代价是每节点两个指针、缓存极差。
deque:中控 map + 固定大小缓冲区(libstdc++ 每块 512 字节)。
- 头尾插入 / 删除均摊 O(1);随机访问 O(1),但要经过「中控数组 → 缓冲区」两次间接。
- 迭代器失效规则特殊:头尾插入只失效迭代器,引用 / 指针仍有效;中间插入使全部失效。
queue需要 O(1) 的pop_front,vector做不到,所以标准选择deque;stack理论上可用vector(缓存更好),但标准统一用deque。
5. 栈与队列
Q: 栈和队列分别有哪些典型应用?
| 结构 | 典型应用 |
|---|---|
| 栈 | 括号匹配、表达式求值(操作数栈 + 运算符栈)、函数调用栈、DFS、撤销 |
| 队列 | BFS、任务队列、消息队列、滑动窗口、生产者-消费者缓冲区 |
循环队列判满:容量为 cap 的数组,常用 (tail + 1) % cap == head 判满,代价是牺牲一个槽位;也可以额外维护 size 计数,避免浪费。
6. 单调栈与单调队列
Q: 单调栈 / 单调队列解决什么问题?为什么是 O(n)?
单调栈:求「下一个更大 / 更小元素」、接雨水、柱状图最大矩形。
cpp
// 下一个更大元素:维护一个从栈底到栈顶递减的栈
vector<int> nextGreater(vector<int>& a) {
int n = a.size();
vector<int> res(n, -1);
stack<int> st; // 存下标
for (int i = 0; i < n; ++i) {
while (!st.empty() && a[st.top()] < a[i]) {
res[st.top()] = a[i];
st.pop();
}
st.push(i);
}
return res;
}单调队列:滑动窗口最大值。队列存下标,保证值从队首到队尾递减;队首过期就弹出,新元素入队前从队尾弹掉更小的。
cpp
// 滑动窗口最大值:单调队列(队头—队尾 递减)
// k:滑动窗口的大小
// res:存每个窗口的最大值
vector<int> maxSlidingWindow(vector<int>& a, int k) {
int n = a.size();
vector<int> res;
deque<int> dq; // 存下标
for (int i = 0; i < n; ++i) {
// 1) 队头过期(滑出窗口)
if (!dq.empty() && dq.front() <= i - k)
dq.pop_front();
// 2) 队尾维护单调递减 (新元素进队前,把队尾比它小的全踢掉,哪怕踢空)
// 为什么不从队头开始?因为队列是"下标递增 + 值递减",所以"又新又小、会被新元素压掉"的必然堆在队尾
while (!dq.empty() && a[dq.back()] < a[i])
dq.pop_back();
dq.push_back(i);
// 3) 窗口成型后输出队头(当前最大)
if (i >= k - 1) res.push_back(a[dq.front()]);
}
return res;
}- 每个元素最多进队一次、出队一次,所以是 O(n)。
- 典型题:滑动窗口最大值、最短子数组、接雨水。
7. 环形队列与 SPSC
Q: 环形队列怎么判空判满?无锁 SPSC 队列靠什么保证正确?
- 判空判满:
head == tail表示空;若用「牺牲一个槽位」法,(tail + 1) & mask == head表示满。 - SPSC(单生产者单消费者)无锁:生产者只写
tail,消费者只写head,各自读对方的下标。- 自己写的下标用
relaxed;发布数据用release;读取对方下标用acquire,形成 happens-before。
- 自己写的下标用
- 工程落点:
io_uring的 SQ / CQ 环、日志系统的双 buffer、线程池任务队列。
实现见 20_无锁环形队列.cpp;伪共享靠 alignas(64) 把两个下标分到不同缓存行,内存序只需记住「写端 release、读端 acquire」的配对。
8. 链表高频手撕
Q: 链表题有哪些固定套路?
| 题目 | 关键点 |
|---|---|
| 反转链表 | prev / cur / next 三指针,先存 next 再改指向 |
| 判断有环 | 快慢指针,相遇即有环 |
| 找环入口 | 相遇后一个指针回到 head,两指针同速再相遇即入口 |
| 合并两个有序链表 | dummy 哨兵 + 尾指针 |
| 删除倒数第 k 个 | 快指针先走 k 步,再同步走 |
| 相交链表 | 长度差对齐;或双指针走完各自换头,总路程相等 |
| 复制带随机指针的链表 | 哈希表存「原节点 → 新节点」;或穿插复制后拆链 |
| K 个一组翻转 | dummy + 每组先找尾 + 组内反转 + 接回 |
| 链表排序 | 快慢指针找中点 + 归并,O(n log n)、O(1) 额外空间 |
| 回文链表 | 找中点 + 反转后半 + 比较(可再反转恢复) |
实现见 02_链表.cpp。
9. KMP
Q: KMP 的
next/pi数组是什么含义?为什到 O(n+m)?
pi[i] 表示 pat[0..i] 的最长相等真前缀 / 真后缀长度。
- 暴力匹配失配时文本指针要回退,最坏 O(nm)。
- KMP 失配时文本指针 i 不回退,只把模式串指针
j跳到pi[j-1],利用已经匹配过的信息。 - 预处理 O(m),匹配 O(n),总 O(n+m);空间 O(m)。
cpp
// 构建 pi
vector<int> pi(m, 0);
for (int i = 1, j = 0; i < m; ++i) {
while (j > 0 && pat[i] != pat[j]) j = pi[j - 1];
if (pat[i] == pat[j]) ++j;
pi[i] = j;
}应用:子串查找;最短循环节 n - pi[n-1](若 n % (n - pi[n-1]) == 0 则由该节循环构成)。
实现见 24_KMP算法.cpp。
三、哈希
1. 哈希表原理与冲突
Q: 哈希冲突有哪些解决方案?链地址法和开放定址法怎么选?
| 链地址法 | 开放定址法 | |
|---|---|---|
| 做法 | 每个桶挂一个链表 / 红黑树 | 冲突后按规则探测下一个空位 |
| 装载因子 | 可以 > 1 | 必须 < 1(否则无空位) |
| 删除 | 直接摘链 | 需要墓碑标记,否则断链 |
| 缓存 | 差(节点分散) | 好(连续探测) |
| 代表 | std::unordered_map(libstdc++ 桶 + 节点) | Java HashMap 早期、Python dict |
std::unordered_map的节点在 rehash 时不移动,所以引用 / 指针稳定,迭代器失效——这是高频细节。
实现见 07_哈希表.cpp。
2. 装载因子与 rehash
Q: 什么是装载因子?rehash 时迭代器和引用会怎样?
- 装载因子 = 元素数 / 桶数。太高冲突多,太低浪费内存;
- 超过阈值触发 rehash:桶数扩到约 2 倍并选下一个质数,重新计算所有元素位置,单次 O(n)。
- rehash 后所有迭代器失效,但指向元素的引用 / 指针仍然有效(节点本身没搬家)。
- 已知规模时先
reserve(n),可以避免多次 rehash。
3. unordered_map vs map
Q:
map和unordered_map有什么区别?怎么选?(高频)
| 维度 | map | unordered_map |
|---|---|---|
| 底层 | 红黑树 | 哈希桶 + 节点 |
| 查找 / 插入 / 删除 | O(log n) | 平均 O(1),最坏 O(n) |
| 是否有序 | 按 key 有序 | 无序 |
| 迭代器稳定性 | 除被删元素外稳定 | rehash 后全部失效 |
| 引用稳定性 | 稳定 | 稳定 |
| 内存 | 每节点额外指针 + 颜色 | 桶数组 + 节点,通常更大 |
| 适用 | 需要排序、范围、前驱后继 | 纯查找、去重、计数 |
追问点:
map的 key 是const,不能直接改——改了会破坏树的有序性。C++17 可用extract取出节点句柄,改 key 后再insert,避免重新分配。operator[]在 key 不存在时会插入默认值;只想查询用find/at,at越界抛std::out_of_range。unordered_map最坏 O(n) 来自恶意构造的哈希冲突;需要防攻击时换自定义哈希或改用map。
4. 位图
底层结构: 由连续的内存空间(通常是数组)构成,数组的每个元素是基本整数类型
核心思想: 用**1个比特(bit)**来标记某个元素的状态(0或1,存在或不存在)
内存映射: 假设用
int(32位)数组存储,数组的一个元素arr[i]就可以表示 32 个状态。- 第
k个元素在数组中的位置:arr[k / 32] - 它在该元素内部的第几位:
k % 32
- 第
读写(查/插/删):通过位运算(如
|置 1,& ~置 0)操作,时间复杂度均为 O(1)。空间消耗极小;但只能记录状态,且如果数据极其稀疏(比如只有1和10000000),会浪费大量空间。
Q: 40 亿个整数去重,内存只有 1GB,怎么做?
用位图:每个数用 1 bit 表示「出现过」,40 亿 × 1 bit = 512MB,可以放下,遍历一遍即可完成去重。
实现见 22_位图.cpp。
5. 布隆过滤器
Q: 布隆过滤器的原理是什么?为什么有假阳性没有假阴性?
- 用 m 个 bit、k 个独立哈希函数;插入时把 k 个位置置 1,查询时 k 个位置全为 1 才可能存在。
- 没有假阴性:插入过的元素对应位一定被置 1。
- 有假阳性:别的元素可能恰好把这 k 位置 1;误判率随元素增多而上升。
- 不支持删除(会把别人的位清掉);需要删除时用计数布隆过滤器。
工程用途:Redis缓存穿透(先挡掉一定不存在的 key)、URL 去重、数据库避免无效磁盘查询。
实现见 21_布隆过滤器.cpp。
6. 海量数据题
Q: 上亿数据放不进内存,怎么统计 / 去重 / TopK?
四步框架:
- 估算内存:数据量 × 单条大小 vs 可用内存。
- hash 分流:按 key 哈希到多个小文件,保证相同 key 落在同一文件。
- 单机处理:每个小文件用哈希表 / 位图 / 堆独立处理。
- 合并结果:小文件的结果再汇总(TopK 用小顶堆)。
| 题目 | 方案 |
|---|---|
| 40 亿 QQ 号去重 | 位图(值域允许时);否则 hash 分流 + 哈希表 |
| 100 亿个整数找 TopK | hash 分流 → 每片维护大小为 K 的小顶堆 → 合并 |
| 两个大文件求共同 URL | hash 分流,同 key 同文件,再逐片求交集 |
| 出现次数最多的 IP | hash 分流 + unordered_map 计数,各片取最大再合并 |
| 判断 URL 是否在 100 亿集合中 | 布隆过滤器(允许假阳性) |
| 海量数据全排序 | 外部排序:分块排序 + 多路归并 |
关键:不要试图一次装进内存;同 key 必须同分片,否则无法局部聚合。
(因为比如7这个数字,出现4次,但被分散了,那就无法统计出4次了)
四、树
1. 二叉树遍历
Q: 前序、中序、后序、层序遍历的递归和迭代写法?
- 递归:访问语句放在不同位置,就是不同遍历。
- 前序迭代:栈先压右再压左,弹出即访问。
- 中序迭代:一路向左入栈,弹栈访问,再转向右子树。
- 后序迭代:按「根 → 右 → 左」遍历再整体反转;或用两个栈。
- 层序:队列 + 每层先记录
size,一次处理一层。
cpp
// 中序迭代:左 → 根 → 右
vector<int> inorder(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur || !st.empty()) {
while (cur)
{
st.push(cur);
cur = cur->left;
}
cur = st.top();
st.pop();
res.push_back(cur->val);
cur = cur->right;
}
return res;
}- 时间 O(n);递归栈 O(h),层序队列 O(w),h 为树高、w 为最大宽度。
- 易错点:后序不能简单「根右左」直接输出,必须反转;中序迭代的
cur = cur->right在访问之后。
实现见 09_二叉树遍历.cpp。
2. BST 二叉搜索树
Q: 二叉搜索树的增删查怎么做?删除节点有哪几种情况?
- 性质:左子树全部小于根,右子树全部大于根;中序遍历有序。
- 删除分三种:
- 叶子:直接删。
- 只有一个孩子:孩子顶替。
- 两个孩子:用中序后继(右子树最小值)或前驱替换值,再删除后继节点。
- 查找 / 插入 / 删除平均 O(log n),最坏 O(n)——按有序序列插入会退化成链表。
高频追问:
- 验证 BST 不能只比较父子,要传上下界:左子树
< root且> lower,右子树> root且< upper。 - 第 k 小:中序遍历计数。
- BST 的最近公共祖先:从根开始,两个值都小于根就往左,都大于就往右,否则当前就是 LCA。
- 插入顺序决定树高;工程上需要平衡,才有 AVL / 红黑树。
实现见 10_二叉搜索树.cpp。
4. AVL 树
BST(二叉搜索树)和 AVL 树的区别一句话:AVL 树是一棵“会自己保持平衡”的 BST。
Q: AVL 树怎么保持平衡?四种旋转分别对应什么情况?
平衡因子 = 左子树高 - 右子树高,取值只能是 -1 / 0 / 1,否则旋转。
| 失衡类型 | 场景 | 处理 |
|---|---|---|
| LL | 左孩子的左子树过高 | 对节点右旋一次 |
| RR | 右孩子的右子树过高 | 对节点左旋一次 |
| LR | 左孩子的右子树过高 | 先对左孩子左旋,再对节点右旋 |
| RL | 右孩子的左子树过高 | 先对右孩子右旋,再对节点左旋 |
- 查找、插入、删除都 O(log n),树高严格 O(log n)。
- 比红黑树更「矮胖」,查找更快;但插入 / 删除要维护严格平衡,旋转更多。
- 适合读多写少的场景;
std::map选择的是红黑树,不是 AVL。
实现见 11_AVL树.cpp。
5. 红黑树
Q: 红黑树的性质是什么?为什么
map和 epoll 都用红黑树,而不用 AVL?
五条性质:
- 每个节点非红即黑。
- 根节点是黑色。
- 叶子(NIL)是黑色。
- 红节点的两个孩子必须是黑色(不能有连续红节点)。
- 从任一节点到其所有叶子的路径上,黑节点数量相同。
由性质 4、5 可推出:最长路径不超过最短路径的 2 倍,树高 ≤ 2 log₂(n+1),所以增删查都是 O(log n)。
| 维度 | AVL | 红黑树 |
|---|---|---|
| 平衡程度 | 严格(高度差 ≤ 1) | 宽松(黑高平衡) |
| 查找 | 略快 | 略慢 |
| 插入 / 删除 | 旋转多 | 旋转少、重着色多 |
| 适用 | 读多写少 | 读写混合、通用 |
std::map/set、Linux epoll 的 fd 管理、CFS 调度器都用红黑树:要有序、要 O(log n) 最坏保证、写操作不能太贵。- 不用哈希:需要范围查询 / 前驱后继;不用 AVL:写操作旋转太频繁。
6. B 树与 B+ 树
Q: 为什么数据库索引用 B+ 树,不用红黑树或哈希?(高频)
| 维度 | 红黑树 | B 树 | B+ 树 |
|---|---|---|---|
| 分叉 | 二叉 | 多叉 | 多叉 |
| 数据位置 | 所有节点 | 所有节点 | 只在叶子,内部节点只存 key |
| 叶子链表 | 无 | 无 | 有,支持范围扫描 |
| 树高(百万级) | ~20 | ~3 | ~3 |
| 磁盘 I/O | 每层一次随机 I/O | 少 | 更少 |
核心原因是磁盘:B+ 树一个节点就是一页(InnoDB 默认 16KB),扇出可达上千,百万数据只需 3~4 层,也就是 3~4 次 I/O;红黑树 20 层就是 20 次随机 I/O。
- B+ 树 vs B 树:内部节点不存数据 → 同样一页能放更多 key → 扇出更大、树更矮;叶子有链表 → 范围查询、排序、分页友好;所有查询都走到叶子,性能稳定。
- 为什么不用哈希:哈希只能等值查询,无法范围查询、排序、最左前缀匹配。
- InnoDB:聚簇索引的叶子存整行;二级索引的叶子存主键,查非索引列要回表;覆盖索引可以避免回表。
7. 堆
Q: 堆的底层为什么用数组?建堆为什么是 O(n) 而不是 O(n log n)?
堆是完全二叉树,可以按层序存进数组,不需要指针:
text
parent(i) = (i - 1) / 2
left(i) = 2 * i + 1
right(i) = 2 * i + 2- 插入:放到数组末尾,然后上浮,O(log n)。
- 删除堆顶:堆顶与末尾交换,弹出末尾,再对堆顶下沉,O(log n)。
- 建堆:从最后一个非叶子节点
n/2 - 1开始向前下沉。总代价是各节点高度之和,约 2n,所以 O(n)。 - 堆排序:建堆 O(n) + n 次取堆顶 O(n log n),原地、不稳定。
priority_queue:底层 vector + make_heap / push_heap / pop_heap;默认大顶堆
小顶堆写 priority_queue<int, vector<int>, greater<int>>;
不支持迭代器遍历,也不支持修改堆中任意元素。
实现见 08_二叉堆.cpp、18_堆排序.cpp。
8. TopK 与对顶堆
Q: 海量数据取 TopK 有哪几种做法?数据流的中位数怎么维护?
| 方法 | 时间 | 空间 | 适用 |
|---|---|---|---|
| 排序后取前 k | O(n log n) | O(n) | 数据量小 |
| 大小为 k 的小顶堆 | O(n log k) | O(k) | 流式 / 海量数据 |
| 快速选择 quickselect | 平均 O(n),最坏 O(n²) | O(1) | 允许打乱数组、一次性 |
| 分治 + 每片堆 | O(n log k) | O(k × 分片) | 单机内存放不下 |
- 第 k 大:维护小顶堆,堆顶就是当前第 k 大;比堆顶大才替换。
- 数据流中位数:左边大顶堆存较小一半,右边小顶堆存较大一半;保持两堆大小差 ≤ 1,中位数取堆顶。
- 合并 K 个有序链表:小顶堆存每个链表当前节点,O(N log k)。
实现见 08_二叉堆.cpp、26_合并K个有序链表.cpp。
9. Trie(前缀树/字典树)
Q: Trie 的结构和复杂度?适合什么场景?
- 每个节点代表一个字符,从根到某节点的路径是一个前缀;节点用
end标记是否为完整单词。 - 插入 / 查询 / 前缀判断都是 O(L),L 为字符串长度,与集合大小无关。
- 代价是内存:每个节点若开 26 个指针就很重;可用
unordered_map<char, Node*>或压缩成基数树 / 压缩 Trie。 - 场景:自动补全、敏感词过滤、IP 路由前缀匹配、拼写检查、词频统计。
实现见 12_前缀树.cpp。
10. 跳表
Q: 跳表的原理是什么?Redis 为什么用跳表而不是红黑树?
- 在有序链表上建多层索引,每层以概率
p(Redis 取 1/4)向上晋升;查找从最高层开始,逐层下降。 - 期望时间 O(log n),最坏 O(n)(随机性导致);空间期望 O(n)。
- 相比红黑树:实现简单、范围查询天然友好、并发加锁粒度小;代价是随机性和额外指针内存。
- Redis zset 同时用跳表 + 哈希表:哈希负责 O(1) 查 score,跳表负责按 score 排序和范围查询(
ZRANGE)。
实现见 23_跳表.cpp。
五、排序与查找
2. 快速排序
Q: 快排的原理、最坏情况、如何优化?
- 选 pivot,
partition把小的放左、大的放右,再递归两侧。 - 最坏 O(n²):数组已经有序且总选第一个 / 最后一个元素做 pivot,每次划分极不平衡。
- 优化:
- 随机 pivot 或三数取中,避免有序输入退化。
- 小区间(如 < 16)改用插入排序,减少递归开销。
- 先递归较小的一侧,较大的一侧尾递归 / 迭代,栈深控制在 O(log n)。
- 大量重复元素用三路划分(小于 / 等于 / 大于),避免全相等时退化。
- 平均 O(n log n),原地、不稳定;实际最快是因为内存连续、常数小、缓存友好。
实现见 16_快速排序.cpp。
3. 归并排序
Q: 归并排序的特点?为什么链表排序适合归并?
- 分治:递归排序两半,再线性合并两个有序数组。
- 时间稳定 O(n log n),稳定,空间 O(n)。
- 链表:合并只需改指针,不需要额外数组,可以做到 O(1) 额外空间;快排对链表不友好(无法随机访问)。
- 求逆序对:合并时若
a[i] > a[j],则a[i..mid]都大于a[j],一次贡献mid - i + 1个逆序对。 - 外部排序的基础:内存里排好块,再多路归并。
实现见 17_归并排序.cpp。
4. 堆排序
Q: 堆排序的过程和优缺点?
- 建堆 O(n)。
- 每次把堆顶与末尾交换,堆大小减一,再下沉,重复 n 次。
- 时间 O(n log n),空间 O(1),不稳定。
- 优点是最坏也有 O(n log n) 且原地;缺点是缓存不友好(跳跃访问),实际通常慢于快排。
std::sort在快排递归过深时会切换到堆排兜底,就是为了这个最坏保证。
实现见 18_堆排序.cpp。
5. std::sort 的内省排序
Q:
std::sort用的是什么算法?为什么它不稳定还能这么快?
std::sort 用内省排序(introsort):
- 主体是快排;
- 递归深度超过
2 log n时切换成堆排,保证最坏 O(n log n); - 小区间切换成插入排序。
- 三者结合:快排的平均速度 + 堆排的最坏保证 + 插入排序的小数组低开销。
- 不稳定;需要稳定排序用
std::stable_sort(归并,尽量复用缓冲区)。 std::partial_sort用堆;std::nth_element用快速选择。
6. 外部排序
Q: 数据量大于内存时怎么排序?
- 分块:每次读入能放进内存的一块,内部排序后写回磁盘,形成若干有序「归并段」。
- 多路归并:用大小为 k 的小顶堆合并 k 个有序段,边读边写。
- 重复直到只剩一个有序文件。
六、图
1. 图的存储
Q: 邻接矩阵和邻接表怎么选?
| 邻接矩阵 | 邻接表 | |
|---|---|---|
| 空间 | O(V²) | O(V + E) |
| 判断边是否存在 | O(1) | O(度数) |
| 遍历某点邻居 | O(V) | O(度数) |
| 适合 | 稠密图、Floyd | 稀疏图、大多数题 |
- 无向图一条边要存两次;带权图在边上加
w。 - 笔试也常用链式前向星(数组模拟邻接表):
head[u]+next+to+w,避免大量new,缓存更友好。
2. BFS / DFS
Q: BFS 和 DFS 分别适合什么?复杂度多少?
| BFS | DFS | |
|---|---|---|
| 数据结构 | 队列 | 递归栈 / 显式栈 |
| 特点 | 按层扩展,无权图最短路 | 一条路走到黑,适合连通性 / 路径 / 环 |
| 空间 | O(V)(最坏一层) | O(h)(递归深度) |
| 复杂度 | O(V + E) | O(V + E) |
- 网格题(岛屿数量、腐烂的橘子、迷宫)把每个格子看成节点,上下左右是边。
- 易错点:BFS 应在入队时标记 visited,否则同一节点会被重复入队,复杂度退化。
- 无权图最短路用 BFS;带权图才用 Dijkstra。
3. 拓扑排序
Q: 拓扑排序的两种写法?如何判断有环?有什么用?
只适用于有向无环图(DAG)。
- Kahn(BFS):统计入度,入度为 0 的入队;每次弹出一个、把它指向的节点入度减 1;若最终输出的节点数 < n,说明有环。
- DFS:三色标记(0 未访问 / 1 访问中 / 2 已完成);遇到「访问中」的节点说明有环;后序结果的逆序就是拓扑序。
- 应用:课程表、编译依赖、任务调度、包管理器的依赖解析。
实现见 14_拓扑排序.cpp。
4. Dijkstra
Q: Dijkstra 的原理?为什么不能处理负权边?复杂度多少?
- 贪心:每次从「未确定」的节点中取
dist最小的,它的最短路已经确定,然后用它去松弛邻居。 - 用
priority_queue<pair<dist, node>, ..., greater<>>,弹出时若d > dist[u]就跳过(惰性删除,代替 decrease-key)。 - 复杂度 O((V + E) log V),适合非负权。
- 负权边会破坏贪心前提:已经「确定」的节点之后可能被一条负边改小,所以 Dijkstra 不成立;负权用 Bellman-Ford / SPFA。
实现见 15_Dijkstra最短路.cpp。
5. Bellman-Ford / SPFA / Floyd
Q: 负权最短路和全源最短路分别用什么算法?
| 算法 | 负权边 | 负环检测 | 复杂度 | 适用 |
|---|---|---|---|---|
| Bellman-Ford | 支持 | 支持 | O(VE) | 单源、有负权 |
| SPFA | 支持 | 支持 | 平均较快,最坏 O(VE) | 单源、稀疏图(竞赛常用) |
| Floyd | 支持 | 支持(对角线 < 0) | O(V³) | 全源、小图 |
- Bellman-Ford:对所有边松弛
V-1轮;第V轮还能松弛,说明存在负环。 - SPFA:只把被松弛过的节点入队,是 Bellman-Ford 的队列优化;最坏仍会退化,出题人可构造数据卡它。
- Floyd:
dp[k][i][j]表示只允许经过前 k 个点的最短路,三重循环;代码短,适合 V ≤ 500。
6. 最小生成树
Q: Prim 和 Kruskal 有什么区别?分别适合什么图?
| Prim | Kruskal | |
|---|---|---|
| 思路 | 从一个点开始,每次加一条连接「已选 / 未选」的最短边 | 所有边排序,依次加入不成环的边 |
| 数据结构 | 优先队列 | 并查集 |
| 复杂度 | O(E log V) | O(E log E) |
| 适合 | 稠密图 | 稀疏图 |
- 正确性都来自切分性质:横跨任意切分的最小边一定属于某棵 MST。
- Kruskal 判环用并查集:两端已连通就跳过。
7. 并查集
Q: 并查集怎么实现?为什么近似 O(1)?
parent[x]指向父节点;根节点parent[x] == x。- 路径压缩:查找时把路径上的节点直接挂到根上。
- 按秩 / 按大小合并:矮树挂到高树下,避免退化成链。
- 两者结合后,单次操作的摊还复杂度是 O(α(n)),α 是反阿克曼函数,实际可视为常数。
应用:连通分量、Kruskal、冗余连接、账户合并、等式方程可满足性、岛屿数量(也可 DFS)。
cpp
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // 路径减半
x = parent[x];
}
return x;
}实现见 13_并查集.cpp。
七、设计题与并发结构
1. LRU Cache (Least Recently Used 最近最少使用缓存淘汰算法)
最近被访问过的数据,未来更可能再次被访问;很久没被访问的数据,未来不太可能被访问。
Q: 设计一个 O(1) 的 LRU,为什么必须是「哈希表 + 双向链表」?(高频)
- 哈希表:O(1) 查找数据:
get哈希定位节点,把它移到链表头(最近使用)。 - 双向链表:O(1) 把访问过的节点
put移到链表头,淘汰时删除链表尾(最久未使用)。 - 为什么不用单链表:删除尾部需要前驱,双向链表才能 O(1)。
- 为什么不用数组:中间移动 / 删除 O(n)。
- 为什么不用
map:map是 O(log n),哈希才能 O(1)。
并发追问:全局加锁简单竞争大;分片(sharded LRU)把 key 哈希到多个独立 LRU,各自加锁,是工程常见做法。
实现见 03_LRU缓存.cpp。
2. LFU Cache (Least Frequently Used Cache 最不经常使用缓存)
当缓存满了,优先淘汰访问频率最低的数据;如果频率相同,通常再按 LRU(最久未使用) 淘汰。
Q: LFU 怎么做到 O(1)?和 LRU 有什么区别?
- 哈希表
key -> node:快速定位缓存节点 - 哈希表
freq -> 双向链表:每个频率对应一个链表,链表内按 LRU 排序 - 维护一个
minFreq:记录当前最小频率,淘汰时从minFreq对应链表尾部删除 - 节点通常保存:key, value, freq
操作逻辑:
- Get(key):不存在返回 -1;存在则频率 +1,并移动到新频率链表的头部
- Put(key, value):
- key 存在:更新 value,频率 +1
- key 不存在:若容量满,删除
minFreq链表尾部节点;插入新节点,频率为 1,并更新minFreq = 1
| LRU | LFU | |
|---|---|---|
| 淘汰依据 | 最久未使用 | 使用频率最低(同频再按 LRU) |
| 优点 | 实现简单,适应访问模式变化 | 保护高频热点 |
| 缺点 | 偶发批量访问会冲刷热点 | 历史频率僵化,新热点难上位 |
LFU 的工程问题:频率只增不减,旧热点会一直占位;常见解法是定期衰减频率。
实现见 04_LFU缓存.cpp。
3. 最小栈
在普通栈的基础上,额外支持 O(1) 时间复杂度获取当前栈中的最小值。
普通栈支持:
push(x):入栈pop():出栈top():看栈顶empty():是否为空
最小栈还要支持:
getMin():返回当前栈中最小元素
Q: 如何让
push / pop / top / getMin都是 O(1)?
用两个栈:
dataStack:存所有数据minStack:存当前对应的最小值
规则:
push(x):dataStack入栈 xminStack入栈min(x, 当前最小值)
pop():- 两个栈同时弹出
top():返回dataStack栈顶getMin():返回minStack栈顶
实现见 05_最小栈.cpp。
4. 两个栈实现队列
Q: 两个栈怎么实现队列?复杂度怎么分析?
in栈负责入队,out栈负责出队。- 出队时若
out为空,把in全部倒入out,顺序正好反过来。 - 摊还 O(1):每个元素最多被倒入一次、弹出一次;但单次
pop最坏 O(n)(倒栈那一次)。 - 反过来「两个队列实现栈」:每次 push 后把队列前面的元素转到后面,或者用两个队列来回倒。
实现见 06_双栈队列.cpp。
5. O(1) 随机插入 / 删除
Q: 设计一个支持 O(1) 插入、删除、随机取元素的结构。
vector + unordered_map<value, index>:
插入:追加到
vector尾部,记录下标。删除:把待删元素与末尾元素交换,
pop_back,更新被交换元素的下标。随机取:
nums[rand() % nums.size()]。「swap-remove」是数组 O(1) 删除的通用技巧。
有重复元素时哈希要存
value -> set<index>,或者改用计数。
实现见 25_随机集合.cpp。
6. 合并 K 个有序链表
Q: 合并 K 个有序链表有哪几种做法?
- 小顶堆:每个链表当前节点入堆,每次取最小,再把它的
next入堆;O(N log k),N 为总节点数。 - 分治归并:两两合并,O(N log k),常数更小、不需要堆。
- 朴素做法每次比较 k 个头节点是 O(Nk),不可取。
实现见 26_合并K个有序链表.cpp。
7. 线程安全队列
Q: 有界阻塞队列怎么实现?为什么
wait必须带谓词?
mutex+ 两个condition_variable(非空 / 非满)+ 有界queue。push:队列满则等待「非满」;入队后notify_one唤醒消费者。pop:队列空则等待「非空」;出队后notify_one唤醒生产者。wait(lock, predicate)必须带谓词:条件变量存在虚假唤醒,醒来看谓词不成立要继续等。- 执行任务时绝不能持锁,否则线程池退化成串行。
实现见 27_线程安全队列.cpp;线程池就是「生产者-消费者 + 线程复用」:提交任务加锁入队,工作线程 wait 取任务,执行时释放锁。
8. 无锁队列与 ABA
Q: 无锁队列怎么实现?ABA 问题是什么?
- SPSC:见 §二.7,单生产者单消费者只需两个原子下标 + acquire/release。
- MPMC:多生产者多消费者要用 CAS 循环(如 Michael-Scott 队列),复杂度高很多。
- ABA:线程读到值 A,准备 CAS 时值被改成 B 又改回 A,CAS 误以为没变。解法:带版本号的 tagged pointer、 hazard pointer。
- 选型:无锁适合临界区极短、竞争极高的场景;一般业务用互斥锁更简单可靠。
内存序只需记住:自己写的下标用 relaxed,发布数据用 release,读取对方下标用 acquire;CAS 的 ABA 用版本号或 hazard pointer 解决。
9. 定时器最小堆(项目常问)
Q: 网络库的定时器为什么常用最小堆?
- 定时器需要频繁「插入超时任务」和「取最早到期任务」:堆的插入 O(log n)、取最小 O(1),正好匹配。
- 取消定时器可用惰性删除:标记取消,等它到堆顶时再丢弃,避免在堆中查找 O(n)。
- 对比:有序链表插入 O(n);红黑树插入 O(log n) 但常数更大、实现复杂;时间轮适合大量定时器、精度要求不极端的场景。
- 工程组合:
timerfd负责「什么时候醒」,最小堆负责「下一个该处理谁」。
典型组合:epoll 负责监听 fd 事件,timerfd 负责报时,最小堆负责选出下一个到期连接。