Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

LeetCode Hot 100 算法清单

本清单即 LeetCode 热题 HOT 100,共 100 题,业界公认的标准刷题集。分类与顺序合理:按「数据结构由易到难 + 算法思想递进」组织。

针对你的定位(中级 Android 转应用):Android 算法面试以中等题为主。下方每个分类标注了 ⭐(高频必刷)和 △(偏难/低频,可缓刷),按优先级投入精力。

如何使用

  • 第一轮:只刷 ⭐ 高频题,建立每类的解题模板(约 40 题),覆盖大部分中小厂。
  • 第二轮:补齐其余中等题,冲大厂。
  • 第三轮:△ 难题(困难/低频)按目标公司选刷。
  • 每类先吃透 1-2 道“母题“模板,其余是变体。重在模板内化而非数量。

进度自测

勾选格式 - [x]。⭐=高频必刷,△=可缓刷。

哈希表(3)

  • ⭐ 1. 两数之和(简单)
  • 49. 字母异位词分组(中等)
  • 128. 最长连续序列(中等)

双指针(4)

  • ⭐ 283. 移动零
  • ⭐ 11. 盛最多水的容器
  • ⭐ 15. 三数之和
  • △ 42. 接雨水(困难)

滑动窗口(5)

  • ⭐ 3. 无重复字符的最长子串
  • 438. 找到字符串中所有字母异位词
  • ⭐ 560. 和为 K 的子数组
  • △ 239. 滑动窗口最大值(困难)
  • △ 76. 最小覆盖子串(困难)

普通数组(5)

  • ⭐ 53. 最大子数组和
  • ⭐ 56. 合并区间
  • ⭐ 189. 轮转数组
  • 238. 除自身以外数组的乘积
  • △ 41. 缺失的第一个正数(困难)

矩阵(4)

  • 73. 矩阵置零
  • ⭐ 54. 螺旋矩阵
  • 48. 旋转图像
  • 240. 搜索二维矩阵 II

链表(14)

  • ⭐ 160. 相交链表
  • ⭐ 206. 反转链表
  • 234. 回文链表
  • ⭐ 141. 环形链表
  • ⭐ 142. 环形链表 II
  • ⭐ 21. 合并两个有序链表
  • 2. 两数相加
  • ⭐ 19. 删除链表的倒数第 N 个结点
  • 24. 两两交换链表中的节点
  • △ 25. K 个一组翻转链表(困难)
  • 138. 随机链表的复制
  • 148. 排序链表
  • △ 23. 合并 K 个升序链表(困难)
  • ⭐ 146. LRU 缓存

二叉树(15)

  • ⭐ 94. 二叉树的中序遍历
  • ⭐ 104. 二叉树的最大深度
  • ⭐ 226. 翻转二叉树
  • ⭐ 101. 对称二叉树
  • 543. 二叉树的直径
  • ⭐ 102. 二叉树的层序遍历
  • 108. 将有序数组转换为二叉搜索树
  • ⭐ 98. 验证二叉搜索树
  • 230. 二叉搜索树中第 K 小的元素
  • 199. 二叉树的右视图
  • 114. 二叉树展开为链表
  • 105. 从前序与中序遍历序列构造二叉树
  • 437. 路径总和 III
  • ⭐ 236. 二叉树的最近公共祖先
  • △ 124. 二叉树中的最大路径和(困难)

图论(4)

  • ⭐ 200. 岛屿数量
  • 994. 腐烂的橘子
  • ⭐ 207. 课程表
  • 208. 实现 Trie (前缀树)

回溯(8)

  • ⭐ 46. 全排列
  • ⭐ 78. 子集
  • 17. 电话号码的字母组合
  • 39. 组合总和
  • 22. 括号生成
  • 79. 单词搜索
  • 131. 分割回文串
  • △ 51. N 皇后(困难)

二分查找(6)

  • ⭐ 35. 搜索插入位置
  • 74. 搜索二维矩阵
  • ⭐ 34. 在排序数组中查找元素的第一个和最后一个位置
  • ⭐ 33. 搜索旋转排序数组
  • 153. 寻找旋转排序数组中的最小值
  • △ 4. 寻找两个正序数组的中位数(困难)

