数据结构
并查集
- 并查集
- 确定元素属于哪一个集合，将两个子集合并成同一个集合
- 环
- 最小生成树
- 无向图才能正确处理强联通分量
散列表(哈希表)
哈希表
- 缓存管理，快速实现变量在内存中的读取
- DNS 解析，快速转化
- 扩容时间：O(n)
哈希函数
- 文件校验，key的快速查询
- 加密
- 分布式，一致性哈希
一致性哈希
- 分布式哈希算法，主用用来解决分布式系统中的负载均衡问题
- 为了解决增加候选集的时候，哈希的值尽可能不变
- 没有固定的顺逆时针
散列表平均查找长度：
- 先对所有元素取余
- 不存在冲突的长度为 1，存在冲突的从 1 开始累加
- 平均查找长度 = 所有元素的查找长度之和 / 元素个数
- 访问时间复杂度 O(1)，查找时间复杂度 O(n)
队列
队列
- 先进新出
- 用于广度优先搜索
堵塞
- 在队满时插入
- 在队空时删除
循环队列
- front 是队头，rear 是队尾
线性表
线性表分类
- 顺序表
- 链表
- 指针实现
- 单链表
- 双链表
- 循环链表
- 数组实现
- 静态链表
- 指针实现
单向链表
- 相交，则尾节点一定相同
- 快慢指针判断环，有环的和无环的不可能相交
链表
- 适合实现稀疏图的邻接关系
树
不存在环的图
Trie 树
- 用于统计和排序大量字符串
- 可以进行深度优先，不适合广度优先
算法
各种算法
- Floyd-Warshall 算法
- 用于解决带权图中任意两点之间的最短路径问题
- Dijsktra 算法
- 用于求带权图中某一点到其他所有点的最短路径
- 挑选离源点最近的点，然后更新其他点到源点的距离
- Prim 算法
- 用于求加权连通图的最小生成树，适用于稠密图
- Kruskal 算法
- 用于求加权连通图的最小生成树，适用于稀疏图
遍历
- 先序遍历
- 中左右
- 中序遍历
- 左中右
- 后序遍历
- 左右中
- 层次遍历
- 类比广度优先遍历
排序
有序数组用堆排序最快。
- 不稳定排序
- 快排
- 堆排序
分治
一定要独自子问题。
- 使用分治法
- 二分查找
- 排序算法
- 快排
- 归并
动态规划
- 最长公共子序列时间复杂度 O(mn)
- KMP 时间复杂度 O(m+n)