🗒️数据结构

二分查找

右移左移

二分查找相同元素时，返回相同值最左侧的下标

在求一个数在数组里的排名时，可以使用leftmost;求前任也用leftmost;求后任就用rightmost

2024.10.19

1-链表

1.1-双向链表

1.2-递归遍历

从索引0开始存储数据：节点i的父节点为floor（（i-1）/2）（向下取整） 节点i的左孩子：2i+1，右孩子：2i+2

最后一个非叶子节点的索引公式：size/2 - 1

二叉树

• pre-order前序遍历，对每一棵子树，先访问该节点然后式左子树，最后是右子树

• in-order中序遍历，对每一棵子树，先访问左子树，然后是该节点，最后是右子树

• post-order后序遍历，对每一棵子树先访问左子树，然后式右子树，最后是该节点

二叉搜索树

• 树节点增加key属性，用来比较谁大谁小，key不可以重复

• 对于任意一个树节点，它的key都比左子树的key大，同时比右子树的key小

avl树

如果一个节点的左右孩子高度差超过1，则此节点失衡，需要旋转

• 失衡节点的bf>1，即左边更高

• 失衡节点的左孩子的bf≥0，即左孩子这边也是左边更高或者等高

• 失衡节点的bf>1，即左边更高

• 失衡节点的左孩子的bf<0，即左孩子这边是右边更高

• 失衡节点的bf<-1，即右边更高

• 失衡节点的右孩子的bf>0，即右孩子这边左边更高

• 失衡节点的bf<-1，即左边更高

• 失衡节点的右孩子的bf≤0，即右孩子这边也是右边更高或者等高

红黑树

• 所有节点都有两种颜色：红与黑

• 所有null视为黑色

• 红色节点不能相邻

• 根节点是黑色

• 从根到任意一个叶子节点，路径中的黑色节点数一样（黑色完美平衡）

B树

磁盘中存储数据一般用b树

哈希表

给每份数据分配一个编号，放入表格（数组） 建立编号和表格索引的关系，将来可以通过编号快速查找数据

归并排序

• 分- 每次从中间切一刀，处理的数据就少了一半

• 治- 当数据仅剩下一个时即可认为是有序的

• 合- 两个有序的结果就可以合并排序

快速排序

单边循环快排（lomuto分区方案）

核心思想：每轮找到一个基准点元素，把比他小的放到他的左边， 比他大的放到他的右边

1. 选择最右元素作为基准点元素

2. j指针负责找到比基准点小的元素，一旦找到则与i进行交换

3. i指针指向大于基准点元素的左边界，也是每次交换的目标索引

4. 最后基准点与i进行交换，i即为每次交换的目标

双边循环

1. 选择最左侧元素作为基准点

2. j找比基准点小的，i找比基准点大的，一旦找到，二者进行交换（i从左向右，j从右向左）

3. 最后基准点与i交换，i即为基准点最终索引

图

图是由顶点和边组成的数据结构；有向图中边是单向的；无向图中边是双向的

度 是指与该顶点相邻的边的数量

拓扑排序

迪科斯特拉 单源最短路径算法

Floyd Warshall 多源最短路径算法

贪心算法

每一次都选取当前最优解 向前看别回头

Huffman编码

动态规划（dp）

• 从已知子问题的解，推导出当前问题的解

• 推导过程可以表达成一个数学公式

• 用一维或二维数组来保存之前的计算结果