PS：根据极客时间《数据结构与算法之美 -- 王争》学习总结，极客时间版权所有: https://time.geekbang.org
一、复杂度分析
- 时间复杂度：
- 表示方式：大O表示法，表示代码执行时间随数据增长的趋势，也叫渐进时间复杂度
- 计算方法：加法法则，乘法法则
- 常见量级：O(1)、O(logn)、O(n)、O(nlogn)、O(n2) ... O(nk)、O(2n)、O(n!）
- 常见分类：最好、最坏、平均、摊还
- 空间复杂度：略
- 其他：
- 递归树分析复杂度
二、线性表
- 数组：连续内存空间
- 链表：不连续的内存空间
- 分类：单链表、双链表、循环链表
- tips：
- LRU缓存淘汰策略可用有序单链表实现
- 可用增加散列表的方式，提高查询链表的效率，降为O(1)
- 利用哨兵简化链表实现
- 栈：先近后出，一种操作受限的线性表
- 分类：顺序栈（数组实现）、链式栈（链表实现）
- 应用：函数调用、表达式求解、括号匹配
- tips：支持动态扩容的顺序栈，摊还分析复杂度还是O(1)
- 队列：先进先出
- 分类：顺序队列、链式队列、循环队列、阻塞队列、并发队列
三、散列表
- 应用：加密、数据校验、负载均衡、分片、分布式（一致性哈希）
四、树
- 概念：跟节点、叶子结点、父节点、子节点、兄弟节点；高度、深度、层
- 分类：二叉树、完全二叉树、满二叉树、二叉查找树、平衡二叉树、B树
- 遍历：前序、中序、后序、层序
- 经典实现：
- 平衡二叉查找树：AVL树、红黑树、伸展树、树堆
- 堆：
- 定义：
- 堆是一个完全二叉树；
- 堆中每一个节点的值都必须大于等于子树中每一个节点
- 操作：
- 插入：上浮堆化
- 删除：下滤堆化
- 排序：建堆、排序
- 定义：
五、图
六、基本算法思想
- 递归：
第一步：找到递推公式和终止条件
f(1) = 1; f(2) = 2; f(n) = f(n-1)+f(n-2)
第二步：翻译成代码
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}
- 贪心算法：
- 分糖果（满足最多孩子）：从需求小的孩子开始，将最小能满足他的糖果先分给他。依次类推
- 钱币找零（用最少纸币）：先用最大纸币，再依次递减，最后用1元补齐
- 区间覆盖（最多选出多少个区间）：从左到右选，每次选和左面不重合，右端点右尽量靠左的区间，依次类推
- 分治算法：分解、解决、合并
- 求逆序对：
- 10G订单金额排序：1-100元，101-200元... 分别排序
- 回溯算法：
- 8皇后问题
- 0-1背包问题
- 正则表达式
- 动态规划：
- 0-1背包问题：
- 问题特征：
- 最优子结构：最优解中包含子问题最优解
- 无后效性：后面的决策不会影响前面已经确定的决策
- 重复子问题：相同阶段不同决策，含有重复的状态
七、排序
- 插入排序
- 冒泡排序
- 选择排序
- 归并排序
- 快速排序
- 桶排序
- 堆排序
八、搜索
九、查找
- 二分查找
- 跳表查找
十、字符串匹配
- 单模式匹配：
- BF算法：暴力匹配
- RK算法：通过哈希优化
- BM算法：根据坏字符和好后缀，一次性向右移动多位