算法方法总结
算法方法总结
一些基本概念
子集合和子序列的区别是：
- 集合中的元素顺序可以是任意的
- 但是序列的元素是有顺序的，而且子序列中的元素的顺序必须跟元素在原集合的顺序相同。
- 子数组，必须是原数组中连续的一段，
算法复杂度的重要性
算法复杂度，看起来并不重要，但是实际上，却非常重要，因为我们在思考一个问题的时候，往往脑子里会冒出很多个思路，但是这些思路中应该采取哪一个继续思考下去，我们是不知道的，那么算法的时间复杂度和空间复杂度就是一个判断的标准，我们只需要简单推断一下算法复杂度，就可以快速分辨出哪些思路效率更高，然后继续深入确定细节。
这一点我在 KM-103. 水流问题 中，印象非常深刻。
关于算法的复杂度 复杂度
题型
- 二分法，代表题型，704. 二分查找
- 双指针法，代表题型，27. 移除元素
- 移动窗口，代表题型，209. 长度最小的子数组
- 固定间隔距离的双指针，19. 删除链表的倒数第 N 个结点
- 差速双指针，142. 环形链表 II
- for 循环遍历指针 + 首尾相向指针，15. 三数之和、18. 四数之和 - 待复习
- 首位相向指针， 344. 反转字符串
- 直接模拟，59. 螺旋矩阵 II
- 虚拟头节点，203. 移除链表元素
- 内置链表长度变量，707. 设计链表
- 递归，206. 反转链表
- 哈希：当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
- 一个字符的 ASCII 码当作下标作为哈希函数进行映射：242. 有效的字母异位词、76. 最小覆盖子串
- 如何将问题变成判断一个元素是否存在于集合中：1. 两数之和
- KMP（前缀表快速有效地回退匹配）：28. 找出字符串中第一个匹配项的下标
- 栈与队列
- 栈：对称匹配类的题目 20. 有效的括号
- 队列：单调队列： 239. 滑动窗口最大值 Top-K：347. 前 K 个高频元素
- 二叉树：二叉树天生适合递归，在练习二叉树相关的题目的时候，也练习了递归的写法
- 遍历二叉树，
- 前中后序遍历（深度优先遍历）：144. 二叉树的前序遍历、94. 二叉树的中序遍历、145. 二叉树的后序遍历
- 层序遍历（广度优先遍历）：102. 二叉树的层序遍历，有很多题都是以这道题为模板进行解答。其中我觉得最容易出错的，就是 104. 二叉树的最大深度 和 111. 二叉树的最小深度
- 有的时候需要回溯，257. 二叉树的所有路径、112. 路径总和
- 通过中序遍历和前序或者后序遍历恢复整个二叉树
- 遇到在二叉搜索树上求什么最值，求差值之类的，都要思考一下二叉搜索树可是有序的，要利用好这一特点。二叉搜索树 + 中序遍历 = 递增序列
- 最近公共祖先怎么求，236. 二叉树的最近公共祖先、235. 二叉搜索树的最近公共祖先，以及利用这种思路去修建二叉搜索树 669. 修剪二叉搜索树
- 确定一个二叉树，其实第一步就是确定这个二叉树的根节点 96. 不同的二叉搜索树
- 树形动态规划：隔一个节点偷一个节点的值，能偷到的最大值：337. 打家劫舍 III
- 遍历二叉树，
- 回溯
- 组合问题
- 从 n 个数里取出 k 个数的所有组合方式：77. 组合，要求组合的元素的总和大于固定值 216. 组合总和 III
- 从不同的集合中取出数据进行组合 17. 电话号码的字母组合
- 组合中元素可无限重复，取出元素之后不放回，39. 组合总和，下一次递归调用的起点依然从自己开始
- 集合中的元素可重复，但是结果中的不能出现两个一样的组合，40. 组合总和 II 通过记录遍历过的元素区分树枝重复还是树层重复，并在树层重复的时候去重。
- 在求和问题中，排序之后加剪枝是常见的套路！
- 分隔问题
- 131. 分割回文串，其实本质上还是组合，只不过是把取某一个范围内的某一个元素，变成了取这个范围的起点到当前元素的这段子字符串。
- 93. 复原 IP 地址，在遍历所有分隔可能的基础上限制每一个 ip 段。
- 子集/子序列问题
- 78. 子集，这道题非常重要，让我们更加深刻地理解 77. 组合 的那段模板代码，可以说上面的所有解法都是 77. 组合 的变体。
- 90. 子集 II 其实就是 78. 子集 叠加 40. 组合总和 II
- 491. 非递减子序列 子序列其实还是子集，只不过不能对原数组排序，因为子序列中的元素的顺序必须跟元素在原集合的顺序相同。所以没法直接套用 40. 组合总和 II，但是方式还是一样的，就是进行树层去重。直接用 Set 记录然后去重即可。
- 排列
- 46. 全排列 每一次都从集合的第一个元素开始遍历，但是跳过已经选择过的元素（已经选择过的元素用 used 数组记录）
- 47. 全排列 II 去掉重复元素，解法实际上就是 46. 全排列 叠加 40. 组合总和 II ，直接复用 used 数组即可。
- 棋盘回溯（二维回溯）：
- 组合问题
- 贪心
- 求数组的元素之间的最大值，递增区间之类的。
- 从头累加小于 0，则从下一个元素开始累加
- 遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。这个思路真的很赞。
- 135. 分发糖果
- 406. 根据身高重建队列 这个例子告诉我们，对于屏藩在列表中间插入的场景，用 LinkedList 是最合适的，对于频繁在末尾添加元素的场景，LinkedList 也是最合适的，只要不是需要根据索引访问元素，LinkedList 都是最合适的。
- 738. 单调递增的数字
- 区间题
- 求数组的元素之间的最大值，递增区间之类的。
- 动态规划
- 斐波那契数列：509. 斐波那契数
- 直接根据要求的数字的定义来定义 dp 数组，然后确定状态转移方程
- 背包问题
- 01 背包问题，（外层 for 循环遍历物品，内层 for 循环遍历背包大小，而且从背包最大值遍历到物品 i 的大小）以及其变种问题：
- 背包的模板，要记下来 背包问题-01背包
- 1049. 最后一块石头的重量 II
- 416. 分割等和子集
- 494. 目标和
- 二维 01 背包：474. 一和零，求物品个数
- 完全背包（外层 for 循环遍历物品，内层 for 循环遍历背包大小，而且从物品 i 的大小背包遍历到最大值）
- 完全背包模板 背包问题-完全背包
- 518. 零钱兑换 II：求组和数，先遍历物品，再遍历背包大小，而且从物品 i 的大小背包遍历到最大值。
- 377. 组合总和 Ⅳ，求排列数，先遍历背包大小（背包从 0 到最大值），再遍历物品，只有在背包容量大于等于物品 i 的大小时才执行状态转移方程。
- 背包问题-爬楼梯进阶版，完全背包 + 塞满背包的物品的排列数的广泛应用，天才般的思路。这也打开了我们的思路。我们可以以背包问题来类比很多其他问题，套模板，然后快速解题。这个题让我感觉完全背包的用处比 01 背包的还要大。
- 322. 零钱兑换，完全背包，刚好塞满背包求物品个数。
- 279. 完全平方数 ，跟 322. 零钱兑换 一模一样，完全背包，刚好塞满背包求物品个数。
- 139. 单词拆分 完全背包，求排列
- 背包问题-多重背包：把物品按照数量展开，就是 背包问题-01背包
- 为什么我们在 背包问题-01背包 中可以不在乎内外层 for 循环的顺序呢？因为他们求的是放物品与不放物品的结果的最大值或者最小值。但是 377. 组合总和 Ⅳ 和 518. 零钱兑换 II 中求的是组合总数或者排列总数，求的是放物品 i 和不放物品 i 的结果的累加值。只要是累加，就会很在乎循环的顺序。
- 背包问题总结，可以刷模板，其实没有那么难，掌握模板往里套即可。
- 01 背包问题，（外层 for 循环遍历物品，内层 for 循环遍历背包大小，而且从背包最大值遍历到物品 i 的大小）以及其变种问题：
- 打家劫舍
- 直接根据问题定义 dp：198. 打家劫舍
- 分只包含首节点和只包含尾节点分开分析，并取两个结果的最大值：213. 打家劫舍 II
- 树形 dp：337. 打家劫舍 III
- 买卖股票
- 模板：122. 买卖股票的最佳时机 II
- 只能交易固定的次数
- 不固定买卖次数，而是在交易过程中进行变种
- 子序列
- 编辑距离
- 单调栈
- 图
- dfs bfs
- KM-98. 所有可达路径
- 797. 所有可能的路径
- 岛屿问题
- KM-99. 岛屿数量
- KM-100. 岛屿的最大面积
- 孤岛问题：从地图的边缘开始遍历即可
- dfs bfs