数据结构和算法
基础知识
- 一维：字符、数组、链表、栈、队列(双端队列;循环队列;优先队列;阻塞队列;并发队列)、散列表(Set;Map)
- 二维：树(普通二叉树;平衡二叉树;完全二叉树;二叉搜索树;四叉树;红黑树;自平衡二叉搜索树)、图、堆heap、并查集、字典树
- 排序：冒泡排序、插入排序、归并排序、快速排序、拓扑排序、堆排序、桶排序
- 二叉树：节点都是一分为二；二叉搜索树：左节点的值<根节点的值<右节点的值；平衡二叉树：左右子树的高度差<=1；B树：多路平衡搜索树，m阶的B树可以称为m树，m=2就是二叉树。B树的特点：1，每个节点有k-1个元素，k个孩子；2，根节点：1<=k<=m-1，非根节点：ceil(m/2)<=k<=m-1（https://zhuanlan.zhihu.com/p/52028653）。
- 插入排序比冒泡排序快：冒泡需要做数据交换，而插入是数据移动，一般插入比冒泡快3倍
- 快速排序比归并排序受欢迎：快速排序虽然不是稳定的排序，但是归并排序空间复杂度是O(n)
- 求无序数组中的第K大元素：用快速排序，时间复杂度O(n)；用小顶堆，堆的大小=K，时间复杂度O(nlogk)，空间复杂度O(k)
- LRU算法的实现：用链表，添加和查找都需要O(n)；用散列表+链表，每次先查散列表得到链表的指针，则CURD都是O(1)
数据结构
| 结构 | 搜索 | 插入删除 | leetcode | 备注 |
|---|---|---|---|---|
| 数组 | O(n) | O(n) | 242 | 基于下标的随机访问是O(1) |
| 链表 | O(n) | O(1) | 24/25/146 | |
| 栈 | O(n) | O(1) | 20/739 | 顺序栈(基于数组)、链式栈(基于链表) |
| 队列 | O(n) | O(1) | 239/347 | 顺序队列(基于数组)、链式队列(基于链表)。239双端队列347优先队列 |
| 跳表 | O(logn) | O(logn) | 数据存在顺序链表中，辅以m条索引 | |
| 散列表 | O(1) | O(1) | 又称哈希表，数据存在数组中，出现散列冲突再用链表存 | |
| 二叉搜索树 | O(logn) | O(logn) | 230 | |
| B树 | O(logn) | O(logn) | ||
| 红黑树 | O(logn) | O(logn) | ||
| AVL树 | O(logn) | O(logn) | ||
| 前缀树 | 212 |
数组排序算法
| 算法 | 时间复杂度 | 空间复杂度 | 是否稳定 | leetcode | 备注 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(1) | √ | n次冒泡 | |
| 插入排序 | O(n^2) | O(1) | √ | 以第1个元素为基准点，排在它左边或右边 | |
| 归并排序 | O(nlogn) | O(n) | √ | 递归拆分成小段，小段排序后再合并 | |
| 快速排序 | O(nlogn) | O(1) | × | 912/215 | 每次选一个数为基准，把数组分成两堆。不断递归 |
| 堆排序 | O(nlogn) | O(1) | × | 973 | 先建堆，再排序 |
二分查找算法
| 基于 | 查找 | 插入删除 | 缺点 |
|---|---|---|---|
| 顺序数组 | O(logn) | O(n) | 需要连续内存空间，频繁的插入删除不高效 |
| 散列表 | O(1) | O(1) | 不能顺序遍历 |
| 跳表 | O(logn) | O(logn) | 空间复杂度是O(n)，适合空间换时间的场景 |
| 红黑树 | O(logn) | O(logn) | 程序难以实现 |
怎么实现一个优先级队列，优先级高的先出
- 用数组实现，数组元素里面有一个优先级字段，插入时就排好序
- 用大顶推来实现