数据结构与算法

面试权重：★★★ | 适用级别：P7为主 | 预计复习时间：3-4周（持续刷题）

概览

面试权重：★★★ | 适用级别：P7为主 | 预计复习时间：3-4周（持续刷题）

算法这一章最容易掉进“题做过不少，但现场讲不清模板和边界”的坑。目标不是刷题数量，而是把高频题型识别、模板调用和口述能力稳定下来。

建议用法

复习时按“题型识别 -> 套模板 -> 口述思路 -> 写代码 -> 自测边界”这条顺序走。做高频题不要只记答案，至少要能说出为什么是这个模板、哪里最容易错。

一、知识体系

1. 基础数据结构 ★★★

1.1 数组与链表 ★★★

核心结论
- 数组和链表的本质差异，不是复杂度表，而是内存布局不同：数组连续、链表离散。
原理展开
- 数组随机访问快，适合按下标定位、二分、滑动窗口、前缀和等场景。
- 链表插入删除方便，但定位节点慢，天然适合双指针、反转、合并、快慢指针。
题型识别
- 看到“原地修改数组”“有序数组”“固定窗口”“左右收缩”优先想数组与双指针。
- 看到“节点重连”“反转”“找中点”“找环入口”优先想链表模板。
高频技巧
- 双指针（快慢指针、左右指针）
- 虚拟头节点(Dummy Head)
- 链表反转（迭代/递归）
- 链表中点（快慢指针）
- 链表成环检测（Floyd 判圈）
口述方式
- “先判断底层结构是连续还是离散，再决定是按索引处理还是按指针关系处理。”
易错点
- 链表题最容易错在空指针、头节点变化和反转后连接断开。

1.2 栈与队列 ★★

核心结论
- 栈解决“最近相关”的问题，队列解决“先进先出”的顺序处理问题。
原理展开
- 栈常用于括号匹配、表达式求值、单调栈、递归转迭代。
- 队列常用于 BFS、生产消费、滑动窗口。
- 双端队列是单调队列的常见载体。
- 优先队列适合动态维护“当前最值”。
题型识别
- “找下一个更大/更小”“括号匹配”通常是栈。
- “按层推进”“最短步数”“窗口最大值”通常是队列。
面试怎么答
- “栈和队列不是容器题，而是思维模型题。先识别问题的时间顺序关系，再决定用 LIFO、FIFO 还是堆。”

1.3 哈希表 ★★★

核心结论
- 哈希表的价值，是把“查找某个条件是否出现过”从线性扫描降成近 O(1)。
原理展开
- 高频场景包括两数之和、计数、去重、窗口内字符频率维护。
- 碰撞处理可以是链地址法或开放寻址法，工程上更多关注使用方式而不是手写实现。
题型识别
- 题目里出现“是否存在”“出现次数”“去重”“映射索引”时，优先想哈希表。
口述方式
- “我会先看能不能用空间换时间，把重复查找的信息提前缓存起来。”
易错点
- 只想到 HashSet 去重，没想到 HashMap 还能存索引、次数、最近位置。

1.4 树 ★★★

核心结论
- 树题本质上是在考层次结构和递归思维。二叉树是遍历模板题，BST 是有序性题，堆是局部最值题。

二叉树

原理展开
- 遍历：前序适合“先处理根”，中序适合 BST 有序输出，后序适合“先处理子问题再处理根”，层序适合按层推进。
- BST：左小右大，适合查找、插入、删除、区间剪枝。
- AVL：更严格的平衡，面试通常知道思想即可。
题型识别
- 看到“路径”“深度”“是否对称”“最近公共祖先”通常先想递归。
- 看到“按层”“最短步数”往往可转 BFS。
易错点
- 递归函数返回值含义不清，是树题最大死穴。

红黑树 ★★

核心结论
- 红黑树是工程上常用的平衡搜索树，用较少旋转成本换取近似平衡。
面试怎么答
- “面试里重点不是手写红黑树，而是知道它为什么适合作为 TreeMap、TreeSet 的底层结构，以及 JDK 8 HashMap 为什么在链表过长后转红黑树。”

B树/B+树 ★★

