最近开始找暑期实习了，刷了一些算法题。下面做个汇总和小结。
数据结构
数据在内存中要么根据偏移得到（数组），要么是地址跳转（链表，树）
数组
中间修改是O(n)，动态数组可以O(1)追加元素，但是开销主要在扩容的时候。有序数组可以两指针夹逼
链表
根据index查找O(n)，快慢指针的方法
树
树的遍历方式，二叉搜索树，二叉平衡树(AVL，红黑树)，多路平衡树(B+，R)。 求最小生成树的方法
队列，双端队列
队列可以由两个栈实现，反之亦然。python队列可以用deque
栈
可以由list简单实现，但是用栈解的题目还是不容易直接看出来，可以先列举几个简单情况观察一下。
最小堆，最大堆
平衡插入和查找的时间开销，都是O(nlogn)
哈希表，集合
基于hash表的set比map/dict更省内存，set也可以用树来实现做到有序，但是从O(1)变成O(logn)。
图
图很少遇到，求最短路径，二分图匹配，拓扑，并查集，网络流。
复杂数据结构
B+树，R树，KD树，线段树
算法
分治
快排，归并都是DC，DC通常是递归的去解决两边的问题，有时候也需要和中间的一并考虑
贪心
例如根据起止点排序的一类问题
搜索
DFS通常是递归，回溯，栈； BFS通常是循环，队列。搜索很常用，另外还有双向的BFS，A*等
排序
主要是快排，归并排序，桶排序。另外用位图排序可以很好解决内存占用的问题
查找
二分搜索
动态规划
子问题以及不对之后产生影响，例如背包问题。动态规划通常也不容易看出来，有一维的，二维的，还有枚举所有可能的。
其它
字符串算法(子串匹配kmp, 回文串m)；数学，包括几何，概率，博弈，随机，近似
小结
并没有系统的练习过。。随着做题不断补充。。
- 括号匹配（栈），表达式求值（中缀转后缀，栈）
- 排列，组合（dfs，逆序数，next permutation）
- 回文子串（dp）
- 蓄水问题（左右扫描）
- 链表（dummy 头结点）
- 前后夹逼要优于one pass（一遍扫描）
- 英文字典（字典树）
- 区间求和（树状数组，线段树）
- 滑动窗口（deque，双端队列）
- 强盗抢劫和买卖商品（贪心）