栈(5)

  • ⭐ 20. 有效的括号
  • ⭐ 155. 最小栈
  • 394. 字符串解码
  • ⭐ 739. 每日温度
  • △ 84. 柱状图中最大的矩形(困难)

堆(3)

  • ⭐ 215. 数组中的第K个最大元素
  • ⭐ 347. 前 K 个高频元素
  • △ 295. 数据流的中位数(困难)

贪心(4)

  • ⭐ 121. 买卖股票的最佳时机
  • ⭐ 55. 跳跃游戏
  • 45. 跳跃游戏 II
  • 763. 划分字母区间

动态规划 - 单维(10)

  • ⭐ 70. 爬楼梯
  • 118. 杨辉三角
  • ⭐ 198. 打家劫舍
  • 279. 完全平方数
  • ⭐ 322. 零钱兑换
  • 139. 单词拆分
  • ⭐ 300. 最长递增子序列
  • 152. 乘积最大子数组
  • 416. 分割等和子集
  • △ 32. 最长有效括号(困难)

动态规划 - 多维(5)

  • ⭐ 62. 不同路径
  • 64. 最小路径和
  • ⭐ 5. 最长回文子串
  • ⭐ 1143. 最长公共子序列
  • △ 72. 编辑距离

技巧题(5)

  • ⭐ 136. 只出现一次的数字
  • ⭐ 169. 多数元素
  • 75. 颜色分类
  • 31. 下一个排列
  • 287. 寻找重复数

知识点解析

下面按分类讲解每类的核心思想、解题模板、复杂度、常见陷阱。吃透模板比刷题数量更重要。

1. 哈希表

核心思想:用 O(1) 查找换取时间,典型“空间换时间“。统计频次、判断存在、查找配对。

模板(两数之和):边遍历边查表,查 target - num 是否已出现。

fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = HashMap<Int, Int>()          // value -> index
    for (i in nums.indices) {
        val need = target - nums[i]
        if (map.containsKey(need)) return intArrayOf(map[need]!!, i)
        map[nums[i]] = i
    }
    return intArrayOf()
}
  • 49 字母异位词分组:排序后的字符串作 key,或用字符计数数组作 key。
  • 128 最长连续序列:用 HashSet,只从“序列起点“(num-1 不存在)开始向后扩展,保证 O(n)。
  • 复杂度:多为 O(n) 时间、O(n) 空间。
  • 陷阱:128 题必须从起点扩展,否则退化成 O(n²)。

2. 双指针

核心思想:用两个指针协同移动,避免暴力双层循环。常见三类:快慢指针、左右对撞、同向滑动。

模板(左右对撞 - 盛最多水):

fun maxArea(height: IntArray): Int {
    var l = 0; var r = height.size - 1; var ans = 0
    while (l < r) {
        ans = maxOf(ans, minOf(height[l], height[r]) * (r - l))
        if (height[l] < height[r]) l++ else r--   // 移动短板
    }
    return ans
}
  • 283 移动零:快慢指针,慢指针指向待填位置。
  • 15 三数之和:排序 + 固定一个数 + 双指针,注意去重(跳过重复值)。
  • 42 接雨水(△):左右指针 + 维护 leftMax/rightMax;也可用单调栈或 DP。
  • 陷阱:三数之和的去重是高频踩坑点;移动短板的贪心要想清楚为什么不移长板。

3. 滑动窗口

核心思想:双指针的进阶,维护一个 [left, right] 窗口,右扩入、左缩出,在 O(n) 内解决子串/子数组问题。

通用模板:

fun slidingWindow(s: String): Int {
    val window = HashMap<Char, Int>()
    var left = 0; var ans = 0
    for (right in s.indices) {
        window[s[right]] = (window[s[right]] ?: 0) + 1
        while (/* 窗口不满足条件 */ window[s[right]]!! > 1) {
            window[s[left]] = window[s[left]]!! - 1   // 左缩
            left++
        }
        ans = maxOf(ans, right - left + 1)             // 更新答案
    }
    return ans
}
  • 3 无重复最长子串:窗口内无重复字符。
  • 438 找异位词 / 76 最小覆盖子串(△):用计数 + need/valid 计数判断窗口达标。
  • 560 和为 K 的子数组:注意这题不是滑窗(有负数),要用前缀和 + 哈希表。
  • 239 滑动窗口最大值(△):用单调队列(双端队列),不是普通滑窗。
  • 陷阱:560 和 239 是“伪滑窗“,真正要用前缀和/单调队列,别套错模板。

