学习要点
基本功是区别业余选手和职业选手的根本。深厚功底来自于过遍数
最大误区：只做一遍
五毒神掌
刻意练习
反馈:看题解、看国际版高票回答
五毒神掌
不要死磕，要看代码学习（一定要看国际版的高票回答）
自己写
24小时候后
一周后
面试前
数组
链表
存储数据结构的存储空间可以不连续，各数据节点的顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系由指针域来确定
跳表
用于元素有序的情况
升维思想+空间换时间
栈
先入后出
队列
先入先出
双端队列
两端可以进出的队列
优先队列
按照元素的优先级取出:O(logn)
底层具体实现的数据结构较为多样和复杂：heap、bst 、treap
哈希表 也叫散列表，根据关键码值而直接进行访问的数据结构 映射函数将任意长度的输入通过散裂算法之后映射成固定长度的输出。
二叉树遍历
前序：根-左-右
中序：左-根-右
后序：左-右-根
二叉搜索树
1、左子树上所有节点的值均小于它的根节点的值
2、右子树上所有节点的值均大于它的根节点的值
3、以此类推：左、右子树也分别为二叉查找树
中序排列：升序排列
递归
循环，通过函数体进行的循环
堆
可以迅速找到一维树中的最大或者最小值的数据结构
二叉堆
1、是一棵完全树
2、树中任意节点的值总是>=其子节点的值（大顶)；树中任意节点的值总是<=其子节点的值(小顶)
3、二叉堆一般都通过“数组”实现
4、父节点和子节点的位置关系：
索引为i的左孩子的索引是(2*i+1)
索引为i的右孩子的索引是(2*i+2)
索引为i的父节点的索引是floor((i-1)/2)
5、插入操作O(logN)：
新元素插入到堆的尾部
依次向上调整整个堆的结构（一直到根即可）
6、删除堆顶操作(O(logN))
堆尾元素替换到顶部（堆顶被删除）
依次从根部向下调整整个堆的结构（一直到堆尾即可）
图
点: 度-入度和出度
点与点之间：联通与否
边: 有向和无向（单行线）
权重
分治
分解,将要解决的问题划分成若干规模较小的同类问题
求解,当子问题划分得足够小时，用较简单的方法解决
合并,按原问题的要求，将子问题的解逐层合并构成原文题的解
回溯
采用试错的思想，尝试分布地解决一个问题。在分布解决问题的过程中，当它通过尝试发现现有的分布答案不能得到有效的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它可能的分步解答再次尝试寻找问题的答案。在最坏的情况下，会导致一次复杂度为指数时间的计算。
深度优先搜索 && 广度优先搜索
搜索：每个节点都要访问有且仅有一次
深度优先代码
| 非递归写法 | 递归写法 |
|---|---|
|
|
广度优先搜索 - 非递归写法
def BFS(graph,start,end):
queue = []
queue.append([start])
visited.add(start)
while queue:
node = queue.pop()
visited.add(node)
process(node)
nodes = generate_realated_nodes(node)
queue.push(nodes)
...
贪心算法
在每一步选择中都采取在的那个前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
动态规划
分治+最优子结构
1、最优子结构 opt[n]=best_of(opt[n-1],opt[n-2],...)
2、存储中间状态：opt[i]
3、递推公式（状态转移方程或者DP方程）
贪心算法 vs 动态规划
贪心算法对每个子问题的解决方案都做出选择，不能回退
动态规划则会保存以前的运算结果，并根据以前的结果选出最优子结构，有回退功能。
共性：找到重复子问题
二分查找
前提: 1、目标函数单调
2、存在上下届
3、能够通过索引访问
代码模板
left,right=0,len(array)-1
while left<=right:
mid = (left + right) / 2
if array[mid] == target:
# find the target!!
break or return result
elif array[mid] < target:
left = mid + 1
else:
right = mid -1
字典树
即Trie树，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈吸表高
基本性质：
1、节点本身不存完整单词
2、从根节点到某一节点，路径上的字符连接起来，为该节点对应的字符串
3、每个节点的所有子节点路径代表的字符都不相同
核心思想: 空间换时间
利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的
并查集
适用场景：组团、配对
基本操作：
makeSet(s):建立一个新的并查集，其中包含s个单元素集合
unionSet(x,y):把元素x和元素y所在的集合合并，要求x和y所在的集合不想交，如果相交则不合并
find(x):找到元素x所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了。
双向广度搜索
基于广度优先搜索，两段均会进行广度搜索操作
启发式搜索
基于广度优先搜索，升级的点在于根据启发式函数（一种告知搜索方向的方法）猜测哪个邻居节点会导向一个目标。
AVL 树
平衡因子：|左子树的高度-右子树的高度|<=1
通过旋转操作进行平衡：
左旋、右旋、左右旋、右左旋
不足：节点需要存储额外信息、且调整次数频繁
红黑树
是一种近似平衡的二叉搜索树，能确保任何一个节点的左右子数的高度差小于2倍
满足如下条件：
1、每个节点要么是红色，要么是黑色
2、根节点是黑色
3、每个叶节点（NIL节点，空节点）是黑色的
4、不能有相邻接的两个红色节点
5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
AVL VS 红黑树
AVL查询更快，多用在需要高效搜索的数据库里
红黑树插入删除更快、更省存储空间，用在map，multimap,multisetin C++等
位运算
| 位运算要点 | 注释 |
|---|---|
| x^0=x | |
| x^1s=~x | |
| x^x=0 | |
| c=a^b=>a^c=b,b^c=a | |
| a^b^c=a^(b^c)=(a^b)^c | |
| x&(~0<<n) | 将x最右边的n位清零 |
| (x>>n)&1 | 获取x的第n位值(0|1) |
| x&(1<<n) | 获取x的第n位的幂值 |
| x|(1<<n) | 仅将第n位置为1 |
| x&(~(1<<n)) | 仅将第n位置为0 |
| x&((1<<n)-1) | 将x最高位至第n位(含)清零 |
| x&(~((1<<(n+1))-1)) | 将第n位至第0位（含）清零 |
| x&1 | 判断奇偶，结果为1是奇数，否则为偶数 |
| x>>1 | x除以2 |
| x=x&(x-1) | 清零最低位的1 |
| x&-x | 得到最低位的1 |
| x&~x | 清零 |
布隆过滤器
HashTable + 拉链存储重复元素
一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。
优点:空间效率和查询时间都远远超过一般算法
缺点：有一定的无识别率和删除困难
LRU
最近最少使用策略
查询、修改、更新时间复杂度均为O(1)
排序算法：
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn),因此也成为非线性时间比较类排序
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
初级排序：O（n^2）
选择排序：每次找最小值，然后放到待排序数组的起始位置
插入排序：从前到后逐步构建有序序列;对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
冒泡排序：嵌套循环，每次查看相邻的元素，如果逆序则交换
高级排序：O(nlogn)
快速排序：数组取标杆pivot，将小元素放pivot左边，大元素放pivot右侧，然后依次对右边和右边的子数组继续快排;以达到整个序列有序
归并排序：把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列
堆排序：数组元素依次建立小顶堆;依次取堆顶元素，并删除
特殊排序
计数排序：计数排序要求输入的数据必须是有确定范围的整数。将输入的数据值转化为键存储在额外开辟的数组空间中;然后依次把计数大于1的填充回原数组
桶排序：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）
基数排序：按照低位先排序，然后收集;再按照高位排序，然后再收集;依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序
常见的DP题目和状态方程
爬楼梯：dp[i]=dp[i-1]+dp[i-2]
不同路径：dp[i][j]=dp[i-1][j]+dp[i][j-1]
打家劫舍: dp[i]=max(dp[i-2]+nums[i],dp[i-1])
或者
dp[i][0]=max(dp[i-1][0],dp[i-1][1])
dp[i][1]=dp[i-1][0]+nums[i]
最小路径: dp[i][j]=min(dp[i-1][j],dp[i][j-1])+A[i][j]
股票买卖: dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
编辑距离:
if(word1[i]==word2[j]) dp[i][j]=dp[i-1][j-1]
else
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
最长子序列:
if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1
else dp[i][j]=max(dp[i-1][j],dp[i][j-1])
最长子串:
if (s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1
else dp[i][j]=0
最长回文字串: dp[i][j]=(s.charAt(i)==s.charAt(j)) && (j-i<3 || dp[i+1][j-1])?true:false;
不同的子序列:
if(S[j]==T[i]) dp[i][j]=dp[i-1][j-1]+dp[i][j-1]
if(S[j]==T[i]) dp[i][j]=dp[i][j-1]
字符串匹配算法
暴力法：挨个比较
Rabin-Karp算法：选择好的哈希函数算出子串的哈希值，然后将它和目标字符串中的子串的哈希值进行比较，哈希值不同，字符串必然不匹配;如果哈希值相同，还需要挨个比较
KMP算法：当子串与目标字符串不匹配时已经知道了前面匹配成功的那一部分的字符，利用这个已知信息，下一次从匹配失误的那个位置开始比较，这样就提高了效率