核心结论
- B 树/B+ 树的核心优势是多路、矮胖、磁盘友好，适合数据库索引。
面试怎么答
- “数据库索引偏向 B+ 树，因为非叶子节点不存行数据，可以放更多键，树更矮，范围查询也更友好。”

前缀树(Trie) ★

核心结论
- Trie 适合前缀匹配、词典检索、自动补全。

堆(Heap) ★★★

核心结论
- 堆不是用来全排序，而是高效维护局部最大/最小值。
题型识别
- 看到 Top K、合并 K 路、动态中位数、最短路径优先扩展，优先想堆。
易错点
- 堆排序和优先队列思想相关，但“会用堆”不等于“会写堆排序”。

1.5 图 ★

核心结论
- 图题的关键不是图这个数据结构本身，而是先判断问题属于遍历、最短路、连通性还是拓扑关系。
原理展开
- 表示方式：邻接矩阵适合稠密图，邻接表适合稀疏图。
- DFS/BFS 是图题基础模板。
- 并查集解决静态连通性，Dijkstra 解决非负权最短路，拓扑排序解决依赖顺序。
题型识别
- 岛屿类问题本质是网格图遍历。
- 课程表类问题本质是有向图拓扑排序。

2. 核心算法思想 ★★★

2.1 排序算法 ★★★

算法	时间(平均)	时间(最坏)	空间	稳定性
冒泡排序	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n²)	O(n²)	O(1)	稳定
归并排序	O(nlogn)	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(n²)	O(logn)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(1)	不稳定
计数排序	O(n+k)	O(n+k)	O(k)	稳定

核心结论
- 排序题重点不在于背表，而在于知道每种排序的适用场景、稳定性和优化方向。

快排：partition 思想、随机化 pivot

题型识别
- 面试要求手写排序时，快排和归并是高频。
模板
- 选基准。
- 分区，让小于基准的在左，大于基准的在右。
- 递归处理左右子区间。
易错点
- 分区边界和递归终止条件最容易写错。
- 大量重复元素时普通双路快排退化明显，可考虑三路快排。
口述方式
- “快排的核心不是交换，而是通过 partition 把问题拆成两个独立子区间。”

归并排序：分治思想、外部排序

核心结论
- 归并稳定，适合链表排序、外部排序和需要稳定性的场景。
易错点
- 合并时临时数组复制和左右边界处理容易出错。
面试常问：为什么 Arrays.sort() 用 TimSort？
- 核心结论：TimSort 综合利用局部有序性和归并思想，对真实业务数据表现更好。

2.2 二分查找 ★★★

核心结论
- 二分不是只能查“有序数组中的某个值”，它本质上是利用单调性缩小搜索空间。
题型识别
- 有序数组查找。
- 查第一个/最后一个满足条件的位置。
- 旋转数组查找。
- 二分答案，如最小可行值、最大化最小值。
模板
- 明确区间定义：闭区间 [left, right] 或左闭右开 [left, right)。
- 明确循环条件与收缩方式。
- 明确最终返回的是索引、值还是边界。
易错点
- left <= right 和 left < right 不能混写。
- 找边界题时，相等后收左还是收右要提前想清楚。
口述方式
- “我先确认问题是否有单调性，再决定二分查值还是二分答案。”

2.3 双指针 ★★★

核心结论
- 双指针的本质，是用两个位置关系替代双重循环。

快慢指针：链表中点、环检测

题型识别
- 找中点、找倒数第 k 个、判环、找环入口。
模板
- 快指针每次两步，慢指针每次一步。
- 利用相对速度差构造相遇。
易错点
- 快指针判空顺序写错容易空指针。

左右指针：两数之和、接雨水、盛水容器

核心结论
- 左右指针通常依赖单调性或排序结果。

滑动窗口 ★★★

模板
- 右指针扩张窗口。
- 窗口不满足条件时左指针收缩。
- 维护窗口状态，如次数表、和、最大值。
题型识别
- 子串、子数组、连续区间、最短/最长满足条件。
易错点
- 不要把“窗口合法时更新答案”和“窗口非法时收缩”顺序写乱。
口述方式
- “滑动窗口是用可维护状态描述当前连续区间，再通过左右指针动态平衡。”