4. 普通数组

核心思想:原地操作、前缀和、边界处理、贪心。看似基础,实则技巧密集。

  • 53 最大子数组和:经典 DP / Kadane —— dp[i] = max(num, dp[i-1]+num),维护全局最大。
fun maxSubArray(nums: IntArray): Int {
    var cur = nums[0]; var ans = nums[0]
    for (i in 1 until nums.size) {
        cur = maxOf(nums[i], cur + nums[i])
        ans = maxOf(ans, cur)
    }
    return ans
}
  • 56 合并区间:按起点排序,遍历合并重叠区间。
  • 189 轮转数组:三次反转法(整体反转 → 前 k 反转 → 后 n-k 反转),O(1) 空间。
  • 238 除自身以外乘积:前缀积 × 后缀积,不用除法。
  • 41 缺失第一个正数(△):原地哈希,把 num 放到 nums[num-1] 位置,O(1) 空间是难点。
  • 陷阱:41 题要求 O(1) 空间 + O(n) 时间,只能用原地置换;189 的三次反转要记牢。

5. 矩阵

核心思想:二维坐标变换、原地标记、利用有序性。考验空间想象力。

  • 73 矩阵置零:用首行首列做标记位,O(1) 额外空间(进阶);简单版用两个 set。
  • 54 螺旋矩阵:维护上下左右四个边界,按层收缩遍历。
  • 48 旋转图像:先转置(沿主对角线)再水平翻转,等价于顺时针 90°。
  • 240 搜索二维矩阵 II:从右上角开始,大则左移、小则下移,O(m+n)。
  • 陷阱:54 螺旋矩阵的边界判断和退出条件是 bug 高发区;48 旋转要记住“转置+翻转“组合。
// 48 旋转图像:转置 + 水平翻转
fun rotate(m: Array<IntArray>) {
    val n = m.size
    for (i in 0 until n) for (j in i + 1 until n) {
        val t = m[i][j]; m[i][j] = m[j][i]; m[j][i] = t   // 转置
    }
    for (row in m) row.reverse()                           // 每行翻转
}

6. 链表

核心思想:指针操作的细节功底。三大利器:虚拟头节点 dummy、快慢指针、递归。面试重中之重。

反转链表(母题,务必背熟):

fun reverseList(head: ListNode?): ListNode? {
    var prev: ListNode? = null
    var cur = head
    while (cur != null) {
        val next = cur.next
        cur.next = prev      // 反转指向
        prev = cur
        cur = next
    }
    return prev
}
  • dummy 头节点:删除/合并/插入时,在头前加哨兵节点,统一处理头节点边界(21、19、2、24、25)。
  • 快慢指针:141/142 判环(Floyd 龟兔,142 求入环点要推数学公式)、19 删倒数第 N 个(快指针先走 N 步)、找中点(148 排序、234 回文)。
  • 160 相交链表:双指针走到头切到对方链表,相遇即交点。
  • 138 随机链表复制:哈希表映射原节点→新节点,或原地交错复制。
  • 148 排序链表:归并排序(快慢找中点 + 合并),O(n log n)。
  • 23 合并 K 个(△):小顶堆 或 分治两两合并。
  • ⭐ 146 LRU 缓存:哈希表 + 双向链表——这题和你工作里的 LruCache 直接相关,面试高频,必须手写到熟。get/put 都要 O(1),双向链表维护访问顺序,哈希表定位节点。
  • 陷阱:142 入环点的数学推导;25 K 个一组翻转的边界;改指针时先存 next 防丢失。

7. 二叉树

核心思想:递归是灵魂。明确“以当前节点为根,左右子树要返回什么“,写好递归三要素(返回值、终止条件、单层逻辑)。

遍历模板:

