算法方法总结
算法方法总结
- 二分法，代表题型，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. 修剪二叉搜索树
- 遍历二叉树，
- 回溯
- 组合问题
- 从 n 个数里取出 k 个数的所有组合方式：77. 组合，要求组合的元素的总和大于固定值 216. 组合总和 III
- 从不同的集合中取出数据进行组合 17. 电话号码的字母组合
- 组合中元素可无限重复，取出元素之后不放回，39. 组合总和，下一次递归调用的起点依然从自己开始
- 集合中的元素可重复，但是结果中的不能出现两个一样的组合，40. 组合总和 II 通过记录遍历过的元素区分树枝重复还是树层重复
- 在求和问题中，排序之后加剪枝是常见的套路！
- 分隔问题
- 131. 分割回文串，其实本质上还是组合，只不过是把取某一个范围内的某一个元素，变成了取这个范围的起点到当前元素的这段子字符串。
- 93. 复原 IP 地址，在遍历所有分隔可能的基础上限制每一个 ip 段。
- 子集/子序列问题
- 78. 子集，这道题非常重要，让我们更加深刻地理解 77. 组合 的那段模板代码，可以说上面的所有解法都是 77. 组合 的变体。
- 90. 子集 II 其实就是 78. 子集 叠加 40. 组合总和 II
- 491. 非递减子序列 子序列其实还是子集，只不过不能对原数组排序，因为子序列中的元素的顺序必须跟元素在原集合的顺序相同。所以没法直接套用 40. 组合总和 II，但是方式还是一样的，就是进行树层去重。
- 排列
- 46. 全排列
- 47. 全排列 II 去掉重复元素，解法实际上就是 46. 全排列 叠加 40. 组合总和 II ，直接复用 used 数组即可。
- 组合问题