2.4 递归与回溯 ★★★

核心结论
- 回溯不是暴力枚举的别名，而是“在搜索树上做选择、递归探索、撤销状态”的系统模板。
递归三要素
- 终止条件
- 递归操作
- 返回值或副作用含义

回溯模板：选择 → 递归 → 撤销

题型识别
- 排列、组合、子集、切割、棋盘类搜索。
模板
- 路径 path
- 选择列表
- 做选择
- 递归
- 撤销选择
易错点
- 去重逻辑分“树枝去重”和“树层去重”，最容易混。
- 忘记恢复状态会直接污染后续分支。
口述方式
- “我会把问题抽成一棵决策树，每一层做一个选择，回溯时恢复现场。”

2.5 动态规划(DP) ★★★

核心结论
- DP 的核心不是记忆化，而是把原问题拆成有重叠子问题的状态转移。
解题步骤
1. 定义状态：dp[i] 或 dp[i][j] 到底表示什么。
2. 写状态转移方程。
3. 确定初始条件。
4. 确定遍历顺序。
5. 再考虑空间优化。

经典题型

斐波那契/爬楼梯：一维线性 DP。
背包问题：0-1、完全、多重。
LIS/LCS：序列 DP。
编辑距离：双序列 DP。
股票买卖：状态机 DP。
打家劫舍：选择与不选择。
区间 DP：依赖更短区间。
题型识别
- 题目问“最优值”，且当前决策依赖前面若干状态，通常要警惕 DP。
易错点
- 没定义清楚 dp 含义就开始写方程，后面大概率全错。
- 背包压缩到一维时，遍历方向写反会改变题意。
口述方式
- “我会先把状态定义清楚，因为转移方程其实是状态定义的直接展开。”

2.6 贪心算法 ★★

核心结论
- 贪心的难点不在写法，而在证明局部最优能推出全局最优。
题型识别
- 区间选择、跳跃覆盖、资源分配、排序后逐步决策。
面试怎么答
- “如果我用贪心，一定要说明排序依据或选择依据为什么不会影响后续最优性。”

2.7 BFS/DFS ★★★

核心结论
- BFS 适合按层或最短步数，DFS 适合连通性、路径枚举和深度搜索。
题型识别
- 最短路径步数、按层扩展：BFS。
- 搜索所有方案、连通块染色：DFS。
模板
- BFS：队列 + 访问标记 + 按层推进。
- DFS：递归/栈 + 访问标记 + 回溯。
易错点
- 没有访问标记会重复遍历甚至死循环。
口述方式
- “我先判断题目是在求‘最短步数’还是‘能否/多少连通块’，再在 BFS 和 DFS 之间选。”

Dijkstra：单源最短路径，优先队列贪心；负权边用 Bellman-Ford

核心结论
- Dijkstra 依赖非负权这个前提，不能乱用到负权边图。

2.8 图论进阶 ★★

Union-Find(并查集) ★★★

核心结论
- 并查集擅长维护“谁和谁在一个集合里”，不擅长路径细节。
模板
- find 查根。
- union 合并。
- 优化：路径压缩 + 按秩合并。
题型识别
- 连通分量、朋友圈、冗余连接、最小生成树判环。
易错点
- 路径压缩和权值维护一起做时，更新顺序容易错。

最小生成树

Kruskal：边排序 + Union-Find，适合稀疏图。
Prim：从点出发逐步扩张，适合稠密图。

拓扑排序 ★★

核心结论
- 拓扑排序只适用于有向无环图，核心是依赖先后关系。

2.9 树的高级遍历 ★★

Morris遍历
- 核心结论：利用线索化思想在 O(1) 额外空间完成遍历。
- 面试怎么答：知道思想和适用场景即可，现场很少要求手写。

3. 高频题型分类 ★★★

3.1 数组

两数之和、三数之和
接雨水
合并区间
下一个排列
旋转数组
题型识别
- 看是否有排序、去重、区间合并、双指针或前缀状态。

3.2 链表