// 递归中序
fun inorder(root: TreeNode?, res: MutableList<Int>) {
    if (root == null) return
    inorder(root.left, res)
    res.add(root.`val`)        // 中序:左-根-右
    inorder(root.right, res)
}
// 层序(BFS,用队列)
fun levelOrder(root: TreeNode?): List<List<Int>> {
    val res = mutableListOf<List<Int>>()
    val queue = ArrayDeque<TreeNode>()
    root?.let { queue.add(it) }
    while (queue.isNotEmpty()) {
        val level = mutableListOf<Int>()
        repeat(queue.size) {                  // 固定本层节点数
            val node = queue.removeFirst()
            level.add(node.`val`)
            node.left?.let { queue.add(it) }
            node.right?.let { queue.add(it) }
        }
        res.add(level)
    }
    return res
}
  • 递归类:104 深度、226 翻转、101 对称、543 直径、110 平衡——都是“后序+返回子树信息“。
  • BST 性质:98 验证(中序递增)、230 第 K 小(中序第 k 个)、108 有序数组转 BST(取中点为根)。
  • 构造/视图:102 层序、199 右视图(每层最后一个)、105 前序+中序建树、114 展开为链表。
  • 路径/祖先:236 最近公共祖先(LCA 递归)、437 路径总和 III(前缀和)、124 最大路径和(△,后序+全局更新)。
  • 陷阱:98 验证 BST 不能只比父子,要用上下界或中序;124/543 要区分“经过节点的路径“和“向上返回的贡献“。

8. 图论

核心思想:DFS/BFS 遍历 + 状态标记。网格类把矩阵当图,每个格子是节点。

  • 200 岛屿数量:遍历网格,遇到陆地 DFS/BFS 把整片淹掉(标记访问),计数。
  • 994 腐烂的橘子:多源 BFS,所有腐烂橘子同时入队,按层扩散记录分钟数。
  • 207 课程表:拓扑排序,建图 + 入度,BFS(Kahn)或 DFS 判环。能完成所有课 = 无环。
// 200 岛屿 DFS 淹没
fun dfs(grid: Array<CharArray>, i: Int, j: Int) {
    if (i !in grid.indices || j !in grid[0].indices || grid[i][j] != '1') return
    grid[i][j] = '0'                       // 标记已访问
    dfs(grid, i+1, j); dfs(grid, i-1, j)
    dfs(grid, i, j+1); dfs(grid, i, j-1)
}
  • 208 Trie 前缀树:每个节点 26 个子指针 + isEnd 标记,insert/search/startsWith。
  • 陷阱:207 必须判环(有环则无法完成);994 是多源 BFS 不是单源。

9. 回溯

核心思想:系统穷举解空间。模板 = 选择 → 递归 → 撤销选择。画出决策树就清晰了。

通用模板:

fun backtrack(path: MutableList<Int>, choices: ...) {
    if (/* 满足结束条件 */) { res.add(ArrayList(path)); return }
    for (choice in choices) {
        if (/* 剪枝:不合法跳过 */) continue
        path.add(choice)              // 做选择
        backtrack(path, ...)          // 进入下一层
        path.removeAt(path.size - 1)  // 撤销选择
    }
}
  • 排列 vs 组合:全排列(46)用 used 标记;子集(78)/组合(39)用 start 下标避免重复。
  • 39 组合总和:可重复选,递归传 i(不是 i+1);需排序剪枝。
  • 22 括号生成:左括号数 < n 可加左,右 < 左可加右。
  • 79 单词搜索 / 51 N皇后(△):网格/棋盘回溯 + 状态标记 + 回撤。
  • 131 分割回文串:每个切点判回文后递归。
  • 陷阱:结果要 ArrayList(path) 拷贝(否则引用同一个被清空);组合问题用 start 去重,排列用 used。

10. 二分查找

核心思想:有序(或部分有序)空间折半。难在边界:开闭区间、< vs <=、mid±1。坚持一种写法练到肌肉记忆。

模板(闭区间):

fun search(nums: IntArray, target: Int): Int {
    var lo = 0; var hi = nums.size - 1       // 闭区间 [lo, hi]
    while (lo <= hi) {
        val mid = lo + (hi - lo) / 2          // 防溢出
        when {
            nums[mid] == target -> return mid
            nums[mid] < target -> lo = mid + 1
            else -> hi = mid - 1
        }
    }
    return -1
}
  • 35 搜索插入位置:返回 lo 即插入点。
  • 34 查找首尾位置:两次二分找左边界、右边界。
  • 33/153 旋转数组:判断哪半有序,再决定收缩方向。
  • 74 搜索二维矩阵:展平成一维做二分。
  • 4 两正序数组中位数(△):二分切分,O(log(m+n)),Hot100 最难之一,可缓刷。
  • 陷阱:mid = lo + (hi-lo)/2 防溢出;旋转数组要先判断有序半区。

