现在真是不知道还应不应该做 LeetCode 了
数组/双指针
两数之和
给定一个数组字和一个目标值，问其中哪两个数字加起来正好等于目标值？只要找出一对就行（通常是返回它们的下标）
关键洞察：
1、对于 x，我们马上知道它应该匹配 y=target-x
2、我们只需要知道 target-x 是否曾经出现过，以及如果出现了，在哪里
所以每次往前走，只需要放在 hashmap 里
三数之和
给定一串数，找出所有不重复的三元组，使得三个数加起来等于 0（或某个目标值）。
字符串
最长无重复子串
在一个序列里寻找一段最长的连续区间，区间内没有任何重复元素
双指针，中间是“ABC”，前面的指针，遇到重复的了，比如“B”，就让后一个指针，直接跳转到“C”，形成“CB”即可
动态规划
这东西看完就会，会完了马上忘
将问题拆解成相互重叠的子问题，通过定义“状态”和“状态转移方程”来有序地重用中间结果，从而避免重复计算
重叠子问题和无后效性的状态
感觉基本上，除了爬楼梯，都有“抉择”，即 max 在两个状态里二选一
哦哦，我大概抓住重点了。重点是，你假装，有人已经告诉你了，n-1 时，状态的答案
爬楼梯
你正在爬楼梯，一次可以爬 1 阶或 2 阶，到达第 n 阶有多少种不同的方法
dp[i] = dp[i-1] + dp[i-2]
背包问题
0-1 背包：每件物品只有 1 个，选或不选。
完全背包：每件物品有无限个，可以选任意次数。
多重背包：每件物品有有限个（给定数量）。
二维费用背包：除了重量，还有体积等其他限制。
分组背包：物品分组，每组最多选一件。
做题时，一般就是经典背包问题，即 0-1 背包
定义：给定 N 件物品和一个容量为 V 的背包，每个物品有重量和价值。不超重，拿最大价值。
关键：
我们对物品一件一件的看过去，当看到第 i 件时：
我们不管之前你拿了多少物品，只关心当前背包剩余的容量
你此时只有两个选择：（1）拿起 i（2）不拿 i
定义 dp[i][j] 表示面对第 i 个物品时，背包剩余容量为 j，获取的最大总价值
如果能拿起，则：dp[i][j] = max(dp[i-1][j] , dp[i-1][j - w[i]] + v[i])
如果拿不起，那就跳：dp[i][j] = dp[i-1][j]
拿起时那个公式并不贪心，因为 j - w[i] 会导致列序号缩小
完全平方数
我们要求 13 的最小完全平方数组成个数
我们假装已知 12、11...（实际上是现场求）
13 减去任何一个 4，得到 9，相当于 9 的完全平方数+1。对着每一个完全平方数试过去，找最小的
零钱兑换
零钱兑换和完全平方数类似
也是，如果你要知道 11 元怎么找，你假装知道 10、9... 所有的找法
你用 11，减去现有所有面额，你再和已知的进行比较，这里一个个枚举即可
单词拆分
问题就是，能否用一些字符串，拼凑成一个新的字符串
还是那个道理，如果你想知道你这个字符串能不能拼成，那你就用你的字符串，减去所有的候选字符串，看剩下的是否能拼成，这就是状态转移
最长增长子序列 LIS
定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度，注意 nums[i] 必须被选取
问题关键还是状态的定义：状态就是某个条件下，子问题的答案
和前面的题有微小区别的是，这个题不是返回 dp[n] 而是返回 max_element(dp.begin(), dp.end())
毕竟那个最长的不一定是用最后一个元素结尾
排序
冒泡排序
从前到后的扫描数组，每次遇到逆序，就交换，直到这次没有交换
选择排序
将数组划分为两个部分
每一轮从未排序部分中选出最小（或最大）的元素，将其与未排序部分的第一个元素交换位置
插入排序
将数组划分为两个部分
每次从未排序部分取出第一个元素，在已排序部分从后向前扫描，找到它应该插入的位置
归并排序
先将整个序列递归地二分，直到每个子序列只剩一个元素（一个树）
将相邻的两个有序子序列合并成一个更大的有序序列（合并时，两个节点中都是一堆有序序列，你看谁开头更小，就先取谁）
二叉树
前中后
前：根左右
中：左根右
后：左右根
即左永远在右前面，前中后序描述的是根所在的位置。
呃，从树的图形来看，遍历是，一定是从根节点，向左侧拉一根线，逐步的包围整改树
前中后序，实际上就是左下右序
前序就是，按照每个节点的左侧，画一个圆点，这根线碰到圆点的先后顺序
中序后序同理，无非圆点在下面和右边
算法上，递归的很好写，无非按照前中后，调整自己 getName 函数的位置
非递归，你只需要记住，它是一个栈来模拟。
递归时，f(LChild)，就是栈里左孩子压栈，右侧同理
getName，就是弹出并访问
所以前序其实就是入栈，弹，左，右
中序就是，左（递归的看，直到没有），弹，右
后序比较独特。
堆
定义：
完全二叉树 + 堆性质
完全二叉树 = 了最后一层，其他层都是满的，且最后一层的节点都靠左排列
利用数组可以紧凑地表达完全二叉树的结构，无需指针
堆性质：任意节点的值 ≥ 其子节点的值。根节点是整个堆中的最大值
特点：兄弟节点之间没有必然顺序
对于数组中索引为 i 的节点（假设从 0 开始）：
父节点索引：(i - 1) // 2
左子节点索引：2 * i + 1
右子节点索引：2 * i + 2
C++ 里实际上有一套堆相关的算法（我还真没用过）
std::priority_queue 优先队列，内部是一个堆，只定义了操作：插入元素、取出最大 or 最小元素（只能是一种）
没有 std::heap，优先队列封装了堆
<algorithm>里面有一些和堆相关的函数