反转链表 / 反转链表II
合并两个有序链表 / 合并K个有序链表
环形链表 / 环形链表II
LRU缓存（哈希表 + 双向链表）
相交链表
模板
- Dummy Head
- 前驱/当前/后继三指针
- 快慢指针

3.3 字符串

最长回文子串
最长无重复子串
字符串匹配(KMP)
字母异位词
题型识别
- 子串问题优先考虑滑动窗口，模式匹配再考虑 KMP。

3.4 树

二叉树的最近公共祖先
二叉树的最大深度/最小深度
对称二叉树 / 翻转二叉树(镜像)
验证二叉搜索树
BST的插入与删除（删除节点找后继替换）
二叉树的层序遍历
二叉树的序列化与反序列化
二叉树路径和（从根到叶DFS）
口述方式
- “先说递归函数定义，再说左右子树怎么合并结果。”

3.5 图

岛屿数量（BFS/DFS标记）
课程表（拓扑排序）
连通分量（Union-Find）
单调栈：柱状图最大矩形
易错点
- 岛屿类题虽然长得像二维数组，本质仍是图遍历。

3.6 动态规划

最长递增子序列
编辑距离
零钱兑换
不同路径
最大子数组和
题型识别
- “最优值 + 重叠子问题 + 可枚举状态转移”。

二、刷题策略

P7面试准备

目标：LeetCode 150-200 题
难度：Easy(30%) + Medium(60%) + Hard(10%)
时间：每天 1-2 题，持续 4 周以上
方法
1. 按题型分类刷，不要随机刷。
2. 每道题限时 30 分钟，超时看题解，但必须自己复写。
3. 重点理解模板和边界，不要只背 AC 代码。
4. 做完后总结“题型识别词 + 模板 + 易错点”。
5. 3-5 天后必须复盘，否则很快遗忘。

面试中的算法技巧

先沟通思路，再写代码。
先给暴力解，再逐步优化。
边界条件要主动说：空数组、单元素、重复元素、溢出。
写完后口头跑样例和极端 case。
如果时间紧，优先写最稳模板，不要现场炫技巧。

三、高频面试题

必刷Top 20

两数之和

30秒答法
- 这题本质是“边遍历边查补数”。用哈希表记录已经见过的值和索引，当前数 num 只要发现 target - num 已存在，就能 O(1) 找到答案，整体 O(n)。
关键词
- 哈希表
- 补数
- 一次遍历
追问提醒
- 常追问如果数组有序怎么办，能否用双指针降空间。

反转链表

30秒答法
- 经典三指针模板：prev/curr/next。每次先保存后继，再把当前节点指向前驱，最后整体前进。递归写法更短，但面试里迭代更稳。
关键词
- 三指针
- 头插方向
- 断链保护
追问提醒
- 常追问反转前 N 个、K 组反转、局部反转。

LRU缓存

30秒答法
- LRU 要求 get/put 都是 O(1)，标准做法是 HashMap + 双向链表。哈希表负责定位节点，双向链表负责维护最近访问顺序，头部最新、尾部最旧。
关键词
- HashMap
- 双向链表
- O(1)
- 淘汰尾部
追问提醒
- 常追问线程安全版怎么做、为什么单链表不方便。

最长无重复子串

30秒答法
- 这是典型滑动窗口。右指针扩张窗口，哈希表记录字符最近位置，出现重复时移动左边界，过程中维护最大长度。
关键词
- 滑动窗口
- 最近位置
- 左边界收缩
追问提醒
- 继续准备最小覆盖子串和“至多 K 个不同字符”变体。

合并两个有序链表

30秒答法
- 用 dummy 头节点和双指针比较两个链表当前值，小的先接入结果链表，最后把剩余部分直接挂上去。重点是边界简洁。
关键词
- Dummy Head
- 双指针
- 有序合并
追问提醒
- 常追问合并 K 个有序链表，通常转最小堆或分治。

二叉树的层序遍历

30秒答法
- 层序遍历本质就是 BFS。用队列按层推进，每轮先记当前队列长度，就能把同一层节点一次性处理出来。
关键词
- BFS
- 队列
- 按层处理
追问提醒
- 常追问之字形遍历、右视图、最小深度。

