哈希表
要求O（1）复杂度找到值。
如果数组不大，推荐用数组而不是哈希表存。因为哈希表的O(1)是平均O(1) 。
双指针
双指针并不是一个具体的具体的算法，而是一种思路，是相对于两次遍历而言的。通常可以把两重for 循环优化到一次遍历。
堆
解决动态求最值/第K大值。
栈
实现非递归；
单调栈解决找一个值左/右第一个比它大/小的值。
扫描线
事件往往以区间的形式存在；
区间两端代表事件的开始和结束；
按照区间起点排序，起点相同的按照终点排序。
并查集
支持集合快速合并和查找操作的数据结构。
跟连通性有关的问题，都可以使用BFS和并查集，需要拆开两个集合的时候无法使用并查集。并查集可以处理动态连通性问题，BFS处理静态连通性问题。
字典树
字符矩阵类问题使用Trie比Hash更高效。
二分法
二分答案：同样是找满足某个条件的最值，但往往没有一个数组让你二分
BFS
使用队列作为主要的数据结构。适用于最短问题等。
DFS
DFS适用搜索全部的解，或者要求走到最深处的问题。尽管DFS不保存中间状态，也要限制递归深度才行。递归深度过深，也会超时 。
拓扑排序
四种问法：
求任意一个拓扑排序；
求是否存在拓扑排序；
求所有的拓扑序=>DFS；
求是否存在且仅存在一个拓扑序=>Queue中最多同时只有一个节点
动态规划
常见题型：计数、求最值、求存在性；
对于动态规划问题，首先要明确两点：状态和选择。然后就可以按照这个框架进行套用。
举个经典的例子，背包问题。我们的状态有「背包的容量」和「可选择的物品」。对于每件物品，选择就是「装进背包」或者「不装进背包」。所以可以定义二维数组dp[N][W]。任意元素dp[i][w]的含义是：对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值。dp[i][w] = max(把物品 i 装进背包, 不把物品 i 装进背包)
具体类型：
序列型动态规划：前i个；经常加状态（eg.房子颜色）。
划分型动态规划：“分成几段” “每个人分到的都是连续的一段”。给定一个序列，划分成若干段，每段满足一定的条件。如果要段数，就把段数加到维度里。思想很像序列型动态规划，但是用了分段的套路。
区间型动态规划：ij表示区间；初始化和运算顺序都是基于区间长度。子区间获得：取一段/二分..
背包型动态规划：总承重一定要放到状态里；看最后一个物品要不要；见下文。
博弈型动态规划：必胜：下面只要有一个必败；必败：下面全是必胜；当前的是先手。
双序列型动态规划
时间优化：画图/小例子/式子展开 前缀和数组
背包问题
背包问题中，背包的总承重一定会是数组的一维。
如果是0-1背包，即数组中的元素不可重复使用，nums放在外循环，target在内循环，且内循环倒序；
for num in nums:for i in range(target, nums-1, -1):
如果是完全背包，即数组中的元素可重复使用，nums放在外循环，target在内循环。且内循环正序。
for num in nums:for i in range(nums, target+1):
如果组合问题需考虑元素之间的顺序，需将target放在外循环，将nums放在内循环。
for i in range(1, target+1):for num in nums:
关于互联网持续学习圈