11. 栈

核心思想:LIFO 后进先出。匹配类、表达式类用普通栈;“找下一个更大/更小元素“用单调栈。

  • 20 有效括号:左括号入栈,右括号匹配栈顶。
  • 155 最小栈:辅助栈同步存当前最小值,getMin O(1)。
  • 394 字符串解码:双栈(数字栈 + 字符串栈)处理嵌套。
  • 739 每日温度:单调递减栈,存下标,出栈时算距离。
  • 84 柱状图最大矩形(△):单调递增栈,找每根柱子左右第一个更矮的。
// 739 每日温度:单调栈
fun dailyTemperatures(t: IntArray): IntArray {
    val res = IntArray(t.size)
    val stack = ArrayDeque<Int>()             // 存下标,栈内温度单调递减
    for (i in t.indices) {
        while (stack.isNotEmpty() && t[i] > t[stack.last()]) {
            val j = stack.removeLast()
            res[j] = i - j
        }
        stack.addLast(i)
    }
    return res
}
  • 陷阱:单调栈存下标还是值要想清楚;84 题常加哨兵简化边界。

12. 堆(优先队列)

核心思想:动态维护极值。Top K、数据流问题首选。Kotlin 用 PriorityQueue。

  • 215 第 K 大:小顶堆维护 K 个最大(堆顶是第 K 大);或快速选择 O(n) 平均。
  • 347 前 K 高频:哈希计数 + 小顶堆按频次,或桶排序 O(n)。
  • 295 数据流中位数(△):大顶堆(左半)+ 小顶堆(右半) 对顶,中位数从堆顶取。
// 215 小顶堆维护 K 个最大值
fun findKthLargest(nums: IntArray, k: Int): Int {
    val heap = java.util.PriorityQueue<Int>()    // 小顶堆
    for (n in nums) {
        heap.offer(n)
        if (heap.size > k) heap.poll()            // 弹出最小,留下 K 个最大
    }
    return heap.peek()
}
  • 陷阱:求第 K 大用小顶堆(反直觉),求第 K 小用大顶堆;295 双堆要维护大小平衡。

13. 贪心

核心思想:每步取局部最优,期望达到全局最优。关键是证明贪心成立(否则要用 DP)。

  • 121 买卖股票:遍历记录历史最低价,每天算“今天卖“的最大利润。
  • 55 跳跃游戏:维护能到达的最远下标,遍历中若当前位置超过最远则失败。
  • 45 跳跃游戏 II:贪心找每一步能跳到的最远范围,边界处步数+1。
  • 763 划分字母区间:记录每个字母最后出现位置,遍历扩展当前区间右界,到界则切分。
// 55 跳跃游戏
fun canJump(nums: IntArray): Boolean {
    var farthest = 0
    for (i in nums.indices) {
        if (i > farthest) return false        // 到不了 i
        farthest = maxOf(farthest, i + nums[i])
    }
    return true
}
  • 陷阱:贪心不是万能,要确认局部最优能推全局;55/45 的“最远可达“思路要分清。

14. 动态规划

核心思想:把大问题拆成重叠子问题,用 dp 数组存历史结果避免重算。五步:定义状态 → 状态转移方程 → 初始化 → 遍历顺序 → 返回值。DP 是面试天花板,务必吃透母题。

单维 DP

  • 70 爬楼梯:dp[i] = dp[i-1] + dp[i-2](斐波那契),DP 入门母题。
  • 198 打家劫舍:dp[i] = max(dp[i-1], dp[i-2] + nums[i])(偷或不偷)。
  • 322 零钱兑换:完全背包,dp[amount] = min(dp[amount - coin] + 1)。
  • 300 最长递增子序列:dp[i] = 以 i 结尾的 LIS,O(n²);进阶贪心+二分 O(n log n)。
  • 139 单词拆分:dp[i] = 前 i 个字符能否拆分。
  • 152 乘积最大子数组:同时维护最大、最小(负负得正)。
  • 416 分割等和子集:01 背包,目标 sum/2。
  • 32 最长有效括号(△):dp[i] = 以 i 结尾的最长有效长度,转移较绕。