最大子数组和

30秒答法
- 这题是 Kadane 算法。定义以当前位置结尾的最大子数组和，如果前面的和为负就直接丢掉，从当前元素重新开始，过程中维护全局最大值。
关键词
- Kadane
- 以 i 结尾
- 状态压缩
追问提醒
- 常追问如果要求返回区间，如何额外记录左右边界。

三数之和

30秒答法
- 先排序，再固定一个数，把另外两个数用左右指针夹逼。关键不是双指针本身，而是排序后的去重处理。
关键词
- 排序
- 双指针
- 去重
追问提醒
- 常追问四数之和、最接近三数之和。

接雨水

30秒答法
- 可以用双指针，也可以用单调栈。双指针做法更适合面试口述：维护左右最大高度，较低的一侧决定当前位置能接多少水。
关键词
- 左右最大值
- 双指针
- 单调栈
追问提醒
- 常追问为什么较低一侧可以先结算。

全排列

30秒答法
- 这是标准回溯题。路径里放当前选择，visited 标记已使用元素，递归到底收集答案，回溯时撤销选择。若有重复元素，要先排序并做同层去重。
关键词
- 回溯
- visited
- 同层去重
追问提醒
- 常追问组合、子集、N 皇后能否统一成一个搜索框架。

零钱兑换

30秒答法
- 这是完全背包的最小值模型。dp[i] 表示凑出金额 i 的最少硬币数，状态转移是 dp[i] = min(dp[i], dp[i-coin] + 1)。
关键词
- 完全背包
- 最小值
- 一维 DP
追问提醒
- 常追问零钱兑换 II、组合数和排列数的差异。

最长递增子序列

30秒答法
- 基础解法是 O(n²) DP，dp[i] 表示以 i 结尾的 LIS 长度。进阶解法是“贪心 + 二分”，维护一个递增数组，把每个数放到它该替换的位置，复杂度降到 O(nlogn)。
关键词
- LIS
- 贪心 + 二分
- 结尾最小
追问提醒
- 常追问为什么那个递增数组不一定是真实子序列。

二叉树的最近公共祖先

30秒答法
- 递归定义很关键：函数返回当前子树中是否找到 p 或 q。如果左右子树都找到了，当前节点就是 LCA；否则返回找到的那一边。
关键词
- 递归定义
- 左右子树
- LCA
追问提醒
- 常追问 BST 版本如何利用有序性优化。

合并区间

30秒答法
- 先按区间起点排序，再顺序扫描。当前区间如果和结果尾部重叠，就更新右边界；否则直接加入新段。
关键词
- 排序
- 扫描线
- 区间合并
追问提醒
- 常追问插入区间、最少箭引爆气球。

有效的括号

30秒答法
- 左括号入栈，右括号时检查栈顶是否匹配，最后栈为空才合法。关键是用映射统一三种括号对。
关键词
- 栈
- 匹配映射
- 左右括号
追问提醒
- 常追问最长有效括号，会转成 DP 或栈。

搜索旋转排序数组

30秒答法
- 还是二分，只是每次先判断哪一半有序，再看目标值是否落在有序半边里，从而决定保留哪一边。
关键词
- 旋转数组
- 有序半边
- 二分变体
追问提醒
- 常追问有重复元素时为什么会退化。

岛屿数量

30秒答法
- 遍历网格，遇到陆地就计数一次，并用 DFS 或 BFS 把整块连通陆地全部标记掉。这样每个格子只访问一次，复杂度 O(mn)。
关键词
- 网格图
- DFS/BFS
- 染色
追问提醒
- 常追问最大岛屿面积、岛屿周长、并查集做法。

买卖股票的最佳时机

30秒答法
- 一次交易版本最简单：维护历史最低价和当前最大利润，边遍历边更新即可，本质是状态机的极简版。
关键词
- 最低价
- 最大利润
- 状态机
追问提醒
- 常追问多次交易、冷冻期、手续费版本。

编辑距离

