《算法训练营》课堂笔记 & 习题

第01课丨数据结构与算法总览

参考链接

• 数据结构脑图
• 算法脑图

课后作业

绘制自己的数据结构和算法脑图

用脑图的方式把知识的脉络串联起来，不管对于学习新知识还是巩固已有知识，都是一种很好的学习方式。同学们可以将目前自己所掌握的数据结构和算法知识绘制成脑图，在绘制过程中可以查阅资料，补充目前掌握欠缺的部分，找到自己薄弱的地方。后面再通过课程的学习和刻意练习，动态地将自己绘制的脑图逐步补充、完善，从而达到真正的融会贯通。

脑图绘制工具不限，同学们需要按时将作业提交到班级 GitHub 中，具体作业提交方式戳此查看。

第02课丨训练准备和复杂度分析

参考链接

• Windows Microsoft New Terminal
• VS Code Themes
• 教你打造一款颜值逆天的 VS Code
• 炫酷的 VS Code 毛玻璃效果
• 自顶向下的编程方式
• 自顶向下编程的 LeetCode 例题

参考链接

• 如何理解算法时间复杂度的表示法
• Master theorem
• 主定理

第03课丨数组、链表、跳表

参考链接

• Java 源码分析（ArrayList）
• Linked List 的标准实现代码
• Linked List 示例代码
• Java 源码分析（LinkedList）
• LRU Cache - Linked list： LRU 缓存机制
• Redis - Skip List：跳跃表、为啥 Redis 使用跳表（Skip List）而不是使用 Red-Black？

Array 实战题目

