算法常见及经典题总结
面试算法常见及经典题总结
适用对象：Android / 客户端 / 后端社招与校招，面试环节有手写代码或算法笔试的候选人。
核心目标：不靠题海死记，而是掌握 题型识别 → 解题模板 → 举一反三 的迁移能力。
一、面试算法考什么
1.1 常见考察形式
| 形式 | 说明 | 建议 |
|---|---|---|
| 白板 / 在线 IDE 手写 | 1～2 道，45～60 分钟 | 先讲思路再写，注意边界 |
| 笔试多题 | 2～4 道，限时 | 先易后难，暴力可拿部分分 |
| 追问复杂度 | 几乎必问 | 时间 + 空间，能否优化 |
| 代码质量 | 变量命名、边界、可读性 | 主流程清晰，边界集中处理 |
1.2 面试官真正想看什么
- 能不能把题翻译成算法模型（排序？双指针？DP？）
- 能不能分析时间空间复杂度
- 能不能处理边界（空、单元素、重复、溢出）
- 能不能在提示下优化（O(n²) → O(n)）
- 代码是否可维护（不过度炫技）
1.3 备考策略
不要：按题号刷 500 道，做完就忘
要做：
1. 掌握 12～15 个核心模式（本文第二节）
2. 每个模式精做 3～5 道经典题
3. 每道题总结「识别信号 + 模板 + 变体」
4. 二刷时遮住答案，15 分钟内独立完成二、题型识别总表（先认模式，再套模板）
| 识别信号 | 首选模式 | 典型关键词 |
|---|---|---|
| 两数 / 三数之和、去重配对 | 哈希 + 双指针 | sum、pair、duplicate |
| 连续子数组 / 子串最值 | 滑动窗口 | 连续、最长、最短、满足条件 |
| 有序数组查找 / 答案单调 | 二分 | 排序、第 k 大、最小化最大值 |
| 链表反转、环、合并 | 链表双指针 | next、cycle、merge |
| 括号匹配、单调性 | 栈 | 有效括号、每日温度 |
| 树的路径、遍历、最近公共祖先 | 树 DFS/BFS | root、path、level |
| 全排列、组合、子集 | 回溯 | 所有可能、不重复组合 |
| 最优子结构 + 重叠子问题 | 动态规划 | 最大/最小、方案数、能否达到 |
| 局部最优能推全局 | 贪心 | 区间、调度、跳跃 |
| 连通分量、冗余边 | 并查集 | 岛屿、朋友圈、最小生成树基础 |
| TopK、流式第 K 大 | 堆 | 前 K 个、中位数、合并 K 路 |
| 只出现一次、异或性质 | 位运算 | 缺失数字、只出现一次 |
三、模式详解 + 经典题 + 举一反三
模式 1：哈希表（HashMap / HashSet）
核心思想
用 O(1) 查找 把「枚举配对」变成「一次遍历」。
经典题 1：两数之和（LeetCode 1）
题意：数组 nums、目标 target，找两数下标使和为 target。
思路
遍历 nums[i]：
需要 complement = target - nums[i]
若 map 里已有 complement → 返回答案
否则 map[nums[i]] = i复杂度：O(n) 时间，O(n) 空间。
代码骨架（Kotlin）
fun twoSum(nums: IntArray, target: Int): IntArray {
val map = HashMap<Int, Int>()
nums.forEachIndexed { i, v ->
val need = target - v
map[need]?.let { return intArrayOf(it, i) }
map[v] = i
}
return intArrayOf()
}举一反三
| 变体题 | 变化点 | 思路迁移 |
|---|---|---|
| 三数之和（15） | 固定一个数，剩下降为「两数之和」 | 排序 + 双指针；去重跳过相同元素 |
| 四数之和（18） | 两重循环固定 | 排序 + 双指针，注意剪枝 |
| 两数之和 II（167） | 数组已排序 | 双指针左右夹逼，无需哈希 |
| 存在重复元素（217） | 判断是否有重复 | HashSet 边遍历边 contains |
| 字母异位词分组（49） | 字符串分组 | 用「排序后字符串」或「26 字母计数」作 key |
| 最长连续序列（128） | 连续数字最长长度 | Set 存所有数；只从序列起点扩展 |
| 和为 K 的子数组（560） | 连续子数组 | 前缀和 + HashMap 记「前缀和出现次数」 |
迁移口诀：
需要「有没有凑成 X」→ 先想哈希；需要「连续子数组和」→ 前缀和 + 哈希。
模式 2：双指针
核心思想
两个下标协同移动，把 O(n²) 枚举降为 O(n)。
子类型
| 类型 | 移动方式 | 场景 |
|---|---|---|
| 对撞指针 | left++ / right-- | 有序数组求和、回文、盛水 |
| 快慢指针 | slow / fast | 链表环、去重、原地修改 |
| 同向双指针 | 滑动窗口特例 | 移动零、移除元素 |
经典题 2：盛最多水的容器（11）
思路
left = 0, right = n - 1
面积 = min(height[left], height[right]) * (right - left)
每次移动较短的那一侧（因为宽度一定变小，只有抬高短板才可能更大）经典题 3：删除有序数组中的重复项（26）
思路：slow 指向已去重区间末尾，fast 扫描；不同则 slow++ 并赋值。
举一反三
| 变体题 | 模式 |
|---|---|
| 验证回文串（125） | 对撞指针跳过非字母数字 |
| 三数之和（15） | 固定 i + 对撞指针 |
| 接雨水（42） | 对撞或单调栈（见模式 6） |
| 链表环入口（142） | 快慢指针相遇后，一指针从头走 |
| 链表中倒数第 K 个（19） | 快指针先走 K 步 |
| 合并两个有序数组（88） | 从尾部双指针填入 |
| 移动零（283） | slow 维护非零区，fast 扫描 |
迁移口诀：
有序 + 配对 → 对撞；链表 + 位置/环 → 快慢；原地修改数组 → slow/fast 同向。
模式 3：滑动窗口
核心思想
维护区间 [left, right]，右扩左缩，使窗口满足（或恰好不满足）某条件。
模板
left = 0
for right in 0..n-1:
将 nums[right] 纳入窗口（更新 count / sum）
while 窗口不满足条件:
将 nums[left] 移出窗口
left++
更新答案（最长 / 最短 / 计数）经典题 4：无重复字符的最长子串（3）
思路：HashMap 记字符最后出现下标；若重复且在下标 ≥ left，则 left = last + 1。
经典题 5：最小覆盖子串（76）
思路：need / window 两个 Map；valid 计数；右扩直到满足，再左缩取最短。
举一反三
| 变体题 | 窗口维护什么 |
|---|---|
| 长度最小的子数组（209） | 和 ≥ target，求最短 → 满足时左缩 |
| 找到字符串中所有字母异位词（438） | 固定窗口长度 + 计数比较 |
| 水果成篮（904） | 最多两种字符 → 种类数 > 2 则左缩 |
| K 个不同整数的子数组（992） | 至多 K 种 → 转化为「atMost(K) - atMost(K-1)」 |
| 滑动窗口最大值（239） | 单调递减队列（见模式 6） |
迁移口诀：
「连续子串 / 子数组」+ 最长/最短/满足条件 → 滑动窗口；固定长度窗口 → 右扩时同步左移。
模式 4：二分查找
核心思想
答案空间或数组具有 单调性，每次排除一半。
两种写法
| 类型 | 场景 | 要点 |
|---|---|---|
| 标准二分 | 找 exact target | while (left <= right) |
| 边界二分 | 找第一个 ≥ x / 最后一个 < x | 缩区间，最后 check |
经典题 6：搜索旋转排序数组（33）
思路：nums[mid] 与 nums[left] 比，判断哪半边有序，再判断 target 是否在有序半边。
经典题 7：在排序数组中查找元素的第一个和最后一个位置（34）
思路：两次二分，分别找左边界和右边界。
举一反三
| 变体题 | 二分对象 |
|---|---|
| 搜索插入位置（35） | 标准 lower_bound |
| x 的平方根（69） | 答案在 [0, x] |
| 寻找峰值（162） | mid 与邻居比，往更大一侧走 |
| 搜索二维矩阵（74） | 拉平成一维二分或从右上/左下走 |
| 爱吃香蕉的珂珂（875） | 二分「速度」，check 能否吃完 |
| 分割数组的最大值（410） | 二分「最大子段和」，check 段数 |
| 寻找两个正序数组的中位数（4） | 二分较短数组的划分位置 |
迁移口诀：
「最小化最大值 / 最大化最小值」→ 二分答案 + check 函数；有序或旋转有序 → 二分下标。
模式 5：链表
必背操作
- 虚拟头节点
dummy：简化头删、合并 - 反转：
prev / curr / next三指针 - 快慢指针：中点、环、倒数第 K
经典题 8：反转链表（206）
fun reverseList(head: ListNode?): ListNode? {
var prev: ListNode? = null
var curr = head
while (curr != null) {
val next = curr.next
curr.next = prev
prev = curr
curr = next
}
return prev
}经典题 9：合并两个有序链表（21）
思路：dummy 尾插，较小者接上；最后接上剩余段。
经典题 10：环形链表 II（142）
思路：快慢相遇后，slow 从头、fast 从相遇点同步走，相遇即环入口（距离关系推导）。
举一反三
| 变体题 | 要点 |
|---|---|
| 两数相加（2） | 虚拟头 + 进位 |
| 删除链表的倒数第 N 个（19） | 快先走 N+1，删 slow.next |
| 重排链表（143） | 找中点 → 反转后半 → 交替合并 |
| K 个一组翻转链表（25） | 分组反转，记录组间连接 |
| 相交链表（160） | 双指针走 A+B / B+A 等长 |
| 排序链表（148） | 归并排序，找中点拆分 |
迁移口诀：
链表题先想 dummy；要改指向先保存 next；环/中点/倒数 → 快慢指针。
模式 6：栈与单调栈
核心思想
- 栈：最近匹配、逆序处理、DFS 迭代
- 单调栈：每个元素左右第一个更大/更小，O(n)
经典题 11：有效的括号（20）
思路：遇左括号入栈；遇右括号检查栈顶匹配。
经典题 12：每日温度（739）
思路：单调递减栈存下标；当前温度大于栈顶对应温度时弹出并算天数差。
经典题 13：柱状图中最大的矩形（84）
思路：单调递增栈；弹出时以弹出高度为高，宽度由当前 i 与栈顶下标算。
举一反三
| 变体题 | 栈类型 |
|---|---|
| 最小栈（155） | 辅助栈同步最小值 |
| 逆波兰表达式（150） | 遇数字入栈，遇运算符弹两个 |
| 字符串解码（394） | 双栈：数字栈 + 字符串栈 |
| 接雨水（42） | 单调栈或双指针 |
| 滑动窗口最大值（239） | 单调递减队列 |
| 下一个更大元素 I（496） | 单调栈 + 哈希 |
迁移口诀：
「下一个更大/更小」→ 单调栈；嵌套结构 → 栈存状态。
模式 7：二叉树 DFS / BFS
DFS 模板（递归）
fun dfs(node: TreeNode?, ...) {
if (node == null) return
// 前序位置
dfs(node.left, ...)
// 中序位置
dfs(node.right, ...)
// 后序位置
}BFS 模板（层序）
val queue = ArrayDeque<TreeNode>()
queue.add(root)
while (queue.isNotEmpty()) {
val size = queue.size
repeat(size) {
val node = queue.removeFirst()
// 处理 node
node.left?.let { queue.add(it) }
node.right?.let { queue.add(it) }
}
}经典题 14：二叉树的最大深度（104）
思路：1 + max(dfs(left), dfs(right))，后序位置聚合。
经典题 15：二叉树的最近公共祖先（236）
思路：后序；若 root 为 p 或 q 返回 root；左右都非空则 root 为 LCA。
经典题 16：二叉树层序遍历（102）
思路：BFS 按层 size 批量出队。
举一反三
| 变体题 | DFS / BFS |
|---|---|
| 相同的树（100） | 同步 DFS 比较 |
| 翻转二叉树（226） | 交换左右递归 |
| 路径总和（112） | 前序减 target，叶节点判断 |
| 路径总和 III（437） | 前缀和 + HashMap（树上前缀和） |
| 二叉搜索树验证（98） | DFS 带 (min, max) 区间 |
| 将有序数组转换为 BST（108） | 递归中点作根 |
| 二叉树的右视图（199） | BFS 每层最后一个 |
| 二叉树展开为链表（114） | 后序或 Morris |
迁移口诀：
自底向上聚合 → 后序；路径问题 → 前序 + 回溯；按层 → BFS；BST → 中序或区间约束。
模式 8：回溯（Backtracking）
核心思想
DFS + 显式撤销选择，枚举所有合法方案。
模板
fun backtrack(path: MutableList<Int>, ...) {
if (满足结束条件) {
ans.add(path.toList())
return
}
for (选择 in 选择列表) {
if (剪枝) continue
做选择
backtrack(path, ...)
撤销选择
}
}经典题 17：全排列（46）
思路：used 数组标记；每层选一个未使用的数。
经典题 18：子集（78）
思路：每个位置选或不选；或起点 start 递增选，避免重复。
经典题 19：组合总和（39）
思路：可重复选 → 递归时 start 从当前 i 开始，不回头。
举一反三
| 变体题 | 剪枝要点 |
|---|---|
| 全排列 II（47） | 排序 + 同层去重 i > 0 && nums[i]==nums[i-1] && !used[i-1] |
| 组合（77） | 只选 n 个，start 递增 |
| 组合总和 II（40） | 排序 + 同层去重，每个数用一次 |
| 括号生成（22） | 左 < n 可加左；右 < 左 可加右 |
| 单词搜索（79） | 网格 DFS + visited |
| N 皇后（51） | 列、主对角、副对角占用 |
| 分割回文串（131） | 切分 + 判断子串回文 |
迁移口诀：
「所有方案」→ 回溯；有重复元素 → 排序 + 同层去重；可重复选 → start 不从 0 重开。
模式 9：动态规划（DP）
识别条件
- 最优子结构
- 重叠子问题（记忆化或表格）
- 能写出状态转移方程
DP 解题四步
1. 定义状态 dp[i] / dp[i][j] 表示什么
2. 转移方程
3. 初始条件
4. 遍历顺序（保证依赖已计算）经典题 20：爬楼梯（70）
dp[i] = dp[i-1] + dp[i-2]，可压缩为两个变量。
经典题 21：最长递增子序列（300）
dp[i] = 以 i 结尾的 LIS 长度；内层 j < i 且 nums[j] < nums[i] 转移。
优化：耐心排序 + 二分 → O(n log n)。
经典题 22：零钱兑换（322）
dp[amount] = 凑 amount 最少硬币数；完全背包正向遍历。
经典题 23：最长公共子序列（1143）
if (s1[i]==s2[j]) dp[i][j] = dp[i-1][j-1] + 1
else dp[i][j] = max(dp[i-1][j], dp[i][j-1])经典题 24：编辑距离（72）
增删改三种操作，dp[i][j] 为 s1[0..i) 到 s2[0..j) 最小编辑次数。
DP 子类与举一反三
| 子类 | 代表题 | 状态设计 |
|---|---|---|
| 线性 DP | 打家劫舍（198） | dp[i] 与 i-1、i-2 关系 |
| 0-1 背包 | 分割等和子集（416） | dp[j] 能否凑重量 j，逆序遍历 |
| 完全背包 | 完全平方数（279） | 正序遍历 |
| 区间 DP | 戳气球（312） | dp[i][j] 开区间最优 |
| 状态机 DP | 买卖股票含冷冻期（309） | 持有/不持有/冷冻 |
| 树形 DP | 打家劫舍 III（337） | 节点返回 (抢, 不抢) |
| 路径 DP | 不同路径（62） | 网格 dp[i][j] |
| 字符串 DP | 最长回文子串（5） | 中心扩展或 dp[i][j] |
迁移口诀：
方案数 → 加法转移；最值 → min/max；能否达到 → boolean；二维串 → 双串 DP；选或不选 → 背包。
模式 10：贪心
核心思想
每步做局部最优，需证明能推出全局最优（面试可说「交换论证」思路）。
经典题 25：跳跃游戏（55）
思路：维护能到达的最远位置 maxReach，遍历中若 i > maxReach 失败。
经典题 26：无重叠区间（435）
思路：按区间右端点排序，贪心选结束最早的，能留最多区间。
经典题 27：分发饼干（455）
思路：排序后双指针，小饼干满足小孩子。
举一反三
| 变体题 | 贪心策略 |
|---|---|
| 跳跃游戏 II（45） | 当前步最远边界内选下一步最远 |
| 合并区间（56） | 按起点排序，能合并则扩右端点 |
| 用最少数量的箭引爆气球（452） | 同无重叠区间，按右端点 |
| 划分字母区间（763） | 记录各字符最后出现位置，扩展当前段 |
| 任务调度器（621） | 公式 (n+1)*(maxCount-1)+sameMax |
模式 11：堆（优先队列）
核心思想
动态维护 TopK 或当前最值，插入删除 O(log n)。
经典题 28：数组中的第 K 个最大元素（215）
思路：大小为 K 的小顶堆；或快速选择 O(n) 平均。
经典题 29：合并 K 个升序链表（23）
思路：小顶堆存各链表头节点，每次弹出最小接上。
经典题 30：数据流的中位数（295）
思路：大顶堆存较小一半，小顶堆存较大一半，保持平衡。
举一反三
| 变体题 | 堆用法 |
|---|---|
| 前 K 个高频元素（347） | 频次入堆 |
| 滑动窗口最大值（239） | 单调队列更优 |
| 查找和最小的 K 对数字（373） | 堆存 (sum, i, j) |
模式 12：并查集（Union-Find）
模板
class UnionFind(n: Int) {
private val parent = IntArray(n) { it }
private val rank = IntArray(n)
fun find(x: Int): Int {
if (parent[x] != x) parent[x] = find(parent[x])
return parent[x]
}
fun union(a: Int, b: Int): Boolean {
val ra = find(a)
val rb = find(b)
if (ra == rb) return false
if (rank[ra] < rank[rb]) parent[ra] = rb
else {
parent[rb] = ra
if (rank[ra] == rank[rb]) rank[ra]++
}
return true
}
}经典题 31：省份数量（547）
思路：邻接矩阵，遍历 union(i,j)，数根节点个数。
经典题 32：冗余连接（684）
思路：加边时若两端已连通则该边冗余。
举一反三
| 变体题 | 并查集作用 |
|---|---|
| 岛屿数量（200） | DFS/BFS 也可；并查集合并陆地 |
| 账户合并（721） | 按邮箱 union |
| 最长连续序列（128） | 也可用 Set，并查集合并相邻数字 |
模式 13：图 BFS / DFS
经典题 33：岛屿数量（200）
思路：遍历网格，'1' 则 dfs 沉岛（标记 visited）并 count++。
经典题 34：课程表（207）
思路：拓扑排序，BFS 入度为 0 或 DFS 三色标记判环。
举一反三
| 变体题 | 方法 |
|---|---|
| 腐烂的橘子（994） | 多源 BFS |
| 单词接龙（127） | BFS 最短路径 |
| 网络延迟时间（743） | Dijkstra 或 BFS+堆 |
模式 14：位运算
常用技巧
| 技巧 | 式子 |
|---|---|
| 取最低位 1 | x & (-x) |
| 去掉最低位 1 | x & (x - 1) |
| 判断 2 的幂 | x > 0 && (x & (x-1)) == 0 |
| 异或性质 | a^a=0, a^0=a，可消重复 |
经典题 35：只出现一次的数字（136）
思路：全体异或。
经典题 36：位 1 的个数（191）
思路：n & (n-1) 直到为 0。
举一反三
| 变体题 | 技巧 |
|---|---|
| 缺失数字（268） | 0..n 异或 |
| 汉明距离（461） | x xor y 再数 1 |
| 颠倒二进制位（190） | 逐位取出 |
四、经典必刷题单（按优先级）
4.1 第一梯队：必须熟练（各模式代表）
| 题号 | 题目 | 模式 |
|---|---|---|
| 1 | 两数之和 | 哈希 |
| 3 | 无重复字符的最长子串 | 滑动窗口 |
| 15 | 三数之和 | 双指针 |
| 20 | 有效的括号 | 栈 |
| 21 | 合并两个有序链表 | 链表 |
| 53 | 最大子数组和 | DP / 贪心 |
| 70 | 爬楼梯 | DP |
| 76 | 最小覆盖子串 | 滑动窗口 |
| 102 | 二叉树层序遍历 | BFS |
| 104 | 二叉树最大深度 | DFS |
| 121 | 买卖股票的最佳时机 | DP |
| 142 | 环形链表 II | 快慢指针 |
| 146 | LRU 缓存 | 哈希 + 双向链表 |
| 200 | 岛屿数量 | DFS/BFS |
| 206 | 反转链表 | 链表 |
| 215 | 数组第 K 个最大 | 堆 |
| 236 | 二叉树最近公共祖先 | 树 DFS |
| 322 | 零钱兑换 | 完全背包 |
| 347 | 前 K 个高频元素 | 堆 |
| 416 | 分割等和子集 | 0-1 背包 |
4.2 第二梯队：高频加深
| 题号 | 题目 | 模式 |
|---|---|---|
| 11 | 盛最多水的容器 | 双指针 |
| 33 | 搜索旋转排序数组 | 二分 |
| 42 | 接雨水 | 双指针 / 单调栈 |
| 46 | 全排列 | 回溯 |
| 56 | 合并区间 | 排序 + 贪心 |
| 78 | 子集 | 回溯 |
| 79 | 单词搜索 | 回溯 |
| 84 | 柱状图最大矩形 | 单调栈 |
| 128 | 最长连续序列 | 哈希 Set |
| 139 | 单词拆分 | DP |
| 141 | 环形链表 | 快慢指针 |
| 148 | 排序链表 | 归并 |
| 152 | 乘积最大子数组 | DP |
| 198 | 打家劫舍 | 线性 DP |
| 207 | 课程表 | 拓扑 |
| 239 | 滑动窗口最大值 | 单调队列 |
| 240 | 搜索二维矩阵 II | 分治走指针 |
| 279 | 完全平方数 | 完全背包 |
| 300 | 最长递增子序列 | DP |
| 322 | 零钱兑换 | DP |
| 437 | 路径总和 III | 树 + 前缀和 |
| 438 | 找到字母异位词 | 滑动窗口 |
| 560 | 和为 K 的子数组 | 前缀和 + 哈希 |
| 739 | 每日温度 | 单调栈 |
| 1143 | 最长公共子序列 | 双串 DP |
4.3 第三梯队：架构 / 高级岗位加分
| 题号 | 题目 | 说明 |
|---|---|---|
| 4 | 寻找两个正序数组中位数 | 二分划分 |
| 23 | 合并 K 个升序链表 | 堆 |
| 25 | K 个一组翻转链表 | 链表难点 |
| 32 | 最长有效括号 | 栈 / DP |
| 72 | 编辑距离 | 经典二维 DP |
| 84 | 柱状图中最大的矩形 | 单调栈经典 |
| 124 | 二叉树最大路径和 | 树形 DP |
| 128 | 最长连续序列 | O(n) 思维 |
| 146 | LRU 缓存 | 设计题必考 |
| 295 | 数据流中位数 | 双堆 |
| 312 | 戳气球 | 区间 DP |
五、举一反三方法论（如何从一题扩展到一类）
5.1 四步迁移法
1. 抽象原题：我在「枚举什么」？瓶颈是什么？
2. 识别结构：有序？连续？树？选或不选？
3. 换约束：个数变 K、重复变不可重复、最大变最小
4. 换数据结构：哈希 → 排序双指针；DFS → BFS；数组 → 树5.2 经典迁移链（建议整链练习）
链 A：两数之和 → 三数之和 → 四数之和 → 最接近的三数之和
哈希 O(n) → 排序+双指针 O(n²) → 多一层循环 → 维护最小差值链 B：爬楼梯 → 打家劫舍 → 打家劫舍 II（环）→ 打家劫舍 III（树）
线性递推 → 不能相邻 → 首尾特殊 → 树形返回双状态链 C：子集 → 组合 → 排列 → 含重复元素的去重
start 递增 → 固定长度 → used 标记 → 排序+同层剪枝链 D：最大子数组和 → 乘积最大子数组 → 环形子数组和
Kadane → 维护 min/max 乘积 → 总和减最小子数组和链 E：反转链表 → K 组翻转 → 重排链表 → 合并 K 链表
单组反转 → 分段 → 找中点+反转+合并 → 堆优化5.3 面试官追问时的升级路径
| 初始解法 | 追问 | 升级方向 |
|---|---|---|
| 暴力 O(n²) | 能否 O(n)？ | 哈希、双指针、单调栈 |
| O(n) 额外数组 | 能否 O(1) 空间？ | 原地交换、读写指针 |
| 递归 DFS | 数据很大栈溢出？ | 改迭代 + 显式栈 |
| TopK 排序 O(n log n) | 能否更快？ | 堆 O(n log k) 或快选 O(n) |
六、复杂度速查
| 操作 | 平均 | 最坏 |
|---|---|---|
| HashMap get/put | O(1) | O(n) |
| 快排 | O(n log n) | O(n²) |
| 堆 push/pop | O(log n) | O(log n) |
| 二分 | O(log n) | O(log n) |
| DFS/BFS 图 | O(V+E) | O(V+E) |
空间复杂度常见来源：哈希 O(n)、递归栈 O(h)、BFS 队列 O(w)、DP 表 O(n) 或 O(n²)。
七、手写代码注意事项
7.1 边界清单（写完必查）
□ 空输入：null、[]、""
□ 单元素
□ 两元素极端
□ 重复元素
□ 整数溢出（Kotlin 一般无此问题，Java 需注意）
□ 链表：空、单节点、环
□ 树：空树、单支、只有左/右7.2 面试沟通模板
1. 复述题意 + 确认输入输出与约束
2. 举例：正常 case + 边界 case
3. 暴力思路 → 瓶颈 → 优化思路
4. 写代码（主逻辑优先，边界可后补）
5. 口述复杂度
6. 主动提测试用例走一遍7.3 Android 面试常见语言
- Kotlin：社招 Android 越来越多，本文代码以 Kotlin 为例
- Java：老牌大厂笔试仍常见，语法与 Kotlin 思路一致
- 建议：同一模板用一门语言练熟，另一门能看懂即可
八、八周刷题计划
第 1～2 周：基础模式
| 天 | 内容 | 题（LeetCode 号） |
|---|---|---|
| 1-2 | 哈希 | 1, 217, 49 |
| 3-4 | 双指针 | 15, 11, 26 |
| 5-6 | 滑动窗口 | 3, 209, 438 |
| 7 | 复盘 | 重做错题 |
第 3～4 周：链表 + 栈 + 二分
| 天 | 内容 | 题 |
|---|---|---|
| 1-2 | 链表 | 206, 21, 141, 142 |
| 3-4 | 栈 | 20, 155, 739 |
| 5-6 | 二分 | 33, 34, 35 |
| 7 | 复盘 |
第 5～6 周：树 + 回溯
| 天 | 内容 | 题 |
|---|---|---|
| 1-3 | 树 DFS/BFS | 104, 102, 236, 98 |
| 4-6 | 回溯 | 46, 78, 39, 22 |
| 7 | 复盘 |
第 7～8 周：DP + 贪心 + 综合
| 天 | 内容 | 题 |
|---|---|---|
| 1-2 | 线性 DP | 70, 198, 53, 152 |
| 3-4 | 背包 | 322, 416, 139 |
| 5 | 贪心 | 55, 56, 435 |
| 6 | 堆 / 并查集 | 215, 347, 200 |
| 7-8 | 模拟面试 | 146, 76, 72 任选 |
九、设计类常考题
9.1 LRU 缓存（146）
思路：HashMap<key, Node> + 双向链表；get/put 时把节点移到头部；超容量删尾部。
举一反三：LFU 缓存（460）→ 多一个频次维度 + 每层双向链表。
9.2 Min Stack（155）
思路：数据栈 + 辅助栈同步压入当前最小值。
9.3 实现 Trie（208）
思路：子节点数组/Map，isEnd 标记；前缀树支撑自动补全、单词搜索 II。
十、与 Android 开发的联系（面试加分表述）
| 算法模式 | 工程场景 |
|---|---|
| LRU | Bitmap 缓存、网络图片库 |
| 拓扑排序 | 模块依赖、任务编排 |
| 并查集 | 连通性、分组 |
| 滑动窗口 | 埋点窗口统计、限流 |
| 堆 | 优先级任务队列 |
| 双指针 | 归并、去重、Diff 类思路 |
| 位运算 | 权限 flag、状态位掩码 |
能在答完题后补一句工程关联，会体现 学以致用，尤其适合 Android 架构岗。
十一、最终应达到的水平
合格的面试算法能力：
- 见到 medium 题 10～15 分钟内 说出正确模式
- 第一梯队 20 题 能独立手写无重大 bug
- 能口述 时间空间复杂度 并给出优化方向
- 能 举一反三：同类变体换约束后知道改哪里
- 代码 边界完整，沟通清晰
十二、最短路径
1. 背熟第二节「题型识别总表」
2. 精做第三节每个模式的「经典题 1」
3. 按第四节第一梯队 20 题过关
4. 每题写三行：识别信号 / 模板 / 一个变体
5. 第八节八周计划或考前集中二刷一句话总结：
面试算法不是背 500 道题，而是掌握 十几种模式 + 经典题锚点 + 举一反三的迁移链。
附录：LeetCode 题号速查索引
| 模式 | 题号 |
|---|---|
| 哈希 | 1, 49, 128, 217, 347, 560 |
| 双指针 | 11, 15, 26, 42, 88, 125, 167, 283 |
| 滑动窗口 | 3, 76, 209, 239, 438, 567 |
| 二分 | 33, 34, 35, 69, 74, 162, 875 |
| 链表 | 19, 21, 23, 141, 142, 148, 206, 234 |
| 栈 | 20, 84, 155, 394, 739, 84 |
| 树 | 94, 98, 100, 102, 104, 105, 114, 199, 226, 236, 297 |
| 回溯 | 17, 22, 39, 40, 46, 47, 51, 78, 79, 131 |
| DP | 5, 53, 62, 70, 72, 121, 139, 152, 198, 279, 300, 322, 416, 1143 |
| 贪心 | 45, 55, 56, 122, 435, 452, 621, 763 |
| 堆 | 23, 215, 295, 347, 373 |
| 并查集 | 200, 547, 684, 721 |
| 图 | 127, 200, 207, 994, 743 |
| 位运算 | 136, 190, 191, 268, 461 |
| 设计 | 146, 155, 208, 460 |