双指针：快慢指针，头尾指针
- 合并两个有序数组(双指针)
- 移除元素(双指针)
- 删除有序数组中的重复项(双指针)
- 删除有序数组中的重复项 II(双指针)
- 多数元素(哈希表、排序法、投票法、分治法)
- 轮转数组(环状替换、数组翻转)
- 买卖股票的最佳时机(一次遍历*)
- 买卖股票的最佳时机II(一次遍历, 动态规划*， 正数相加*)
- 跳跃游戏(动态规划*，贪心)
- h指数(排序)
- O(1)时间插入、删除和获取随机变量(变长数组+哈希表)
- 除自身以外数组的乘积(动态规划*左右累乘)
- 加油站(一次遍历)
- 分发糖果(一次遍历*分阶段计算、二次遍历**)
- 接雨水(二次遍历*)
- 二分查找
- 有序数组的平方
- 长度最小的子数组(滑动窗口)
- 螺旋矩阵(循环不变量*)
- 替换空格
- 反转字符串中的单词(分步写函数：去除空格、整体反转、单词反转、反转函数用双指针)
- 左旋转字符串(反转再反转)
- 实现 strStr()(***KMP算法)
哈希表的类型：数组、set、map
栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中是不是连续分布。
缺省情况下，默认底层容器是deque，那么deque的在内存中的数据分布是什么样的呢？ 答案是：不连续的，下文也会提到deque。
经典例题：括号匹配问题、栈在系统中的应用、滑动窗口最大值、前k个最值、字符串去重问题
链表的类型: 单链表、双链表、循环链表
链表的操作：增删改查
题目跟一层有关的均可用层次遍历(例：层里最大值，层里平均值，右视图，左视图)
二叉搜索树的中序遍历是有序的
- 二叉树的递归遍历
- 二叉树的迭代遍历(*用栈来存放树结点)
- 二叉树的层次遍历(队列)
- 翻转二叉树(递归法、迭代法)
- 对称二叉树
- 二叉树的最大深度
- 二叉树的最小深度
- 完全二叉树的节点个数(递归+完全二叉树的性质)
- 二叉树的所有路径
- 左叶子之和
- 找树左下角的值
- 从中序与后序遍历序列构造二叉树(*递归)
- 最大二叉树
- 合并二叉树
- 二叉搜索树的搜索
- 验证二叉搜索树(中序遍历)
- 二叉搜索树的最小绝对差(中序遍历)
- 二叉搜索树中的众数
- 二叉树的最近公共祖先
- 二叉搜索树的最近公共祖先*
- 二叉搜索树中的插入操作*
- 删除二叉搜索树中的节点*
- 修剪二叉搜索树*
- 将有序数组转换为二叉搜索树
- 把二叉搜索树转换为累加树(*反中序遍历)
排列和组合，所有需要暴力枚举的题目都可想到回溯，回溯无非就是暴力枚举+剪枝
- 组合(递归枚举)
- 组合总和 III
- 电话号码的字母组合
- 组合总和
- 组合总和 II
- 分割回文串
- 复原IP地址**
- 子集
- 子集II(*排序+剪枝)
- 递增子序列
- 全排列
- 全排列II(*排序+剪枝)
- 重新安排行程(***需要用到unordered_map和map，直接遍历map的key，大大的缩减了时间)
- N皇后
- 解数独(***遍历+递归，不用占有太多的内存)
贪心的题目如果不要求顺序，先排序可能更好做
一次遍历，二次遍历
- 分发饼干(*排序 + 双指针 + 贪心)
- 摆动序列
- 最大子数组和(贪心、动态规划)
- 买卖股票的最佳时机 II
- 跳跃游戏
- 跳跃游戏II
- K 次取反后最大化的数组和
- 加油站
- 分糖果(前后各自遍历)
- 柠檬水找零
- 根据身高重建队列(*排序+贪心)
- 用最少数量的箭引爆气球(*排序+贪心)
- 无重叠区间(排序+贪心)
- 划分字母区间(***二次遍历，第一遍记录字母最远，第二遍记录分割线)
- 合并区间(排序+贪心)
- 单调递增的数字
- 监控二叉树(*后序遍历+贪心)
涉及一个数组分成两份重量相同或最近的两个子数组的题，想到01背包。
完全背包问题，如果是组合数，那么外循环是物品，如果是排列数，那么外循环是背包。
买卖股票的套路即分别记录各个状态下的最大现金，一般的状态有：持有股票、未持有股票、第i次持有股票、第i次未持有股票、冻结期等
- 买卖股票的最佳时机II(*记录持有股票和未持有股票两个状态)
- 买卖股票的最佳时机III(***记录第一、二次持有股票和第一、二次未持有股票的状态)
- 买卖股票的最佳时机 IV
- 买卖股票的最佳时机含冷冻期**
- 买卖股票的最佳时机含手续费
子序列问题最主要是dp如何定义，一般定义dp[i]为以num[i]元素为结尾的子序列
也可以用双指针做回文问题，具体就是重中点想两边扩散 判断是否是回文串
通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)
接雨水和柱状图中最大的矩形有所不同，接雨水是找到左边最大和右边最大的下标，或者找到左边第一个大和右边第一个大的下标。柱状图是找到左边第一个最小和右边第一个最小的下标。
单调栈的目的是找到右边第一个最大/最小的下标，同时也可以找到左边第一个最大/最小的下标，前者是入栈的元素，后者是还在栈内的元素。(为了所有元素都涉及到，前后都得插入最大/最小值~0)
三个作用：查找一个点的根节点，判断两个点是否一个集合(两个点的根节点是否相同)，将两个节点接入到同一个集合
无向图计算冗余线时只需找相同根就行，而有向图则是判断是否有入度为2或者成环，冗余线在上述两种情况
-
分割平衡字符串 回文字符串的动态规划的dp设置是二维数组，存放开头下标到结尾下标处是否为回文字符串
-
[搜索二维矩阵 II]
-
[随机链表的复制]
-
[最小覆盖子串 必做]
-
[最长有效括号 必做]
-
[乘积最大子数组 动态规划经典题]
-
[最小栈 必做]
-
[寻找重复数 必做]
-
[路径总和 III]
-
[字符串解码 必做]
-
[数组中的第K个最大元素 必做！！]
-
[字符串解码 类逆波兰式]
-
[课程表 拓扑排序 必做]
-
[二叉树展开为链表 空间复杂度O(1)的做法]
-
[实现 Trie (前缀树) 很好懂 主要是实现]
-
[缺失的第一个正数 必做！！！ 类似的题如 寻找重复数 例如num[i]来获得解题思路]
-
[旋转图像 可看 类比一维数组旋转]
-
[矩阵置零 必做]
-
[LRU 缓存 经典题 LinkedHashMap的实现]
-
[数据流的中位数 必做!!]
-
[寻找峰值 logn做法 值得看]
-
[Pow(x, n) 可看]
-
[只出现一次的数字 I II 背下来]
-
[数字范围按位与 必做！！]
-
[交错字符串]
-
[面试题 01.01. 判定字符是否唯一 技巧：常数数组 存26个字母之类的数组 可以替换成位运算符]
当数组全为正时，需要找到某个连续子数组的和是否等于k时，可以用滑动窗口；当数组有正有负时，滑动窗口不适用，可以用map记录前i个数组的和，那么j-i连续子数组的和为后一段减前一段
哈希表里不一定放的是pre，可以是余数，可以是平均数等等， 主要看sum2-sum1这个公式如何推导
- 和为 K 的子数组**(前缀和 + 哈希表)
- 连续的子数组和(***哈希表里放的是余数)
- 剑指 Offer 42. 连续子数组的最大和
- 让所有学生保持开心的分组方法数(***排序+枚举)
- 插入区间(*二分+排序+一次遍历) 插入区间
- 最长连续序列***(set.count()哈希+枚举) leetcode
- 反转链表 II
- [路径总和 III]
*小美的树上染色 树除了二叉树基本都是用图的结构，从子节点(入度为1)进行拓扑遍历 存储图结构一般用邻接矩阵(二维数组) 邻接列表(包含列表的列表) 边列表(包含所有边的列表)