查询：O(1) 插入：O(n) 删除：O(n)
链表
查询：O(n) 插入：O(1) 删除：O(1)
- 迭代
- 递归
环判断
- set判重
- 快慢指针
栈Stack
先进后出(FILO)
单调栈
下一个更大的数
队列Queue
先进先出(FIFO)
from collections import deque
q = deque()
q.append(1)
q.append(2)
q.append(3)
q.popleft()
q.pop()
堆
log(n)
import heapq
# 小顶堆
heap0 = []
heapq.heappush(heap0, 5)
heapq.heappush(heap0, 4)
heap1 = [5, 2, 3, 4]
heapq.heapify(heap1)
# 优先队列
heap2 = []
heapq.heappush(heap2, (5, '5'))
heapq.heappush(heap2, (4, '4'))
print(heapq.heappop(heap0)) # 出堆
print(heapq.heappushpop(heap0, 0)) # 先压后弹
print(heapq.heapreplace(heap0, 0)) # 先弹后压
# 大顶堆，没法push，一般用小顶堆相反数
data = [1, 5, 3, 2, 8, 5]
heapq._heapify_max(data)
# 优先队列，可以用heapq实现，也可以用下面的同步方法
from queue import PriorityQueue
二叉堆
父节点的权值不大于儿子的权值（小顶堆），可以用数组存储数据
单调队列
固定大小滑动窗口，获取最值。 单独看 push 操作的复杂度确实不是 O(1)，但是算法整体的复杂度依然是 O(N) 线性时间。要这样想，nums 中的每个元素最多被 push_back 和 pop_back 一次，没有任何多余操作，所以整体的复杂度还是 O(N)。 单调队列
映射Map
HashMap/TreeMap 无序/有序
from collections
# 有序字典
ordmap = collections.OrderedDict()
ordmap.move_to_end(key)
ordmap.popitem(last=False)
# 计数字典
countmap = collections.Counter()
# 访问不存在的key时自动添加key值为默认值
defaultdict([int,list,set,str,dict])
散列冲突：分离链接、线性探查
集合Set
HashSet/TreeSet
set_a = set('12345')
set_b = set(['1', '2', '3', '4', '5', '5'])
set_c = {1, 2, 3, 4, 5, 5}
set_d = set(set_a)
set_a.add('6')
set_a.update(['1', '2']) # 可以添加列表、集合等
set_a.remove('1') # 元素不存在会报错
set_a.discard('1') # 元素不存在不会报错
print(set_a-set_b)
print(set_a | set_b)
print(set_a & set_b)
print(set_a ^ set_b)
树Tree
二叉树-完全二叉树-满二叉树
二叉搜索树BST
左子树小于根节点 右子树大于根节点 左右子书满足二叉搜索树
遍历
前序pre：根-左-右 中序in：左-根-右 升序返回 后续post：左-右-根 中序遍历的两种写法
# 递归
def inorder(root):
if root:
inorder(root.left)
print(root.val)
inorder(root.right)
# 迭代
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
print(root.val)
root = root.right
字典树/前缀树Trie
图Graph
广度优先搜索BFS
最短路径问题
狄克斯特拉算法
有向无环加权图最小开销问题
深度优先搜索DFS
递归
重复计算->效率低
分治
贪心
剪枝-回溯
位运算
x^0=X
x^x=0
x&1==0or1 #判断奇偶
x=x&(x-1) #清零最低位1
x&(-x) #取最低位的1
补码=反码+1
动态规划
NP完全问题
旅行商问题 集合覆盖问题
并查集
数组实现
LRU/LFU Cache 缓存替换算法
双链表实现
布隆过滤器
判断在不在，肯定不在/应该在