视频题解合集
liweiwei1419 ... 2021-12-19 About 11 min
我从 2019 年 9 月开始录制视频题解。最开始的时候，我会对着要讲的材料录好几遍。现在讲解知识点的时候写逐字稿。已经沉淀了很多视频，其实也算是一个小小的体系课程，现在罗列在这里，希望能够对大家有所帮助。
# 自我介绍
说明：上传日期：2022 年 3 月 23 日（星期三）。
# 0. 算法新手如何刷力扣（LeetCode）？【干货分享】
# 1. 时间复杂度与空间复杂度
这个视频提到了时间复杂度是一个渐进概念，需要用动态的角度去理解。并且讲解了时间复杂度的严格定义（极限形式），以便大家理解时间复杂度的计算规则。并且还指出了：时间复杂度不是程序的运行时间；应该使用「空间换时间」，更多关注在优化「时间复杂度」。
# 2. 二分查找
这个视频介绍了如何写对二分查找算法，二分查找的细节虽然多，但只要我们掌握了正确的解题思路，并且多加练习、勤于思考、多做总结，写对二分查找的问题就不再困难。
下面的视频讲解了几道二分查找的例题，我们重点分析了题意和如何利用题目中给出的条件逐渐缩小搜索区间。
我们通过「力扣」第 4 题（寻找两个正序数组的中位数）的分析，向大家介绍了这样的技巧：如果要找的目标元素的性质比较复杂，可以对这条性质取反，进而写出可以简单的可以缩减问题区间的逻辑语句。
# 3. 和排序相关的问题
- B 站：《算法不好玩》专题二：基础排序算法 (opens new window)
- B 站：《算法不好玩》专题三：循环不变量 (opens new window)
- B 站：《算法不好玩》专题四：归并排序 (opens new window)
「归并排序」和「快速排序」是非常重要的排序算法，深刻理解它们对于理解「递归」函数的运行机制有着非常大的帮助，同时它们也是「分治思想」的典型应用。「逆序对」和「荷兰国旗问题（颜色分类）」也是非常经典的算法问题。
| 题目链接 | 力扣 | B 站 |
|---|---|---|
| 《剑指 Offer》 51. 数组中的逆序对（困难） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
| 315. 计算右侧小于当前元素的个数（困难） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
计算「逆序对」完全就是按照「归并排序」的思路而来。
| 题目链接 | 力扣 | B 站 |
|---|---|---|
| 75. 颜色分类（中等） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
在「颜色分类」问题的讲解中，我们向大家介绍了「循环不变量」，在编写代码的过程中，我们应该一直遵守所使用的变量的语义，在「程序执行前」「执行过程中」「执行结束」以后保持不变。遵守我们自己定义「循环不变量」是我们写对正确代码的重要方法。
| 题目链接 | 力扣 | B 站 |
|---|---|---|
| 41. 缺失的第一个正数（困难） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
「缺失的第一个正数」是一个经典的算法问题，用到的思想是「原地哈希」，可以理解为是「桶排序」算法的特殊应用：一个萝卜一个坑，一个桶里只存放一个元素。要和大家强调的是，可以这样做是和输入数组的元素的数值密切相关。
# 4. 滑动窗口
「滑动窗口」问题是典型的应用「循环不变量」解决的问题，比较考验我们编码和调试的能力。
# 5. 栈相关的问题
使用「栈」解决的问题，需要我们通过具体例子，发现解决它们正好符合「后进先出」的规律：
- 把暂时还不能确定结果的数据放入栈，把可以确定结果的数据从栈中拿出；
- 很多数据结构恰好应用于这种「动态」处理问题的场景，而发挥出它们的应用价值。
掌握下面这两个问题，离不开对具体例子的研究，进而归纳出一般规律。
| 题目链接 | 力扣 | B 站 |
|---|---|---|
| 84. 柱状图中最大的矩形（困难） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
| 316. 去除重复字母（中等） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
「栈」最为广泛的一种应用就是作为「递归」「深度优先遍历」「分治算法」的数据结构支持。
# 6. 并查集
「并查集」这个数据结构目前来说在面试中出现比较少，如果是准备算法面试的朋友，可以跳过。
# 7. 树
树的问题很多都可以使用「深度优先遍历」或者「广度优先遍历」去做。
| 题目链接 | 力扣 | B 站 |
|---|---|---|
| 105. 从前序与中序遍历序列构造二叉树（中等） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
# 8. 回溯算法
「回溯算法」其实就是对题目中所蕴含的「树形结构」执行一次 深度优先遍历。做这一类问题，在草稿纸上画出树形结构图很重要。
# 9. 动态规划
# 10. 广度优先遍历与拓扑排序
| 题目链接 | 力扣 | B 站 |
|---|---|---|
| 127. 单词接龙（困难） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
| 1203. 项目管理（困难） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
# 11. 哈希表
| 题目链接 | 力扣 | B 站 |
|---|---|---|
| 1. 两数之和（简单） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
| 面试题 10.02. 变位词组（同「力扣」第 49 题：变位词组） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |
# 12. 位运算相关
| 题目链接 | 力扣 | B 站 |
|---|---|---|
| 1128. 等价多米诺骨牌对的数量（简单） (opens new window) | 力扣 (opens new window) | B 站 (opens new window) |