• 1. 两数之和
• 11. 盛最多水的容器
• 15. 三数之和 (高频老题）
• 70. 爬楼梯
• 283. 移动零

Linked List 实战题目

• 24. 两两交换链表中的节点
• 25. K 个一组翻转链表
• 141. 环形链表
• 142. 环形链表 II
• 206. 反转链表

课后作业

• 1. 两数之和
• 21. 合并两个有序链表
• 26. 删除排序数组中的重复项
• 66. 加一
• 88. 合并两个有序数组
• 189. 旋转数组
• 283. 移动零

第04课丨栈、队列、优先队列、双端队列

参考链接

• Java 的 PriorityQueue 文档
• Java 的 Stack 源码
• Java 的 Queue 源码
• Python 的 heapq
• 高性能的 container 库

预习题目

• 20. 有效的括号
• 155. 最小栈

实战题目

• 84. 柱状图中最大的矩形
• 239. 滑动窗口最大值

课后作业

• 用 add first 或 add last 这套新的 API 改写 Deque 的代码
• 分析 Queue 和 Priority Queue 的源码
• 42. 接雨水
• 641. 设计循环双端队列

说明：改写代码和分析源码这两项作业，同学们需要在第 1 周的学习总结中完成。如果不熟悉 Java 语言，这两项作业可选做。

第05课丨哈希表、映射、集合

参考链接

• Java Set 文档
• Java Map 文档

课后作业

写一个关于 HashMap 的小总结。
说明：对于不熟悉 Java 语言的同学，此项作业可选做。

实战题目 / 课后作业

• 1. 两数之和
• 49. 字母异位词分组
• 242. 有效的字母异位词

参考链接

• 养成收藏精选代码的习惯（示例）

第06课丨树、二叉树、二叉搜索树

参考链接

• 二叉搜索树 Demo

思考题

树的面试题解法一般都是递归，为什么？
说明：同学们可以将自己的思考写在课程下方的留言区一起讨论，也可以写在第 2 周的学习总结中。

参考链接

• 树的遍历 Demo

实战题目 / 课后作业

• 94. 二叉树的中序遍历
• 144. 二叉树的前序遍历
• 429. N叉树的层序遍历
• 589. N叉树的前序遍历
• 590. N叉树的后序遍历

第07课丨泛型递归、树的递归

参考链接

• 递归代码模板

实战题目

• 22. 括号生成
• 70. 爬楼梯
• 98. 验证二叉搜索树
• 104. 二叉树的最大深度
• 111. 二叉树的最小深度
• 226. 翻转二叉树
• 297. 二叉树的序列化与反序列化

每日一课

• 如何优雅地计算斐波那契数列

课后作业

• 46. 全排列
• 47. 全排列 II
• 77. 组合
• 105. 从前序与中序遍历序列构造二叉树
• 236. 二叉树的最近公共祖先

第08课丨分治、回溯

参考链接

• 分治代码模板
• 括号生成问题

预习题目

• 50. Pow(x, n)
• 78. 子集

参考链接

• 牛顿迭代法原理
• 牛顿迭代法代码

实战题目

• 17. 电话号码的字母组合
• 51. N皇后
• 169. 多数元素 （简单、但是高频）

第09课丨深度优先搜索和广度优先搜索

参考链接

• DFS 代码模板（递归写法、非递归写法）
• BFS 代码模板

实战题目

• 22. 括号生成
• 102. 二叉树的层序遍历
• 433. 最小基因变化
• 515. 在每个树行中找最大值

课后作业

• 126. 单词接龙 II
• 127. 单词接龙
• 200. 岛屿数量
• 529. 扫雷游戏

第10课丨贪心算法

参考链接

• coin change 题目
• 动态规划定义

课后作业

• 45. 跳跃游戏 II
• 55. 跳跃游戏
• 122. 买卖股票的最佳时机 II
• 455. 分发饼干
• 874. 模拟行走机器人
• 860. 柠檬水找零

第11课丨二分查找

参考链接

• 二分查找代码模板
• Fast InvSqrt() 扩展阅读

实战题目

• 69. x 的平方根
• 367. 有效的完全平方数

课后作业

• 33. 搜索旋转排序数组
• 74. 搜索二维矩阵
• 153. 寻找旋转排序数组中的最小值

使用二分查找，寻找一个半有序数组 [4, 5, 6, 7, 0, 1, 2] 中间无序的地方
说明：同学们可以将自己的思路、代码写在第 3 周的学习总结中

第12课丨动态规划

参考链接

• 递归代码模板
• 分治代码模板
• 动态规划定义

参考链接

• 不同路径题目
• 不同路径 2 题目
• 最长公共子序列题目
• MIT 动态规划课程最短路径算法

实战题目

• 53. 最大子序和
• 70. 爬楼梯
• 120. 三角形最小路径和
• 120. 三角形最小路径和
• 152. 乘积最大子数组
• 322. 零钱兑换

实战题目

• 121. 买卖股票的最佳时机
• 121. 买卖股票的最佳时机
• 122. 买卖股票的最佳时机 II
• 123. 买卖股票的最佳时机 III
• 188. 买卖股票的最佳时机 IV
• 198. 打家劫舍
• 213. 打家劫舍 II
• 309. 最佳买卖股票时机含冷冻期
• 714. 买卖股票的最佳时机含手续费

高级 DP 实战题目

• 45. 跳跃游戏 II
• 55. 跳跃游戏
• 62. 不同路径
• 63. 不同路径 II
• 72. 编辑距离 （重点）
• 279. 完全平方数
• 322. 零钱兑换
• 518. 零钱兑换 II
• 980. 不同路径 III

注意：请大家先消化前面的实战题目，高级 DP 的方法和题解会在课程后面解锁。

课后作业

• 32. 最长有效括号
• 64. 最小路径和
• 72. 编辑距离
• 76. 最小覆盖子串Copy
• 91. 解码方法
• 221. 最大正方形
• 312. 戳气球
• 363. 矩形区域不超过 K 的最大数值和
• 403. 青蛙过河
• 410. 分割数组的最大值
• 552. 学生出勤记录 II
• 621. 任务调度器
• 647. 回文子串

第13课丨字典树和并查集

参考链接

• 二叉树的层次遍历
• 实现 Trie
• Tire 树代码模板

实战题目 / 课后作业

• 208. 实现 Trie (前缀树)
• 212. 单词搜索 II

分析单词搜索 2 用 Tire 树方式实现的时间复杂度，请同学们提交在第 6 周的学习总结中。

参考链接

• 岛屿数量
• 并查集代码模板

实战题目 / 课后作业

• 130. 被围绕的区域
• 200. 岛屿数量
• 547. 朋友圈

第14课丨高级搜索

参考链接

• DFS 代码模板
• BFS 代码模板
• AlphaZero Explained
• 棋类复杂度

实战题目

• 22. 括号生成
• 36. 有效的数独
• 37. 解数独
• 51. N皇后
• 70. 爬楼梯

实战题目

• 127. 单词接龙
• 433. 最小基因变化

课后作业

总结双向 BFS 代码模版，请同学们提交在第 6 周学习总结中。

参考链接

• A* 代码模板
• 相似度测量方法
• 二进制矩阵中的最短路径的 A* 解法
• 8 puzzles 解法比较

实战题目

• 37. 解数独
• 773. 滑动谜题
• 1091. 二进制矩阵中的最短路径

第15课丨红黑树和AVL树

参考链接

• 平衡树

第16课丨位运算

参考链接

• 如何从十进制转换为二进制

参考链接

• N 皇后位运算代码示例

实战题目 / 课后作业

• 51. N皇后
• 52. N皇后 II
• 190. 颠倒二进制位
• 191. 位1的个数
• 231. 2的幂
• 338. 比特位计数

第17课丨布隆过滤器和LRU缓存

参考链接

• 布隆过滤器的原理和实现
• 使用布隆过滤器解决缓存击穿、垃圾邮件识别、集合判重
• 布隆过滤器 Python 代码示例
• 布隆过滤器 Python 实现示例
• 高性能布隆过滤器 Python 实现示例
• 布隆过滤器 Java 实现示例 1
• 布隆过滤器 Java 实现示例 2

参考链接

• Understanding the Meltdown exploit
• 替换算法总揽
• LRU Cache Python 代码示例

实战题目 / 课后作业

• 146. LRU缓存机制

第18课丨排序算法

参考链接

• 十大经典排序算法
• 快速排序代码示例
• 归并排序代码示例
• 堆排序代码示例
• 直播课回顾: https://pan.baidu.com/s/1sFuZ8GjDCXy5mPCNLZhHxw 提取码: 2rdy

课后作业

用自己熟悉的编程语言，手写各种初级排序代码，提交到第 7 周学习总结中。

参考链接

• 十大经典排序算法
• 9 种经典排序算法可视化动画
• 6 分钟看完 15 种排序算法动画展示

实战题目 / 课后作业

• 56. 合并区间
• 242. 有效的字母异位词
• 493. 翻转对
• 1122. 数组的相对排序
• https://leetcode-cn.com/problems/design-a-leaderboard/

第19课丨高级动态规划

参考链接

• 爬楼梯
• 不同路径
• 打家劫舍
• 最小路径和
• 股票买卖

课后作业

在第 8 周学习总结中，写出不同路径 2 这道题目的状态转移方程。

参考链接

• 爬楼梯
• 使用最小花费爬楼梯
• 编辑距离

课后作业

• 32. 最长有效括号
• 85. 最大矩形
• 91. 解码方法
• 115. 不同的子序列
• 300. 最长上升子序列
• 818. 赛车

第20课丨字符串算法

参考链接

• 不可变字符串
• Atoi 代码示例

字符串基础问题

• 8. 字符串转换整数 (atoi)
• 58. 最后一个单词的长度
• 387. 字符串中的第一个唯一字符
• 709. 转换成小写字母
• 771. 宝石与石头
• 789. 在 Python 中将字符串转换为浮点数

字符串操作问题

• 14. 最长公共前缀
• 151. 翻转字符串里的单词
• 344. 反转字符串
• 541. 反转字符串 II
• 557. 反转字符串中的单词 III
• 917. 仅仅反转字母

异位词问题

• 49. 字母异位词分组
• 242. 有效的字母异位词
• 438. 找到字符串中所有字母异位词

回文串问题

• 5. 最长回文子串
• 125. 验证回文串
• 680. 验证回文字符串 Ⅱ

最长子串、子序列问题

• 5. 最长回文子串
• 72. 编辑距离
• 1143. 最长公共子序列

字符串 + DP 问题

• 10. 正则表达式匹配
• 10. 正则表达式匹配
• 44. 通配符匹配
• 115. 不同的子序列

参考链接

• Boyer-Moore 算法
• Sunday 算法
• 字符串匹配暴力法代码示例
• Rabin-Karp 代码示例
• KMP 字符串匹配算法视频
• 字符串匹配的 KMP 算法

课后作业

• 5. 最长回文子串
• 8. 字符串转换整数 (atoi)
• 32. 最长有效括号
• 44. 通配符匹配
• 115. 不同的子序列
• 151. 翻转字符串里的单词
• 205. 同构字符串
• 387. 字符串中的第一个唯一字符
• 438. 找到字符串中所有字母异位词
• 541. 反转字符串 II
• 557. 反转字符串中的单词 III
• 680. 验证回文字符串 Ⅱ
• 917. 仅仅反转字母