- 一维：
- 基础：数组(array、string), 链表(linkedList);
- 高级：栈(stack)、队列(queue)、双端队列(deque)、集合(set)、映射(Hash、Map);
- 二维：
- 基础：树(tree)、图(graph);
- 高级：字典树(trie)、二叉搜索树(BinarySearch Tree){红黑树、AVL}、堆(heap)
- 特殊： 布隆过滤器、LRU cache
- 常见的算法时间复杂度(从低到高排序)：O(1)、O(logN)、O(n)、O(n^2)、O(n^3)、O(2^n)、O(n!)
- 空间复杂度比较常用的有：O(1)、O(n)、O(n²)
- 操作的时间复杂度：
- 数组：插入、删除, 要对数组的部分元素进行移动，所以时间复杂度为 O(n);
查找,数组通过系统的内存管理器直接对数组元素进行访问，时间复杂度为O(1)。 - 链表：插入、删除, 直接改变前后元素的指针方向, 时间复杂度为O(1); 查找, 必须要从头开始循环查找到目标元素, 时间复杂度为O(n)。
- 跳表：用另外的表进行数组元素索引的建立,将一维的数据结构变为二维。增删查的时间复杂度皆为O(logN), 由于效率高，所以redis用跳表来代替树。
- 数组：插入、删除, 要对数组的部分元素进行移动，所以时间复杂度为 O(n);
- 例题：package array and linklist
- 操作的时间复杂度：
- 栈(stack)： 存入(push)、弹出(pop)、查看栈顶元素(peek)，O(1)；寻找特定数值的位置，O(n)。
- 队列(queue)：队尾添加、队头移除、队头获取的时间复杂度皆为O(1)。
- 双端队列(deque)：队头和队尾添加、移除和获取的时间复杂度都为O(1)。
- 优先队列(PriorityQueue)：插入为O(1),因为有优先级算法所以取出时的时间复杂度为O(n),底层实现为堆(heap)或二叉搜索树(bst)
- Deque操作的实例代码: class que.DequeTest
- 分析 Queue 和 Priority Queue 的源码：
- Queue的源码分析：
- PriorityQueue的源码分析：
- 1.PriorityQueue和Queue的区别在于，它的出队顺序与元素的优先级有关，对PriorityQueue调用remove()或poll()方法，返回的总是优先级最高的元素。 要使用PriorityQueue，我们就必须给每个元素定义“优先级”。
- 2.Java对于优先级的实现是通过Comparable接口实现的。传入PriorityQueue的对象实现Comparable接口，在offer对象的时候会对象按照compare方法的规则 进行排序，从而实现优先级队列。
- Queue的源码分析：
https://juejin.cn/post/6928650091377098765
- 根节点：树的起始节点
- 父节点
- 子节点
- 邻居节点
- 层级：根节点为第一层，叶根节点为最后一层
- 二叉树：每个节点最多只能有两个子节点的树结构
- 图没有闭环就是树结构（树是特殊化的图）；树的每个节点只有一个子节点时就是链表结构（链表是特殊化的树）
- 特性：所有的结点的值都小于其右节点并大于其左结点
- 中序遍历：升序
- 常见操作与时间复杂度：
- 查询：O(log(n))
- 新增：O(log(n))
- 删除：O(log(n))
- 前序：先访问中间节点，再访问左节点，最后访问右节点
- 中序：先访问左节点，再访问中间节点，最后访问右节点
- 后序：先访问左节点，再访问右节点，最后访问中间节点
- 代码示例：class={tree.TwoChildrenTree.class}
可以迅速找到一堆数中的最大或最小值的数据结构。根节点最大称为大顶堆（大根堆），根节点最小称为小顶堆（小根堆）。 常见的堆有二叉堆、斐波那契堆等。
- 找到最大值：O(1)
- 删除最大值：O(logN)
- 新增：O(logN) | O(1)
-
完全通过二叉树来实现（不是二叉搜索树），满足一下性质
- 是一颗完全树
- 树中任意节点的值总是>=或<=其子节点
-
二叉堆的效率并不是最好的，只不过因为比较好理解，所以经常作为面试题
-
二叉堆一般通过数组来实现：假设第一个元素再数组中的索引为0，则父节点和子节点的关系如下：
- 索引为i的左孩子索引是(2 * i + 1);
- 索引为i的右孩子索引是(2 * i + 2);
- 索引为i的父节点索引是floor((i - 1) / 2);
-
操作过程：
- Insert(O(logN)): 先插到尾部，然后依次调整向上的顺序，取floor((i - 1) / 2)，进行比较；
- Delete Max(O(logN)): 删除堆顶元素，比较两个子节点的大小，与较大的那一个子节点交换值；
// 1. 终止条件
// 2. 处理本层的逻辑
// 3. 进入到下一层
// 4. 清理一些全局的变量
- 处理本层逻辑和下探到下一层可以归到一个步骤中去。
- 不要人肉递归、不要人肉递归、不要人肉递归。关注本层的逻辑即可，千万不要下探到底 否则会浪费很多时间。
// 1. 终结条件
// 2. 拆分任务
// 3. 下探到下一层
// 4. 合并结果
// 5. 清理一些全局变量
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> allResults = new ArrayList<>();
if(root==null){
return allResults;
}
travel(root,0,allResults);
return allResults;
}
private void travel(TreeNode root,int level,List<List<Integer>> results){
if(results.size()==level){
results.add(new ArrayList<>());
}
results.get(level).add(root.val);
if(root.left!=null){
travel(root.left,level+1,results);
}
if(root.right!=null){
travel(root.right,level+1,results);
}
}