> For the complete documentation index, see [llms.txt](https://datastructure-1.gitbook.io/datastructure-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://datastructure-1.gitbook.io/datastructure-docs/fu-lu/appendix-b-exercises.md).

# 附录 B：常见面试题与练习

[<- 附录 A：数据结构选择速查](/datastructure-docs/fu-lu/appendix-a-quick-reference.md) | [课程目录](/datastructure-docs/readme.md) | [附录 C：常见陷阱与注意事项 ->](/datastructure-docs/fu-lu/appendix-c-pitfalls.md)

***

## 附录 B：经典面试题与高频算法精选

本附录遴选了各大工业界一线团队（如 Google、Meta、字节跳动、腾讯等）与算法竞赛中最高频出现的经典数据结构考题，剖析其**核心不变式**与**避坑要点**。

***

### 1. 线性结构与双指针

#### 1.1 单链表反转 (Reverse Linked List)

* **核心思想**：三指针滑动窗口（`prev`, `curr`, `next`）。在切断 `curr->next` 之前必须先暂存原后续节点。
* **循环不变量**：在每次迭代开始前，`prev` 始终指向已反转部分的头节点，`curr` 指向待反转的第一个节点。
* **复杂度目标**：时间 $O(n)$，额外空间 $O(1)$。
* **典型误区**：未保存 `curr->next` 便执行 `curr->next = prev`，导致后半段链表永久内存丢失。

#### 1.2 链表环检测与环入口定位 (Floyd Cycle Detection)

* **核心思想**：快慢双指针（Floyd 判圈算法）。快指针步长为 2，慢指针步长为 1。相遇后，将一指针重置回 head，两指针同以步长 1 前进，再次相遇点即为环入口。
* **数学依据**：设起点到环入口距离为 $a$，环入口到相遇点为 $b$，相遇点回环入口为 $c$。有 $2(a+b) = a+b+k(b+c) \implies a = (k-1)(b+c) + c$。
* **复杂度目标**：时间 $O(n)$，额外空间 $O(1)$。

#### 1.3 柱状图中最大的矩形 (Largest Rectangle in Histogram)

* **核心思想**：**单调递增栈**。求以每个柱子高度为高的最大矩形，本质是寻找左右两边第一个比它矮的柱子。
* **循环不变量**：栈中下标对应的高度严格单调递增。新元素小于栈顶时弹出结算。
* **复杂度目标**：每个元素最多进出栈各一次，均摊时间 $O(n)$，空间 $O(n)$。
* **哨兵技巧**：在原高度数组首尾各补充一个高度为 0 的哨兵，可彻底消除栈非空判断与尾部清栈循环。

#### 1.4 滑动窗口最大值 (Sliding Window Maximum)

* **核心思想**：**单调双端队列 (Monotonic Deque)**。维护一个严格单调递减的下标队列。
* **队列不变量**：队头元素始终是当前窗口内的最大值；队尾维护递减性，新入队元素会将前面所有较小元素从队尾弹出（它们永无翻身之日）。
* **复杂度目标**：时间 $O(n)$，空间 $O(k)$。

***

### 2. 树与二叉搜索树

#### 2.1 验证二叉搜索树的合法性 (Validate BST)

* **核心思想**：**区间收缩法** 或 **中序遍历单调性**。
* **区间收缩法**：递归传入当前子树允许的开区间 $(min\_val, max\_val)$。左子树更新上界，右子树更新下界。
* **复杂度目标**：时间 $O(n)$，空间 $O(h)$。
* **典型误区**：仅校验 `node->val > node->left->val && node->val < node->right->val`，忽略了祖先节点对整个子树的全局单调约束。

#### 2.2 二叉树的最近公共祖先 (LCA)

* **核心思想**：后序递归分解（自底向上回溯）。
* **递归契约**：若当前子树包含 $p$ 或 $q$，返回对应指针；若两侧子树各找到一个，说明当前节点就是 LCA；若仅一侧找到，向上透传该侧结果。
* **复杂度目标**：时间 $O(n)$，空间 $O(h)$。

#### 2.3 二叉树的序列化与反序列化 (Serialize & Deserialize)

* **核心思想**：前序遍历（先根再左右）结合 `nullptr` 显式占位符（如 `#`），或者层序遍历（BFS）。
* **充要条件**：带 `nullptr` 标记的前序序列具有**唯一前缀无歧义性**，无需后序/中序即可唯一反解。

***

### 3. 堆与优先队列

#### 3.1 数组中的第 K 大元素 (K-th Largest Element)

* **方案一（小顶堆门槛模型）**：维护大小为 $k$ 的小顶堆。堆顶为当前第 $k$ 大门槛。若新元素大于堆顶，则 `pop()` 淘汰门槛并 `push()` 新元素。时空复杂度：时间 $O(n \log k)$，空间 $O(k)$。
* **方案二（快速选择 QuickSelect）**：利用三向切分/双指针划分，每次舍弃一半无用区间。平均时间 $O(n)$，最坏 $O(n^2)$。

#### 3.2 数据流中的中位数 (Find Median from Data Stream)

* **核心思想**：**对顶堆结构**。
  * 大顶堆（MaxHeap）存储较小的一半元素；
  * 小顶堆（MinHeap）存储较大的一半元素。
* **平衡不变量**：
  1. 大顶堆的最大值 $\le$ 小顶堆的最小值；
  2. 元素总数为偶数时，两堆大小相等；为奇数时，大顶堆比小顶堆恰许多 1 个元素。
* **复杂度目标**：`addNum` 为 $O(\log n)$，`findMedian` 为 $O(1)$。

***

### 4. 图论与网络流

#### 4.1 课程表与拓扑排序判环 (Course Schedule)

* **核心思想**：Kahn 算法（入度数组 + 队列）或 DFS 三色染色法（0-未访问，1-访问中，2-已完成）。
* **判环准则**：
  * Kahn 算法：最终出队节点数 $< V$，则图中必存在有向环。
  * DFS 染色：若在递归遍历中遭遇状态为 1 的节点（遭遇回边 Back-Edge），说明存在环。
* **复杂度目标**：时间 $O(V + E)$，空间 $O(V + E)$。

#### 4.2 网络延迟时间 (Network Delay Time)

* **核心思想**：单源最短路径（Dijkstra 堆优化版）。
* **循环不变量**：每次从小顶堆中弹出的 `(d, u)`，只要 `d == dist[u]`，则 `dist[u]` 已经收敛为其全局最短距离，不再被松弛。
* **复杂度目标**：时间 $O(E \log V)$，空间 $O(V + E)$。
* **避坑要点**：图中若存在**负权边**，Dijkstra 贪心前提彻底失效，必须选用 Bellman-Ford 或 SPFA 算法。

***

### 5. 哈希表与并查集

#### 5.1 LRU 缓存淘汰设计 (LRU Cache)

* **核心架构**：**哈希表 + 双向循环链表（带伪头伪尾 Dummy Head/Tail）**。
* **职责划分**：
  * 双向链表：按访问新鲜度维护顺序（最新在表头，最旧在表尾），支持 $O(1)$ 节点摘除与头插；
  * 哈希表：存储 `Key -> ListNode*`，将链表线性的 $O(n)$ 查找压平为 $O(1)$。
* **复杂度目标**：`get()` 与 `put()` 均严格 $O(1)$。

#### 5.2 冗余连接与图连通性 (Redundant Connection)

* **核心思想**：并查集（Disjoint Set Union）。
* **算法逻辑**：依次遍历无向图的每一条边 $(u, v)$：
  * 若 `find(u) == find(v)`，说明两点在之前已处于同一连通块中，当前边即为导致成环的冗余边；
  * 否则，执行 `unite(u, v)` 合并集合。
* **复杂度目标**：近乎线性时间 $O(E \cdot \alpha(V))$。

***

### 6. 高级字符串

#### 6.1 字符串匹配 (Implement strStr() / KMP)

* **核心思想**：利用模式串的前缀自相似性构建 `next` / `nextval` 失配跳跃表。
* **不变量**：`next[j]` 记录前缀 $P\[0..j-1]$ 的最长相等真前后缀长度。主串指针 $i$ 永不回退。
* **复杂度目标**：构建时间 $O(m)$，匹配时间 $O(n)$，空间 $O(m)$。

#### 6.2 最长重复子串 (Longest Duplicate Substring)

* **核心思想**：后缀数组 (SA) + 最长公共前缀 (LCP / Height 数组)。
* **算法精要**：任何重复子串必然是某两个后缀的前缀。在排序后的后缀数组中，相邻后缀拥有最大的公共前缀。因此问题转化为：$\max\_{1 \le i < n} \text{Height}\[i]$。
* **复杂度目标**：时间 $O(n \log n)$，空间 $O(n)$。

***

[<- 附录 A：数据结构选择速查](/datastructure-docs/fu-lu/appendix-a-quick-reference.md) | [课程目录](/datastructure-docs/readme.md) | [附录 C：常见陷阱与注意事项 ->](/datastructure-docs/fu-lu/appendix-c-pitfalls.md)