// 322 零钱兑换(完全背包)
fun coinChange(coins: IntArray, amount: Int): Int {
    val dp = IntArray(amount + 1) { amount + 1 }   // 初始化为不可达
    dp[0] = 0
    for (i in 1..amount)
        for (c in coins)
            if (c <= i) dp[i] = minOf(dp[i], dp[i - c] + 1)
    return if (dp[amount] > amount) -1 else dp[amount]
}

多维 DP

  • 62 不同路径:dp[i][j] = dp[i-1][j] + dp[i][j-1](网格路径母题)。
  • 64 最小路径和:同上取 min + 当前值。
  • 5 最长回文子串:区间 DP,dp[i][j] = s[i..j] 是否回文;或中心扩展。
  • 1143 最长公共子序列(LCS):dp[i][j],相等 +1,否则取两侧 max——序列型 DP 母题。
  • 72 编辑距离(△):dp[i][j] = word1 前 i 转 word2 前 j 的最少操作(增删改三选一取 min)。
// 1143 LCS:序列型 DP 母题
fun longestCommonSubsequence(a: String, b: String): Int {
    val dp = Array(a.length + 1) { IntArray(b.length + 1) }
    for (i in 1..a.length) for (j in 1..b.length) {
        dp[i][j] = if (a[i-1] == b[j-1]) dp[i-1][j-1] + 1
                   else maxOf(dp[i-1][j], dp[i][j-1])
    }
    return dp[a.length][b.length]
}
  • 陷阱:dp 数组大小常为 n+1(含空状态);初始化和遍历顺序错是主要 bug;先吃透 LCS、01背包、完全背包三个母题,其余是变体。

15. 技巧题

核心思想:发现问题的特殊性质,用位运算、数学、特定结构巧解。考察活用能力。

  • 136 只出现一次的数字:异或,相同抵消,剩下的就是答案,O(1) 空间。
  • 169 多数元素:摩尔投票,众数计数抵消法,O(1) 空间。
  • 75 颜色分类:荷兰国旗,三指针(0/1/2)一次遍历原地排序。
  • 31 下一个排列:从右找第一个升序对,交换 + 反转后缀。
  • 287 寻找重复数:把数组看成链表,快慢指针找环(Floyd),不修改数组、O(1) 空间。
// 136 只出现一次:异或
fun singleNumber(nums: IntArray): Int {
    var x = 0
    for (n in nums) x = x xor n      // a^a=0, a^0=a
    return x
}
  • 陷阱:这类题“知道就秒、不知道想破头“,务必记住每题的 trick(异或、摩尔投票、Floyd 判环)。

刷题策略总结

高频母题(背到能默写)

反转链表、二叉树三种遍历 + 层序、二分模板、回溯模板、滑动窗口模板、01背包/完全背包/LCS。这 7 类模板覆盖了 Hot 100 的 70%。

针对中级 Android 的优先级

  1. 第一梯队(必刷,中小厂够用):本文 ⭐ 标记的 ~40 题。尤其 146 LRU(和 LruCache 直接相关,Android 超高频)、链表全套、二叉树遍历、岛屿数量、爬楼梯/打家劫舍/零钱兑换、买卖股票、20 有效括号。
  2. 第二梯队(冲大厂):其余中等题。
  3. 第三梯队(△ 困难,选刷):42 接雨水、4 中位数、23 合并K个、25 K个一组、84 柱状图、124 最大路径和、51 N皇后、72 编辑距离。时间不够可跳过,面到再说。

方法论

  • 分类刷,不要顺序刷:一次攻一个专题,内化模板。
  • 二刷三刷:第一遍看题解理解,第二遍独立写,第三遍默写模板。
  • 手写 + 口述复杂度:面试要边写边讲思路和时间/空间复杂度。
  • 限时:中等题目标 20-30 分钟内 AC。
  • 错题本:记录卡壳点和 trick,面试前快速过。