在数据库、分布式系统与 AI Infra 研发面试中,算法题与系统设计题很少是割裂的两张皮。面试官往往先抛出一道看似普通的数组、图或缓存题,紧接着把某个假设改掉——例如把“正数数组”改成“允许负数”,把“单机 LRU”改成“带父子依赖的显存块淘汰”,或者追问“如果同一任务递归请求自己的 Key 怎么防死锁”——以此观察候选人是否真正看穿了数据结构背后的物理约束与边界条件。
下面把近期系统梳理的并发控制、显存调度、图论最短路以及 18 个高频算法范式沉淀成一份可随时翻阅的实战笔记,重点写清每一类问题在什么地方会踩坑、条件一变模型如何切换,以及工程代码落地时的关键细节。
一、 窗口求和与单调性边界:为什么同样的题会有四种写法
先看一个极小的反例:nums = [-5, 4],元素类型都是 1,要求子数组内最多包含 m = 1 种类型且和最大。
如果直接套用“右指针扩窗、超限缩左指针、合法就更新答案”的双指针写法,当右指针走到 4 时,窗口 [0, 1] 本身只有 1 种类型,完全合法,于是双指针会停在左边界 0 并算出 -1。但只要把前面的 -5 丢掉,只取 [1, 1],就能得到更优的 4。
这个反例直接把窗口求和题劈成了四个完全不同的模型:
| 题型变体 | 核心约束 | 是否怕负数 | 正确做法 | 时间 / 空间 |
|---|---|---|---|---|
1. 定长 k 最大和 | 长度固定为 k | 不怕 | 定长滑窗:sum += a[i] - a[i - k] | $O(n)$ / $O(1)$ |
2. 定长 k 且种类 $\le m$ | 长度固定 + 种类上限 | 不怕 | 定长滑窗 + 类型计数表,仅合法时更新 | $O(n)$ / $O(\min(k, \text{种类数}))$ |
| 3. 变长且种类 $\le m$(非负) | a[i] >= 0 | 要求非负 | 同向双指针扩右缩左,直接取当前窗口和 | $O(n)$ / $O(\text{种类数})$ |
| 4. 变长且种类 $\le m$(含负数) | 允许 a[i] < 0 | 不怕 | 双指针定最左合法界 l + 前缀和 + 单调递增队列 | $O(n)$ / $O(n)$ |
之所以定长窗口不怕负数,是因为长度被锁死为 k,没有“缩短窗口丢掉负前缀”的自由度;而在变长窗口里,种类数 distinct <= m 对窗口长度有单调性,但窗口和只有在元素非负时才对长度有单调性。一旦允许负数,双指针只能用来求每个右端点 r 对应的最左合法边界 l——即起点 j 必须落在 [l, r] 内。子数组和写成 prefix[r + 1] - prefix[j] 后,问题就转化为在滑动区间 [l, r] 里找最小的 prefix[j],用一个单调递增双端队列就能维持 $O(n)$。
同样受“负数破坏单调性”影响的经典题对比,还有 209. 长度最小的子数组、560. 和为 K 的子数组 和 862. 和至少为 K 的最短子数组:
- 209 题(全正数,和 $\ge K$ 最短):单调性成立,直接同向双指针 $O(1)$ 空间。
- 560 题(含负数,和 $== K$ 计数):单调性失效,用前缀和 + 哈希表查历史
prefix - K出现次数,别忘了初始化prefix_count[0] = 1。 - 862 题(含负数,和 $\ge K$ 最短):单调性失效,用前缀和 + 单调递增双端队列:队头一旦满足
prefix[i] - prefix[dq.front()] >= K就结算并直接出队(后面只会更长,不可能更优);队尾入队前把prefix[dq.back()] >= prefix[i]的点全部弹出(又靠左、起点前缀和又大,彻底被支配)。
实战写代码时还有三个高频边界:无解或全负数时不能把 best 初始化为 0(应使用 None / std::optional 或 -inf);计数归零时要显式从哈希表删除或递减 distinct;当 m >= 总种类数 时,非负数组退化为全局和,含负数数组则退化为 Kadane 最大子数组和(53. 最大子数组和)。
二、 进程内请求合并(SingleFlight):并发共享与递归自锁破局
进程内请求合并器(SingleFlight)的目标很明确:同一个 key 的并发请求只由第一个到达的 Leader 执行一次计算,其余 Waiter 共享结果或异常,完成后不保留缓存。
主干做法是用一把锁保护 key -> Future/Call 映射:Leader 注册条目后立刻释放锁去执行计算,Waiter 拿到共享句柄后也在锁外等待;计算结束无论成功还是抛异常,都唤醒所有 Waiter,再加锁按指针或 Future 身份比对清理映射(if inflight.get(key) is fut: del inflight[key]),防止误删后续新发起的同名请求。
面试必追问的三个深水区
- 单个 Waiter 被取消或超时,不能连带取消共享任务
在 Pythonasyncio中,直接await asyncio.wait_for(fut, timeout)会在超时时把底层fut一起cancel()掉,导致 Leader 和其他 Waiter 全部陪葬。正确写法是套一层asyncio.shield(fut)隔离取消信号。而在 C++ 多线程实现中,Waiter 只是在std::condition_variable::wait_for(或std::shared_future::wait_for)上阻塞,超时退出不会修改共享Call的状态,天然具备shield语义。 - 同一任务递归请求自己的 Key,如何避免永久等待?
如果 Leader 在执行fn()期间又以相同key调回do(),它会看到key仍在inflight中而等待自己尚未完成的Future,形成自环死锁(间接环A -> B -> A同理)。- Python
asyncio:使用contextvars.ContextVar维护当前调用链的活跃key集合(frozenset)。ContextVar沿await链自动传播且create_task会自动拷贝上下文,不同并发请求天然隔离,入口命中即抛出ReentrantKeyError(或按业务要求旁路直调)。 - C++ 多线程:使用
thread_local std::unordered_set<Key>配合 RAII Guard 在执行fn()前后登记/移除当前线程活跃key。但如果fn()内部把子任务提交到线程池,C++ 没有语言级自动透传,需显式拷贝上下文或依赖wait_for超时兜底。 - C++20 协程 / 单线程 EventLoop(极易踩坑):在事件循环上绝对不能用
thread_local!因为同一线程上多个无关协程交替挂起与恢复,协程 A 挂起后协程 B 请求同一key会误判重入;必须把活跃key集合显式挂在随co_await链传递的RequestContext中。
- Python
- C++ 结果共享的所有权与锁热点
如果结果类型T很大或不可拷贝,返回值建议设计为std::shared_ptr<const T>避免每个 Waiter 深拷贝一次;若高并发下全局mu_成为热点,可按hash(key) % N做分段锁(Striped Lock)。
核心代码骨架(Python asyncio 与 C++20)
1_ACTIVE_KEYS: ContextVar[frozenset[Any]] = ContextVar("active_keys", default=frozenset())
2
3class AsyncSingleFlight:
4 def __init__(self) -> None:
5 self._inflight: dict[Any, asyncio.Future[Any]] = {}
6 self._lock = asyncio.Lock()
7
8 async def do(self, key: Any, fn: Callable[[], Awaitable[T]], timeout: float | None = None) -> T:
9 active = _ACTIVE_KEYS.get()
10 if key in active:
11 raise ReentrantKeyError(f"Cycle/reentrant request for key: {key!r}")
12
13 async with self._lock:
14 fut = self._inflight.get(key)
15 is_leader = fut is None
16 if is_leader:
17 fut = asyncio.get_running_loop().create_future()
18 self._inflight[key] = fut
19
20 if not is_leader:
21 wait_coro = asyncio.shield(fut)
22 return await (asyncio.wait_for(wait_coro, timeout) if timeout is not None else wait_coro)
23
24 token = _ACTIVE_KEYS.set(active | {key})
25 try:
26 result = await fn()
27 if not fut.done():
28 fut.set_result(result)
29 return result
30 except BaseException as exc:
31 if not fut.done():
32 fut.set_exception(exc)
33 raise
34 finally:
35 _ACTIVE_KEYS.reset(token)
36 async with self._lock:
37 if self._inflight.get(key) is fut:
38 del self._inflight[key]
C++20 多线程版用 std::shared_ptr<Call>(内含 mutex、condition_variable、done、std::optional<T>、std::exception_ptr)搭配 try/catch (...) 与 ActiveKeyGuard RAII 守卫,保证异常传播与按 shared_ptr 身份清理不遗漏。
三、 任务 DAG 与最短路:Kahn 拓扑、三色定位环与三类最短路边界
工程里的 ETL / 物化视图刷新任务、Agent 工具调用编排,底层都是有向图偏序调度:u -> v 表示 u 必须先于 v 完成。
1. Kahn 入度法 vs DFS 三色标记:为什么不能互相完全替代?
口述拓扑排序时很容易说出一句不严谨的话:“Kahn 结束后,入度还大于 0 的就是环上的点。”
举个反例就能推翻它:如果 b <-> c 成环,同时 c -> d,那么 Kahn 结束后 b、c、d 的入度都大于 0,但 d 只是被环阻塞的下游任务,它自己并不在环上。因此,调度系统通常采用组合拳:
- Kahn 入度队列:负责产出执行序、按层统计并行度(1136. 并行课程);若需确定性输出则把普通队列换成最小堆;若任务耗时不等,则按拓扑序做关键路径 DP(
earliest_start[v] = max(earliest_start[u] + duration[u]))。 - DFS 三色标记(0 未访 / 1 在当前栈 / 2 已完成):一旦 Kahn 出队数小于总任务数,用三色 DFS 找到指向灰色节点(
1)的回边,顺着parent回溯就能精确打印出b -> c -> b环路报错。 - 失败级联取消:某个节点失败时,从该点出发沿正向出边做 BFS 求可达集,只取消下游依赖,旁路任务正常执行。
常见拓扑题的变形对照:
| 题号与名称 | 核心变形点 | 解法关键 |
|---|---|---|
| 207 / 210 | 基础判环 / 出序 | Kahn 统计出队数,或三色 DFS 抓回边 |
| 2115. 做菜 | 只有给定起点可用 | 仅将 supplies 作为初始队列,逐层解锁菜品 |
| 269. 火星词典 | 隐式字符建图 | 相邻词找首个不同字符连边;"abc" 在 "ab" 前直接判非法 |
| 1857. 最大颜色值 | 拓扑序 + DAG DP | 出队 u 时向后继 v 传递 dp[u][0..25] 最大值 |
| 329. 矩阵最长递增路径 | 隐式 DAG | 值严格递增天然无环,比自己小的邻居数即入度,按层剥离 |
| 802. 最终安全状态 | 能走到环的不安全 | 建反图,从出度为 0 的安全终点反向跑 Kahn |
| 1203. 项目管理 | 组内 + 组间双层约束 | 孤立项分配虚拟组,组间与组内分别拓扑再拼接 |
| 310. 最小高度树 | 无向树拓扑剥叶子 | 度为 1 的叶子入队逐层向心剥离,剩下 $\le 2$ 个中心点 |
2. 三类最短路的边界:BFS、Dijkstra 与 Bellman-Ford
这三个算法之所以不能乱套,用 3 个节点的小反例就能一眼看穿:
- 为什么不等权图不能用普通 BFS(127. 单词接龙)?
图A -> C (10)、A -> B (1)、B -> C (1)。BFS 只看步数,第 1 步先碰到C就误以为最短是10。无权图(或边权全等)才用 BFS(状态多时用双向 BFS,每次只扩展较小集合)。 - 为什么有负权边时 Dijkstra(743. 网络延迟时间)会算错?
图A -> C (2)、A -> B (5)、B -> C (-10)。Dijkstra 假设“后面的路只会越走越贵”,先把最小的C(2)锁死,结果漏掉了5 + (-10) = -5这条路。 - 为什么限制最多走 $k$ 步(787. K 站中转内最便宜的航班)时标准 Dijkstra 也会错?
限制最多走 2 条边从A到D,图有A -> B(1) -> C(1) -> D(100)和A -> C(5)。标准 Dijkstra 在C点看到A -> B -> C花费2 < 5,就把直达A -> C(5)淘汰掉了,等走到D才发现A -> B -> C -> D走了 3 条边超步数!因此必须用 Bellman-Ford 跑k + 1轮松弛,且每轮开始前必须备份prev = dist,防止同轮内串联松弛多走步数。
四、 事件驱动调度与优先级队列:双堆选机、反悔贪心与延迟删除
任务调度题在基础设施里非常常见,底层共同骨架是按事件时间线跳跃推进 + 优先级堆维护候选池(绝不能按秒空转)。
- 单机 SJF / EDF 调度(1834、1353):堆空时时间直接快进到下一个到达时刻;1834 按耗时最短出堆(注意
time用long long),1353 每天清理过期会议后按最早截止时间(EDF)出堆。 - 双堆集群选机(1882、2402):维护
free_heap(按权重/编号选机器)与busy_heap(按释放时间戳finish_time排序)。每次派发前先将busy_heap中finish_time <= current_time的机器全部归还free_heap;若无空闲机器,时间直接跳到busy_heap.top().finish_time并批量归还同时释放的所有机器。 - 反悔贪心与配额瓶颈(871、1383):871 路过加油站先把油量存进大顶堆,油不够时从历史堆里挑最大的一桶补上;1383 先按效率降序固定瓶颈,再用小顶堆维护速度 Top-K。
- 冷却桶与区间贪心(621、452、2054):621 利用最高频次 $M$ 与并列种类数 $C$ 构造桶公式 $\max(N, (M-1)(n+1)+C)$;452 按右端点排序射箭;2054 按开始时间扫描,用小顶堆弹出已结束活动并更新历史最大价值。
- 动态删任意元素——延迟删除对顶堆(295 $\to$ 480):295 用“小的一半大顶堆 + 大的一半小顶堆”过一遍筛子维持平衡;480 滑窗移出任意元素时,堆不支持 $O(\log k)$ 随机删除,因此引入
delayed哈希表记录待删次数,并单独维护逻辑大小small_size_/large_size_,只在元素浮到堆顶时才通过prune()真正弹出。
五、 树状前缀缓存(RadixTree)与带约束 LRU:vLLM / SGLang 显存底座
在 LLM 推理引擎中,多轮对话、Few-shot 与 Agent 工作流存在大量公共前缀。RadixTree 的本质,是以 Token 序列为路径、以 GPU 物理 KV Block(固定大小,如 16 个 Token 一块)为映射目标的树状显存缓存管理器。
1. 显存布局与 PagedAttention 计算闭环
GPU 启动时将显存预分配为巨大的连续 Tensor Pool(如 [num_blocks, block_size, num_kv_heads, head_dim])。对于序列第 $i$ 个 Token,逻辑块号为 i / 16、块内偏移为 i % 16,再通过请求私有的 block_table 页表查到物理 block_id。PagedAttention CUDA Kernel 接收 block_table 后,直接用指针算术就地跳块读取非连续物理 Block 算 Attention,零拷贝。
当尾部只填了部分槽位(比如 18 个 Token 占 2 块,第 2 块只用了 2 格,闲置 14 格)时:
- 计算时:Kernel 依据传入的
context_len对超出有效边界的槽位做掩码(置为 $-\infty$),绝不读出脏数据; - 生成时:Decode 阶段新生成的 Token 就地写入空槽位,填满 16 个才申请下一块;
- 跨请求共享时:为避免并发写写冲突,vLLM 早期采用块对齐截断(只缓存填满 16 个的完整块,尾部零头宁可花几微秒重算);SGLang 则支持未满块共享,并在分叉写入时触发 Copy-on-Write(CoW) 克隆新块。
2. vLLM V0 到 V1 架构演进动机
vLLM V0 早期采用平铺的级联块哈希(H_i = Hash(H_{i-1}, Tokens_i) 存入 Dict[BlockHash, Block])。这种设计没有显式树拓扑,长上下文下每步在 Python 里切块算 Hash 带来毫秒级 CPU 调度瓶颈,更难以干净地统一 Chunked Prefill(长 Prompt 分块跨步状态挂载) 与 推测解码的树状验证(Draft Token Tree 1:1 映射与瞬间剪枝)。因此在 V1 重构中,vLLM 转向了显式分层前缀树模型。
3. 带约束的树状 LRU 淘汰机制
由于子节点存储的 KV Cache 在物理和语义上强依赖父节点前缀,任何内部节点都不能在子节点存活时被直接驱逐——淘汰必须严格自叶向根(Leaf-to-Root)。
可驱逐不变量:node->ref_count == 0 && node->children.empty()
核心结构采用树节点 + 侵入式双向 LRU 链表:
- 全局 LRU 链表:仅挂载当前可驱逐的叶子节点(头最旧、尾最新),保证 $O(1)$ 摘除、尾插与淘汰;
match_prefix:沿树向下匹配,更新last_access,若节点在 LRU 链表中则 $O(1)$ 挪到链表尾;inc_ref/dec_ref:引用计数变化时,若节点状态在“完全无锁”与“有锁”之间翻转,沿parent向上更新locked_children,遇到已处于相同锁定状态的祖先可提前终止;evict(B):从 LRU 头部逐个淘汰叶子并从parent->children摘除;当某父节点的所有孩子都被逐空且自身ref_count == 0时,晋升为新的可驱逐叶子并保留原有last_access挂入 LRU(核心实现已沉淀于cc/cclab/src/utils/prefix_cache_lru.h与python/pylab/prefix_cache_lru.py)。
六、 工程数据结构手写模板:Bloom Filter 与 LRU Cache
1. 面试手写 Bloom Filter 的四个加分细节
- 先报参数公式与经验值:给定预期元素数 $n$ 与误判率 $p$,位数组大小 $m = -\frac{n \ln p}{(\ln 2)^2}$,最优哈希数 $k = \frac{m}{n} \ln 2$(当 $p = 1%$ 时,约 $9.6\text{ bits/elem}$、$k \approx 7$)。
- 双哈希模拟 $k$ 个哈希(Kirsch-Mitzenmacher):工业界(RocksDB / Guava)只算两个 64 位哈希 $h_1, h_2$,用 $g_i(x) = (h_1(x) + i \cdot h_2(x)) \pmod m$ 模拟 $k$ 个独立哈希。
- 底层位操作:用
std::vector<uint64_t>按 64 位对齐存储,bits[idx / 64] |= (1ULL << (idx % 64))。 - DB 内核级追问准备:
- 如何支持删除? 改用 Counting Bloom Filter(4-bit 计数器,空间 $\times 4$)或 Cuckoo Filter(存指纹支持 $O(1)$ 删除);
- 标准 Bloom Filter 的硬件瓶颈? 每次查询触发 $k$ 次随机内存访问导致 $k$ 次 L3 Cache Miss;工业界用 Blocked Bloom Filter 将 $k$ 个 bit 全塞进同一个 64 字节 CPU Cache Line 内配合 SIMD 检查,将 Cache Miss 降为至多 1 次;
- 无锁并发写? 使用
std::atomic<uint64_t>::fetch_or(..., std::memory_order_relaxed)。
1class BloomFilter {
2public:
3 BloomFilter(size_t expected_elements, double fp_rate = 0.01) {
4 double ln2 = std::log(2.0);
5 num_bits_ = static_cast<size_t>(
6 std::ceil(-1.0 * expected_elements * std::log(fp_rate) / (ln2 * ln2)));
7 num_bits_ = std::max<size_t>(64, (num_bits_ + 63) / 64 * 64);
8 num_hashes_ = std::clamp<size_t>(
9 static_cast<size_t>(std::round((double(num_bits_) / expected_elements) * ln2)), 1, 30);
10 bits_.resize(num_bits_ / 64, 0);
11 }
12
13 void Add(std::string_view key) {
14 auto [h1, h2] = Hash128(key);
15 for (size_t i = 0; i < num_hashes_; ++i) {
16 size_t idx = (h1 + i * h2) % num_bits_;
17 bits_[idx / 64] |= (1ULL << (idx % 64));
18 }
19 }
20
21 bool Contains(std::string_view key) const {
22 auto [h1, h2] = Hash128(key);
23 for (size_t i = 0; i < num_hashes_; ++i) {
24 size_t idx = (h1 + i * h2) % num_bits_;
25 if ((bits_[idx / 64] & (1ULL << (idx % 64))) == 0) return false;
26 }
27 return true;
28 }
29
30private:
31 static uint64_t Mix64(uint64_t z) {
32 z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
33 z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
34 return z ^ (z >> 31);
35 }
36 static std::pair<uint64_t, uint64_t> Hash128(std::string_view s) {
37 uint64_t h1 = 0xcbf29ce484222325ULL, h2 = 0x100000001b3ULL;
38 for (char c : s) {
39 h1 = (h1 ^ static_cast<uint8_t>(c)) * 0x100000001b3ULL;
40 h2 = (h2 ^ static_cast<uint8_t>(c)) * 0xcbf29ce484222325ULL;
41 }
42 return {Mix64(h1), Mix64(h2 | 1ULL)};
43 }
44 size_t num_bits_{0}, num_hashes_{0};
45 std::vector<uint64_t> bits_;
46};
2. C++ 工程实现优化要点
- LRU 缓存(146):
std::list<std::pair<int, int>>配合unordered_map,命中时用cache_.splice(cache_.begin(), cache_, it->second)原地改指针移到表头,零内存重分配。 - Trie(208 / 212):小写字母场景用
std::array<std::unique_ptr<Node>, 26>替代哈希表;网格搜词(212)在终点节点直接存std::string word,命中后置空防止重复收集。 - 二叉树序列化(297):
std::ostringstream写"# "占位符配合std::istringstream(in >> token自动跳过前导空白符并按空格切分);追求极致零拷贝可用std::string_view+std::from_chars原地切分。
七、 18 个高频算法范式全景速查与切换开关
1. 一眼看懂 18 个解题范式
| 范式 | 识别信号 | 大白话核心思路 & 极简示例 | 代表题 |
|---|---|---|---|
| 1. 哈希与计数 | 查找配对、频率、去重 | 用小本本记下见过谁。[2,7,11] 找 9:到 7 时查表里有 9-7=2 | 1, 49 |
| 2. 双指针 | 有序数组、两端夹逼 | 排序后两头往中间捏。[-1,-1,0,1,2]:和太小左进、太大右退,注意去重 | 15, 42 |
| 3. 滑动窗口 | 连续子串/数组、非负极值 | 毛毛虫爬行:头往前伸凑条件,尾往回收砍多余(valid 计数器 $O(1)$ 判覆盖) | 3, 76, 209 |
| 4. 前缀和 / 差分 | 含负数区间和、批量范围改 | 先算总账,区间和等于两笔总账之差:prefix[i] - prefix[j] == k | 560 |
| 5. 二分 / 答案二分 | 有序局部或单调判定谓词 | 不止能搜下标,还能猜答案区间 [1, max],行就往小猜、不行往大猜 | 33, 875 |
| 6. 单调栈 | 下一个更大/小、矩形面积 | 栈内维持递增,来矮柱子就把高于它的栈顶踢出并结算左右边界 | 84 |
| 7. 单调队列 | 滑动窗口极值、负数最短子数组 | 队里只留“又晚过期又更强”的候选,淘汰队尾弱者、踢掉过期队头 | 239, 862 |
| 8. 堆 / Top-K | 动态最值、中位数、多路归并 | 不排全名次,只用大小堆拎出尖子生;删任意元素配延迟删除表 | 215, 295, 347, 480 |
| 9. 排序 + 扫描线 | 区间重叠、会议室安排 | 按左端点排一排,从左扫过去能接就拉长、断开就另开一段 | 56, 2054 |
| 10. 贪心 | 最少次数、区间覆盖、资源调度 | 每步选当前最赚且经得起交换论证的选择;拿不准就先入堆再反悔 | 45, 452, 871 |
| 11. DFS / BFS | 连通块、层序、无权最短步数 | DFS 撞南墙淹没连通块,BFS 如水波纹扩散找首次撞线最短路 | 102, 127, 200 |
| 12. 回溯 / 剪枝 | 枚举全排列/组合、约束满足 | 做选择 $\to$ 下潜 $\to$ 撞墙悔棋撤回,死胡同提前砍掉 | 51, 212 |
| 13. 动态规划 | 重叠子问题、最值/方案数 | 拆子问题记表格(线性/背包/双序列),0-1 背包倒序、完全背包正序 | 72, 198, 300, 322, 416 |
| 14. 分治 / 归并 | 逆序对、跨段点对统计 | 对半切开分别算完,趁两半各自有序用双指针扫跨界配对,再归并 | 493, 23 |
| 15. 并查集 | 动态加边连通、无向图判环 | 认老大看终极 Boss 是否同人,新边两端已同根则成环 | 547, 684 |
| 16. 图最短路 / 拓扑 | 依赖序、带权路径、步数约束 | Kahn 剥入度 0、Dijkstra 非负权贪心、Bellman-Ford 抗负权/限步数 | 207, 743, 787 |
| 17. Trie / 前缀树 | 共享前缀检索、词典剪枝 | 相同开头共用树枝,查词只需按字母往下走 | 208 |
| 18. 位运算 / 状态压缩 | 小规模集合状态枚举 | 用一个整数的二进制位代替 bool used[] 数组当状态 Key | 698 |
2. 高频「条件切换开关」
做题和面试时,重点盯住这五处条件变化:
- 数组全正 $\to$ 允许负数:滑动窗口(209)立刻切为前缀和 + 哈希(560)或前缀和 + 单调队列(862)。
- 无权 $\to$ 正权 $\to$ 负权/限步数:BFS(127) $\to$ Dijkstra(743) $\to$ Bellman-Ford(787)。
- 静态全图 $\to$ 流式加边:DFS/BFS(200) $\to$ 并查集(684)。
- 普通 LRU $\to$ 树状前缀依赖 LRU:
list + map(146) $\to$ 叶子 LRU + 引用锁定(RadixCache)。 - 静态 Top-K $\to$ 滑窗删除任意元素:对顶堆(295) $\to$ 延迟删除对顶堆(480)。
八、 经典母题精讲:通用方法抽象与 C++ 模板
上面的 18 个范式如果只停留在概念表上,面试落笔时仍然容易在边界条件和循环不变量上出错。下面挑出 12 个最具迁移价值的经典母题——每一题都对应一类可复用的解题骨架,掌握这些骨架和它们的 C++ 实现,遇到同家族变体时只需替换判定条件或状态转移即可。
1. 滑动窗口通用骨架:76. 最小覆盖子串
给定字符串 s 和 t,求 s 中涵盖 t 所有字符(含重复个数)的最小子串。如果每次窗口变动都把两个字符频次表完整比对一遍,时间会退化到 $O(|\Sigma| \cdot n)$。
把这个问题抽象成通用滑窗模板,关键在于引入一个增量计数器 valid:只有当某个目标字符在窗口内的频次刚好追平需求量时,valid 才加 1;移出左端点导致该字符跌破需求量时,valid 才减 1。这样就把“窗口是否合法”压缩成了一次 $O(1)$ 的整数比较 valid == required_kinds。所有“求最短合法区间”的滑窗题(3、209、438、567)都遵循同一套四步循环:右端入窗更新状态 $\to$ 满足条件时循环缩左 $\to$ 在合法态更新最优解 $\to$ 左端出窗撤销状态。
1#include <array>
2#include <climits>
3#include <string>
4
5class Solution {
6public:
7 std::string minWindow(std::string s, std::string t) {
8 std::array<int, 128> need{};
9 std::array<int, 128> window{};
10 int required_kinds = 0;
11 for (char c : t) {
12 if (need[static_cast<unsigned char>(c)]++ == 0) ++required_kinds;
13 }
14
15 int left = 0, valid = 0, start = 0, min_len = INT_MAX;
16 for (int right = 0; right < static_cast<int>(s.size()); ++right) {
17 unsigned char c = s[right];
18 if (need[c] > 0 && ++window[c] == need[c]) ++valid;
19
20 while (valid == required_kinds) {
21 if (right - left + 1 < min_len) {
22 start = left;
23 min_len = right - left + 1;
24 }
25 unsigned char d = s[left++];
26 if (need[d] > 0) {
27 if (window[d] == need[d]) --valid;
28 --window[d];
29 }
30 }
31 }
32 return min_len == INT_MAX ? "" : s.substr(start, min_len);
33 }
34};
2. 前缀和 + 哈希表:560. 和为 K 的子数组
给定可能包含负数的数组 nums,统计和恰好等于 k 的连续子数组个数。负数破坏了窗口和随长度递增的单调性,双指针无法判断该扩右还是缩左。
通用破局思路是把连续区间问题写成前缀差分:子数组 [j, i] 的和等于 prefix[i] - prefix[j - 1] == k,移项即 prefix[j - 1] == prefix[i] - k。问题瞬间退化成“遍历到当前前缀和时,历史哈希表里有多少个匹配的旧前缀和”。同理,只要把 sum - k 换成 (sum % k + k) % k(同余定理,如 523/974 题),或者把 0 看成 -1 求 0/1 数量相等的最长子数组(525 题),整套模板原封不动即可复用。
1#include <unordered_map>
2#include <vector>
3
4class Solution {
5public:
6 int subarraySum(std::vector<int>& nums, int k) {
7 std::unordered_map<int, int> prefix_count;
8 prefix_count[0] = 1; // 空前缀和为 0,覆盖从下标 0 开始直接命中 k 的情况
9
10 int sum = 0, ans = 0;
11 for (int x : nums) {
12 sum += x;
13 if (auto it = prefix_count.find(sum - k); it != prefix_count.end()) {
14 ans += it->second;
15 }
16 ++prefix_count[sum];
17 }
18 return ans;
19 }
20};
3. 答案空间二分:875. 爱吃香蕉的珂珂
给定若干堆香蕉 piles 和时间上限 h,求每小时能吃完的最小速度 k。题目并没有给你一个排好序的数组,但答案本身具有单调性:如果速度 k 能在 h 小时内吃完,那么任何大于 k 的速度也一定吃得完。
这类“求最小可行值”或“最小化最大值”的问题(如 1011 运送包裹、410 分割数组的最大值)全部对应同一套单调谓词二分模板:确定答案上下界 [left, right],写一个线性扫描判定函数 check(mid);若 check(mid) 为真,说明最优解在左半边(含 mid),令 right = mid,否则 left = mid + 1,循环结束时 left 即为最小可行解。
1#include <algorithm>
2#include <vector>
3
4class Solution {
5public:
6 int minEatingSpeed(std::vector<int>& piles, int h) {
7 int left = 1;
8 int right = *std::max_element(piles.begin(), piles.end());
9
10 auto canFinish = [&](int speed) -> bool {
11 long long hours = 0;
12 for (int p : piles) {
13 hours += (p + speed - 1) / speed; // 向上取整
14 }
15 return hours <= h;
16 };
17
18 while (left < right) {
19 int mid = left + (right - left) / 2;
20 if (canFinish(mid)) {
21 right = mid;
22 } else {
23 left = mid + 1;
24 }
25 }
26 return left;
27 }
28};
4. 单调栈找左右边界:84. 柱状图中最大的矩形
给定柱子高度数组 heights,求最大矩形面积。若以第 k 根柱子为矩形高度,它向左向右最多能延伸到哪里?恰好停在左边第一个严格比它矮的柱子和右边第一个严格比它矮的柱子之间。
单调栈的通用抽象是:栈内保存下标并维持对应值的严格单调性;每当新元素打破单调性时,被弹出的栈顶元素就同时锁定了它的右边界(当前下标 i)与左边界(弹出后的新栈顶)。在循环末尾 i == n 处喂入一个高度 0 的虚拟哨兵,可以一次性把留在栈里的所有柱子结算干净,免去循环外写重复收尾代码。
1#include <algorithm>
2#include <stack>
3#include <vector>
4
5class Solution {
6public:
7 int largestRectangleArea(std::vector<int>& heights) {
8 int n = heights.size();
9 std::stack<int> st;
10 int max_area = 0;
11
12 for (int i = 0; i <= n; ++i) {
13 int cur_h = (i == n) ? 0 : heights[i]; // 末尾虚拟哨兵 0 强制清空栈
14 while (!st.empty() && heights[st.top()] > cur_h) {
15 int h = heights[st.top()];
16 st.pop();
17 int left_bound = st.empty() ? -1 : st.top();
18 max_area = std::max(max_area, h * (i - left_bound - 1));
19 }
20 st.push(i);
21 }
22 return max_area;
23 }
24};
5. 前缀和 + 单调队列:862. 和至少为 K 的最短子数组
给定含负数的数组 nums,求和至少为 k 的最短非空连续子数组。先构造前缀和 prefix[0..n],目标变为对每个右端点 i 寻找最靠右的 j < i 满足 prefix[i] - prefix[j] >= k。
单调队列维护的是候选起点之间的双维支配关系:
- 队头结算即出队:只要队头
j已经满足prefix[i] - prefix[j] >= k,更新最短长度后立刻弹出j,因为后面更大的右端点再配对j只会更长,绝不可能刷新最优解; - 队尾淘汰劣势点:新下标
i入队前,把队尾所有prefix[dq.back()] >= prefix[i]的点全部弹出,因为它们既更靠左、又需要更大的右端点才能凑够差值k,在两个维度上都被i彻底碾压。
1#include <algorithm>
2#include <climits>
3#include <deque>
4#include <vector>
5
6class Solution {
7public:
8 int shortestSubarray(std::vector<int>& nums, int k) {
9 int n = nums.size();
10 std::vector<long long> prefix(n + 1, 0);
11 for (int i = 0; i < n; ++i) prefix[i + 1] = prefix[i] + nums[i];
12
13 std::deque<int> dq;
14 int min_len = INT_MAX;
15
16 for (int i = 0; i <= n; ++i) {
17 while (!dq.empty() && prefix[i] - prefix[dq.front()] >= k) {
18 min_len = std::min(min_len, i - dq.front());
19 dq.pop_front();
20 }
21 while (!dq.empty() && prefix[dq.back()] >= prefix[i]) {
22 dq.pop_back();
23 }
24 dq.push_back(i);
25 }
26 return min_len == INT_MAX ? -1 : min_len;
27 }
28};
6. 对顶堆 + 延迟删除:480. 滑动窗口中位数
固定长度为 k 的窗口在数组上滑动,每次返回窗口中位数。这道题把“动态维护中位数(295 题)”与“标准堆不支持随机删除”两个难点叠在了一起。
通用解法是延迟删除(Lazy Deletion)框架:用 small_(大顶堆)和 large_(小顶堆)各存一半元素,额外用 delayed_ 哈希表记录“逻辑上已删除、物理上还留在堆里”的数值频次,并用 small_size_、large_size_ 维护有效逻辑大小。只要每次平衡堆大小后立刻调用 prune(heap) 把浮到堆顶的过期元素清理干净,就能保证对外暴露的堆顶永远是有效值。
1#include <functional>
2#include <queue>
3#include <unordered_map>
4#include <vector>
5
6class DualHeap {
7public:
8 explicit DualHeap(int k) : k_(k) {}
9
10 void insert(int num) {
11 if (small_.empty() || num <= small_.top()) {
12 small_.push(num);
13 ++small_size_;
14 } else {
15 large_.push(num);
16 ++large_size_;
17 }
18 makeBalance();
19 }
20
21 void erase(int num) {
22 ++delayed_[num];
23 if (num <= small_.top()) {
24 --small_size_;
25 if (num == small_.top()) prune(small_);
26 } else {
27 --large_size_;
28 if (num == large_.top()) prune(large_);
29 }
30 makeBalance();
31 }
32
33 double getMedian() const {
34 return (k_ & 1) ? static_cast<double>(small_.top())
35 : (static_cast<double>(small_.top()) + large_.top()) / 2.0;
36 }
37
38private:
39 template <typename Heap>
40 void prune(Heap& heap) {
41 while (!heap.empty()) {
42 int num = heap.top();
43 auto it = delayed_.find(num);
44 if (it == delayed_.end()) break;
45 if (--(it->second) == 0) delayed_.erase(it);
46 heap.pop();
47 }
48 }
49
50 void makeBalance() {
51 if (small_size_ > large_size_ + 1) {
52 large_.push(small_.top());
53 small_.pop();
54 --small_size_;
55 ++large_size_;
56 prune(small_);
57 } else if (small_size_ < large_size_) {
58 small_.push(large_.top());
59 large_.pop();
60 ++small_size_;
61 --large_size_;
62 prune(large_);
63 }
64 }
65
66 int k_, small_size_ = 0, large_size_ = 0;
67 std::priority_queue<int> small_;
68 std::priority_queue<int, std::vector<int>, std::greater<int>> large_;
69 std::unordered_map<int, int> delayed_;
70};
7. 反悔贪心:871. 最低加油次数
初始油量 startFuel,沿途有若干加油站 [pos, fuel],求到达 target 的最少加油次数。当场路过加油站时并不知道后面够不够开,如果立刻决定加不加,很容易陷入局部决策困境。
**反悔贪心(Regret Greedy)**的通用思想是把决策推迟到不得不做的时候:沿途路过的所有加油站先不加,统统把油量塞进一个大顶堆里当备用库;继续往前开,直到当前油量不足以撑到下一个目标时,再从大顶堆里掏出历史经过的最大一桶油加上(等价于“反悔”当初在那一站加了油)。同样套路可直接解 630. 课程表 III(先按截止日排序硬选,超时就从大顶堆里把耗时最长的课踢掉)。
1#include <queue>
2#include <vector>
3
4class Solution {
5public:
6 int minRefuelStops(int target, int startFuel, std::vector<std::vector<int>>& stations) {
7 std::priority_queue<int> max_heap;
8 long long fuel = startFuel;
9 int refuels = 0, idx = 0, n = stations.size();
10
11 while (fuel < target) {
12 while (idx < n && stations[idx][0] <= fuel) {
13 max_heap.push(stations[idx++][1]);
14 }
15 if (max_heap.empty()) return -1;
16 fuel += max_heap.top();
17 max_heap.pop();
18 ++refuels;
19 }
20 return refuels;
21 }
22};
8. 二叉树后序树形 DP:124. 二叉树中的最大路径和
求二叉树中任意节点到任意节点的最大路径和(路径不必经过根)。树形 DP 最核心的通用思维,是把每个节点处计算的两个量彻底拆开:
- 以当前节点为最高拐点、连通左右子树的完整答案:
node->val + left_gain + right_gain,用来刷新全局max_sum_; - 向上返回给父节点的单边最大链贡献:
node->val + max(left_gain, right_gain),因为路径往上延伸不能分叉。如果某侧子树贡献小于 0,直接截断取0。二叉树的直径(543 题)、最长同值路径(687 题)都完全复用这一套后序汇总结构。
1#include <algorithm>
2#include <climits>
3
4class Solution {
5private:
6 int max_sum_ = INT_MIN;
7
8 int maxGain(TreeNode* node) {
9 if (!node) return 0;
10 int left_gain = std::max(0, maxGain(node->left));
11 int right_gain = std::max(0, maxGain(node->right));
12 max_sum_ = std::max(max_sum_, node->val + left_gain + right_gain);
13 return node->val + std::max(left_gain, right_gain);
14 }
15
16public:
17 int maxPathSum(TreeNode* root) {
18 maxGain(root);
19 return max_sum_;
20 }
21};
9. 双向 BFS 状态搜索:127. 单词接龙
每次改一个字母从 beginWord 走到 endWord,求最短步数。在无权状态转移图中,单向 BFS 的搜索树按分支因子 $b$ 呈 $b^d$ 指数膨胀;而只要起点和终点都已知,双向 BFS 每次只扩展当前集合更小的那一端(if (q1.size() > q2.size()) swap(q1, q2)),把状态数压到 $2 \cdot b^{d/2}$。同时通过按位替换 26 个字母查哈希表生成邻居,省去了 $O(N^2)$ 建图开销。
1#include <string>
2#include <unordered_set>
3#include <utility>
4#include <vector>
5
6class Solution {
7public:
8 int ladderLength(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
9 std::unordered_set<std::string> dict(wordList.begin(), wordList.end());
10 if (!dict.contains(endWord)) return 0;
11
12 std::unordered_set<std::string> q1{beginWord}, q2{endWord};
13 dict.erase(beginWord);
14 dict.erase(endWord);
15
16 int steps = 1;
17 while (!q1.empty() && !q2.empty()) {
18 if (q1.size() > q2.size()) std::swap(q1, q2);
19 std::unordered_set<std::string> next_q;
20 for (std::string word : q1) {
21 for (size_t i = 0; i < word.size(); ++i) {
22 char orig = word[i];
23 for (char c = 'a'; c <= 'z'; ++c) {
24 if (c == orig) continue;
25 word[i] = c;
26 if (q2.contains(word)) return steps + 1;
27 if (dict.erase(word)) next_q.insert(word);
28 }
29 word[i] = orig;
30 }
31 }
32 q1 = std::move(next_q);
33 ++steps;
34 }
35 return 0;
36 }
37};
10. 线性 DP 降维与双序列 DP:300. 最长递增子序列 & 72. 编辑距离
动态规划最常见的两种形态,一是利用贪心单调性把 $O(n^2)$ 线性 DP 降到 $O(n \log n)$,二是双序列二维状态对齐。
- 300 题(LIS):定义
tails[k]表示长度为k + 1的递增子序列中末尾元素的最小值。因为同长度下末尾越小越容易接后续元素,tails天然严格递增,每次用std::lower_bound替换第一个>= x的位置即可。 - 72 题(编辑距离):定义
dp[i][j]为word1[0..i)变成word2[0..j)的最少步数,末尾字符相等直接继承左上角dp[i - 1][j - 1],不等则在删(上)、插(左)、替(左上)三个方向取最小+ 1(LCS 1143 题、正则匹配 10 题都是同一张二维表)。
1#include <algorithm>
2#include <string>
3#include <vector>
4
5// 300. LIS: 贪心 + 二分 O(n log n)
6int lengthOfLIS(const std::vector<int>& nums) {
7 std::vector<int> tails;
8 for (int x : nums) {
9 auto it = std::lower_bound(tails.begin(), tails.end(), x);
10 if (it == tails.end()) tails.push_back(x);
11 else *it = x;
12 }
13 return tails.size();
14}
15
16// 72. 编辑距离: 双序列二维 DP O(m * n)
17int minDistance(const std::string& w1, const std::string& w2) {
18 int m = w1.size(), n = w2.size();
19 std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
20 for (int i = 0; i <= m; ++i) dp[i][0] = i;
21 for (int j = 0; j <= n; ++j) dp[0][j] = j;
22
23 for (int i = 1; i <= m; ++i) {
24 for (int j = 1; j <= n; ++j) {
25 if (w1[i - 1] == w2[j - 1]) {
26 dp[i][j] = dp[i - 1][j - 1];
27 } else {
28 dp[i][j] = 1 + std::min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
29 }
30 }
31 }
32 return dp[m][n];
33}
11. 并查集与带权最短路:684. 冗余连接 & 743 / 787
图论工程题里最常手写的三个底层模板:
- 并查集在线判环(684):带路径压缩的
find,合并边[u, v]前若发现find(u) == find(v),说明两点早已连通,当前边必成环。 - 非负权单源最短路(743 Dijkstra):小顶堆按距离从小到大弹出,遇到
d > dist[u]的过时条目直接跳过。 - 步数受限最短路(787 Bellman-Ford):跑
k + 1轮松弛,每轮开始先拷贝prev = dist隔离本轮更新,严防单轮串联松弛超过 1 条边。
1#include <algorithm>
2#include <climits>
3#include <numeric>
4#include <queue>
5#include <utility>
6#include <vector>
7
8// 684. 并查集在线判环
9std::vector<int> findRedundantConnection(const std::vector<std::vector<int>>& edges) {
10 int n = edges.size();
11 std::vector<int> parent(n + 1);
12 std::iota(parent.begin(), parent.end(), 0);
13 auto find = [&](auto&& self, int x) -> int {
14 return parent[x] == x ? x : (parent[x] = self(self, parent[x]));
15 };
16 for (const auto& e : edges) {
17 int ru = find(find, e[0]), rv = find(find, e[1]);
18 if (ru == rv) return e;
19 parent[ru] = rv;
20 }
21 return {};
22}
23
24// 743. 堆优化 Dijkstra(非负权最短路)
25int networkDelayTime(const std::vector<std::vector<int>>& times, int n, int k) {
26 std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
27 for (const auto& t : times) adj[t[0]].emplace_back(t[1], t[2]);
28
29 std::vector<int> dist(n + 1, INT_MAX);
30 dist[k] = 0;
31 using P = std::pair<int, int>;
32 std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
33 pq.emplace(0, k);
34
35 while (!pq.empty()) {
36 auto [d, u] = pq.top();
37 pq.pop();
38 if (d > dist[u]) continue;
39 for (const auto& [v, w] : adj[u]) {
40 if (d + w < dist[v]) {
41 dist[v] = d + w;
42 pq.emplace(dist[v], v);
43 }
44 }
45 }
46 int ans = *std::max_element(dist.begin() + 1, dist.end());
47 return ans == INT_MAX ? -1 : ans;
48}
49
50// 787. Bellman-Ford(最多 k 次中转 = k + 1 条边)
51int findCheapestPrice(int n, const std::vector<std::vector<int>>& flights, int src, int dst, int k) {
52 const int kInf = 1e9;
53 std::vector<int> dist(n, kInf);
54 dist[src] = 0;
55 for (int step = 0; step <= k; ++step) {
56 std::vector<int> prev = dist; // 备份上一轮,禁止同轮串联松弛
57 for (const auto& f : flights) {
58 if (prev[f[0]] != kInf) {
59 dist[f[1]] = std::min(dist[f[1]], prev[f[0]] + f[2]);
60 }
61 }
62 }
63 return dist[dst] == kInf ? -1 : dist[dst];
64}
12. 位运算状态压缩 DP:698. 划分为 k 个相等的子集
给定最多 16 个整数的数组 nums,判断能否分成 k 个和相等的非空子集。如果直接写朴素回溯,不同排列顺序会反复访问完全相同的“已选元素集合”,导致严重重复搜索。
当元素规模 $n \le 20$ 时,通用优化手段是位掩码状态压缩(Bitmask DP):用一个 $n$ 位整数 mask 的每一位表示第 i 个元素是否已被放入桶中,dp[mask] 记录当前正在填充的桶的剩余已占容量(满 target 自动取模归 0,表示开启下一个新桶;-1 表示该状态不可达)。将数组升序排序后,一旦 dp[mask] + nums[i] > target 就能直接 break 剪枝,把原本阶乘级的回溯压到了确定的 $O(n \cdot 2^n)$。
1#include <algorithm>
2#include <numeric>
3#include <vector>
4
5class Solution {
6public:
7 bool canPartitionKSubsets(std::vector<int>& nums, int k) {
8 int sum = std::accumulate(nums.begin(), nums.end(), 0);
9 if (sum % k != 0) return false;
10 int target = sum / k;
11
12 std::sort(nums.begin(), nums.end());
13 if (nums.back() > target) return false;
14
15 int n = nums.size();
16 int total = 1 << n;
17 std::vector<int> dp(total, -1);
18 dp[0] = 0;
19
20 for (int mask = 0; mask < total; ++mask) {
21 if (dp[mask] == -1) continue;
22 for (int i = 0; i < n; ++i) {
23 if ((mask & (1 << i)) != 0) continue;
24 if (dp[mask] + nums[i] > target) break; // 已排序,后续更大直接剪枝
25 int next_mask = mask | (1 << i);
26 if (dp[next_mask] == -1) {
27 dp[next_mask] = (dp[mask] + nums[i]) % target;
28 }
29 }
30 }
31 return dp[total - 1] == 0;
32 }
33};
整理基线说明:本文由多轮系统与算法专题梳理沉淀而成,对应的 C++20 与 Python 可运行代码及单元测试已归档至 xlab 仓库的 cc/cclab/src/utils/(singleflight.h、window_sum.h、task_dag.h、prefix_cache_lru.h)与 python/pylab/。