数据结构与算法

数据结构回答“数据如何组织、支持哪些操作”，算法回答“如何利用数据的性质解决问题”。复习时建议按 基础表示 → 核心操作 → 不变量 → 复杂度 → 组合应用 → 算法范式 的顺序推进，而不是孤立背代码。

推荐学习路径

1. 基础线性结构

1. 数组、前缀和与区间：连续存储、双指针、滑动窗口、前缀和与差分；
2. 链表：指针重连、dummy node、反转、快慢指针；
3. 哈希表：精确 key 查找、冲突处理、装载因子与 rehash。

先掌握访问、插入、删除的成本，以及连续存储和节点式存储在缓存局部性上的差异。

2. 树形与优先结构

1. 树：遍历、递归契约、BST 查找/插入/删除；
2. 平衡二叉搜索树与红黑树：通过额外不变量保证树高；
3. 堆与优先队列：只维护堆顶最优，支持 Top K 和调度。

重点区分：BST 维护全局有序关系，堆只维护父子堆序，哈希表不维护顺序。

3. 组合数据结构

• LRU 缓存：用哈希表实现 O(1) 定位，用双向链表维护访问顺序。

组合题先拆解目标操作，再为每个操作选择结构，并说明多结构之间如何保持一致。

4. 基础算法

1. 排序算法：比较、分治、堆与稳定性；
2. 字符串匹配与 KMP：前缀函数、失配跳转、周期和 border；
3. 位运算与位掩码：集合压缩、子集枚举和状态压缩；
4. 递归、显式栈与字符串解码：递归状态、调用栈与手动栈模拟。

5. 搜索与优化

1. 二分查找：利用单调性定位边界；
2. 图搜索、回溯与并查集：遍历状态空间、枚举方案、维护连通性；
3. 动态规划与贪心：重叠子问题、状态转移与局部选择证明。

按需求选择结构

需求	常见结构	典型复杂度
按下标随机访问	数组 / vector	O(1)
已知节点位置后插删	链表	O(1)
按 key 精确查找，不要求有序	哈希表	平均 O(1)
有序遍历、范围查询、前驱后继	平衡搜索树	O(log n)
反复获取最大值或最小值	堆	top O(1)，更新 O(log n)
O(1) 查找并维护最近使用顺序	哈希表 + 双向链表（LRU）	平均 O(1)
动态合并集合并判断连通	并查集	均摊 O(α(n))

面试回答框架

解释一种数据结构时，可按以下顺序回答：

1. 定义与不变量：它必须始终满足什么；
2. 存储方式：连续数组、节点链接，还是多种结构组合；
3. 核心操作：查找、插入、删除如何维护不变量；
4. 复杂度：平均、摊还和最坏情况分别是什么；
5. 失效与边界：迭代器、内存所有权、退化输入、并发安全；
6. 选择理由：与数组、哈希表、树、堆等替代方案相比为何合适。

算法题则先定义状态 / 搜索空间和不变量，再写转移或指针移动，最后分析时间与空间复杂度。