30秒答法
- 这是典型双序列 DP。dp[i][j] 表示前 i 个字符变成前 j 个字符的最少操作数，转移考虑插入、删除、替换三种操作。
关键词
- 双序列 DP
- 插删改
- dp[i][j]
追问提醒
- 常追问最长公共子序列和编辑距离的关系。

合并K个有序链表

30秒答法
- 两个主流解法：最小堆和分治。最小堆每次弹出当前最小节点，复杂度 O(NlogK)；分治是把 K 个链表两两合并，复杂度也能做到 O(NlogK)。
关键词
- 最小堆
- 分治
- O(NlogK)
追问提醒
- 可继续准备为什么不是 O(KN)、什么时候选堆更直观。

补充高频题

二叉树前中后序遍历（非递归实现）

30秒答法
- 前序、中序、后序都可以用栈模拟递归。中序的关键是一路向左压栈，后序常见写法是“根右左再反转”，或者用双标记法。
关键词
- 栈模拟
- 中序模板
- 后序反转
追问提醒
- 常追问 Morris 遍历为什么能做到 O(1) 空间。

快速排序与归并排序的对比？各自的优化？

30秒答法
- 快排平均快、原地、不稳定，适合内存敏感场景；归并稳定但需要额外空间，适合链表排序和外部排序。优化上，快排看 pivot 与重复元素处理，归并看小数组切换插入排序和自底向上实现。
关键词
- 稳定性
- 原地排序
- 分治
- 优化
追问提醒
- 常追问为什么工程实现不会直接用教科书版快排。

动态规划背包问题（0-1 背包与完全背包）

30秒答法
- 二者状态转移形式类似，关键区别在一维压缩后的遍历方向：0-1 背包倒序，防止同一物品重复使用；完全背包正序，因为同一物品可以重复选。
关键词
- 0-1 背包
- 完全背包
- 遍历方向
追问提醒
- 常追问组合数和排列数版本怎么区分。

链表常见操作：K组反转、环检测、有序合并

30秒答法
- 链表题底层模板其实就三类：指针重连、快慢指针、dummy 头节点。K 组反转是局部反转的扩展，环检测是快慢指针，合并是双指针。
关键词
- 指针重连
- 快慢指针
- Dummy Head
追问提醒
- 常继续问环入口为什么能用数学关系推出。

滑动窗口经典题型

30秒答法
- 一类是“最长/最短满足条件的连续区间”，一类是“固定窗口统计”。通用做法都是右扩左缩，关键是维护好窗口状态并明确何时更新答案。
关键词
- 连续区间
- 右扩左缩
- 计数状态
追问提醒
- 常追问最小覆盖子串为什么比无重复子串更难。

二分查找变体：查找第一个/最后一个位置、旋转数组最小值

30秒答法
- 变体二分的关键不在 mid 公式，而在区间定义和相等时边界往哪收。找左边界时相等继续压右边，找右边界时相等继续抬左边。
关键词
- 左边界
- 右边界
- 区间定义
追问提醒
- 常追问为什么边界题更推荐统一模板。

图的 BFS/DFS 应用：拓扑排序、连通分量

30秒答法
- 连通分量问题通常用 DFS/BFS 或并查集；拓扑排序则是有向无环图上的依赖处理，可用 Kahn 或 DFS 逆后序。
关键词
- DAG
- 入度
- 连通分量
追问提醒
- 常追问如果图里有环怎么办，如何检测。

堆排序过程？建堆为什么是 O(n)？

30秒答法
- 堆排序是先建大顶堆，再不断把堆顶换到数组末尾并下沉调整。建堆之所以是 O(n)，因为大量节点位于底层，虽然节点多，但每个节点下沉距离很短。
关键词
- 大顶堆
- siftDown
- 建堆 O(n)
追问提醒
- 常追问优先队列和堆排序的关系。

Union-Find（并查集）的实现及优化？带权并查集是什么？

30秒答法
- 并查集核心就两个操作：find 和 union。路径压缩把节点直接挂到根上，按秩合并减少树高。带权并查集是在这个基础上额外维护节点间关系权值。
关键词
- find
- union
- 路径压缩
- 按秩合并
追问提醒
- 常追问除法求值、等式方程类题怎么映射到带权并查集。