2021-01-02

数据结构

线性表

1、数组

1.1 概念
一种线性表数据结构，使用一组连续的内存空间，来存储一组具有相同类型的数据。

1.2 特点
(1) 随机访问
根据数组首地址，被访问元素的下标和数据类型的长度，可以高效地访问到特定的元素，时间复杂度为 O(1)。
(2) 插入
元素有序：在数组中间插入和删除时可能涉及多个元素的数据搬运。
元素无序：插入时将指定位置的已有元素移到数组尾部，再将新元素插入指定位置以提升效率。
(3) 删除
删除元素时为了保证数组中数据的连续性，不可避免地要进行数据搬运（删除最后一个元素这种情况除外）。可以每次先记录下要删除的数据，在数据没有更多空间时，再进行真正的删除操作，减少大量数据搬运的次数。

1.3 思考：数组下标为何从 0 开始？
当下标从 0 开始时，寻址公式伪代码为 a[i]_address = base_address + i * data_type_size
当下标从 1 开始时，寻址公式伪代码为 a[i]_address = base_address + (i-1) * data_type_size
对比后可以看出，当下标不为 0 时，每次随机访问，都需要额外做一次减法操作，为了将效率优化到极致，数组采取了下标从 0 开始的做法。

2、链表

2.1 概念
一种线性表数据结构，通过“指针”将一组零散的内存块（节点）串联起来使用。

2.2 特点
(1) 随机访问
非连续存储，需要依次遍历，时间复杂度为 O(n)。
(2) 插入和删除
只需改变相邻节点的指针，时间复杂度为 O(1)。

2.3 分类
(1) 单链表
每个节点存储数据，同时记录下一个节点的地址。
头节点记录链表的基地址，尾节点指向 NULL。
(2) 循环链表
在单链表的基础上，尾节点指针指向头节点。
(3) 双向链表
在单链表的基础上，每个节点额外增加一个指针，指向上一个节点。
优点在于在特定节点前插入和删除一个特定节点时，无需从头遍历来获取特定节点的上一个节点。
体现了一种“用空间换时间”的设计思想。
(4) 双向循环链表
循环链表和双向链表的结合。

2.4 链表代码编写技巧
(1) 理解指针和引用的含义
将某个变量赋值给指针，实际就是将这个变量的地址赋值给指针，指针中保存了这个变量的内存地址，通过指针就能访问到该变量。
(2) 警惕指针丢失和内存泄漏
插入节点时注意操作顺序。
删除节点时注意内存的释放。
(3) 利用“哨兵”简化实现难度
使用“哨兵”节点来统一链表插入和删除的实现代码。
使用“哨兵”减少对于边界情况的判断。
(4) 重点留意边界条件处理
(5) 举例画图，辅助思考
(6) 多写多练，练习常用链表操作

2.5 思考：如何用链表来实现LRU缓存淘汰策略（最近最少使用策略）？
(1) 维护一个有序单链表，越靠近链表尾部的节点是越早访问的。
(2) 当有一个新的数据被访问时，从链表头部开始顺序遍历链表。
(3) 如果数据之前已存在，则将其从原先的位置删除，然后插入链表的头部。
(4) 如果数据没有存在链表中，看链表是否已满：若未满，将数据插入链表头部；若已满，则将链表尾节点删除，将数据插入链表头部。

2.6 LeetCode题号
单链表反转（206）
链表中环的检测（141）
两个有序链表的合并（21）
删除链表倒数第n个节点（19）
获取链表的中间节点（876）

3、栈

3.1 概念
一种操作受限的线性表数据结构，有后进先出和先进后出的特性。

3.2 特点
(1) 数据集合只涉及一端的插入和删除操作。
(2) 后进先出，先进后出。
(3) 常用于实现涉及“最近相关性”的逻辑。

3.3 应用场景
(1) 函数调用栈
每个线程的独立内存空间，会被组织成“栈”结构，用来存储函数调用时的临时变量
(2) 表达式求值
使用两个栈，一个存储操作数，一个存储运算符。当运算符比栈顶元素优先级高时，运算符入栈；比栈顶元素优先级低或相同时，从运算符栈中取出栈顶运算符，从操作数栈中取出栈顶的两个操作数，进行计算，然后把结果压入操作数栈。
(3) 括号匹配
扫描字符串，遇到左括号入栈，遇到右括号时与栈顶元素匹配，成功配对后将栈顶元素出栈。若扫描完成后栈为空，则字符串格式合法，否则格式非法。

3.4 思考：如何实现浏览器的前进后退功能？
使用两个栈。栈 A 保存每次跳转的页面，跳转到新页面时，压入栈 A。后退时，将页面从栈 A 出栈，压入栈 B 中。前进时，将页面从栈 B 出栈，压入栈 A 中。中途跳转时，要清空栈 B 中的页面。

3.5 LeetCode题号
20、155、232、844、224、682、496

4、队列

4.1 概念
一种操作受限的线性表数据结构，有先进先出和后进后出的特性。

4.2 特点
(1) 入队时将元素插入队列尾部，出队时从队列头部读取元素。
(2) 先进先出，后进后出。

4.3 分类
(1) 循环队列
能够避免入队操作时可能触发的数据搬移，若用数组实现，会浪费一个存储空间。
队列为空的判断条件：head == tail。
队列为满的判断条件：(tail+1) % n == head。
入队时，tail = (tail+1) % n。
出队时，head = (head+1) % n。
(2) 双端队列
能够在头部和尾部进行插入和删除操作。
(3) 阻塞队列
当队列为空时，从队列头部取数据会被阻塞，直到队列中有数据才会取出数据并返回。
当队列已满时，在队列尾部插入数据会被阻塞，直到队列中有空闲位置才会插入数据并返回。
(4) 并发队列
线程安全的队列。
基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。

4.4 思考：线程池没有空闲线程时，新的任务请求线程资源，线程池该如何处理？
策略分为 2 种
(1) 非阻塞：直接拒绝任务请求。
(2) 阻塞：使用队列来保存请求，有空闲线程时，再从队列中取出请求继续处理。
对于阻塞式的策略，基于数组实现的有边界队列更加合适，当已排队的请求数量达到队列大小时，新来的请求会被拒绝，设置合理的队列大小十分关键。

5、跳表

5.1 概念
(1) 在有序链表的基础上，增加多级索引结构（只能用于有序链表）。
(2) 每 x 个节点中抽出一个节点作为上一级索引的节点，x 一般为 2，为了节省空间可以使用更大的值。
(3) 在每层索引的基础上继续向上构建索引，直到最顶层索引节点的个数到 x 为止。

5.2 特点
假设抽取规则中 x 为 2
(1) 第 k 级索引格式是第 k-1 级索引的节点个数的 1/2，第 k 级索引节点个数是 n/(2^k)。
(2) 假设索引有 k 层，最高级的索引层有 2 个节点，则 n/(2^k) = 2，每层只需要遍历 x+1 个节点，其时间复杂度为 O(logn)。
(3) 索引占用的空间大小为 n/2 + n/4 + … + 4 + 2，需要额外用接近 n 个节点的存储空间，空间复杂度为 O(n)。

5.3 动态更新
(1) 插入时，可以通过一个随机函数，来决定将当前节点插入到哪几级索引中（比如随机函数生成了值 k，那就将该节点添加到第 1 级至第 k 级这些索引中）。
(2) 删除时，不仅要删除原始链表中的节点，还要删除索引中的节点。

6、散列表

6.1 概念
又称哈希表；在数组的基础上，通过散列函数将 key 转化为数组下标，来进行数据的存储。

6.2 特点
根据 key 和散列函数计算出散列值作为数组下标，本质上还是数组，拥有数组的随机访问特性。

6.3 散列函数
(1) 散列函数设计的好坏，决定了散列表冲突的概率大小，直接决定了散列表的性能。
(2) 散列函数的设计不能太复杂，生成的值要尽可能随机且均匀分布。

6.4 装填因子
装填因子 = 填入表的元素个数 / 散列表的长度
(1) 动态更改散列表容量：当装填因子达到某个阈值时，可以进行动态扩容；小于某个阈值时，也可以进行缩容。
(2) 高效扩容：将数据转移操作穿插在插入操作中，分批完成，避免一次性的数据转移导致单次操作耗时过长。

6.5 解决散列冲突的方法
(1) 开放寻址法：如果出现散列冲突，则重新探测下一个空闲位置（线性探测、二次探测、双重散列）；有利于数据结构的序列化，适合数据量小、装填因子小的场景；相比链表法需要更多的内存空间。
(2) 链表法（工程中最常用的方式）：散列表中的每个元素对应一个链表，所有散列值相同的数据都放到同一个链表中，查找时根据散列值可以取到对应链表，再进行数据的插入、查找和删除操作即可；适合数据量大、装填因子大的场景；相比开放寻址法，有更多的优化策略（例如用红黑树代替链表）。

6.6 工业级的散列表
(1) 支持快速的查询、插入、删除操作。
(2) 内存占用合理，不能浪费过多的内存空间。
(3) 性能稳定，极端情况下性能不能退化到无法接受的程度。

树

1、普通树

1.1 概念
由 n 个有限节点组成的一个具有层次关系的集合。

1.2 特性
(1) 树中的元素称为“节点”。
(2) 节点的高度：节点到叶子节点到最长路径（边数）。
(3) 节点的深度：根节点到这个节点所经历的边的个数。
(4) 节点的层数：节点的深度+1。
(5) 树的高度：根节点的高度。

2、二叉树

2.1 概念
每个节点最多有 2 个子节点的树。

2.2 存储形式
(1) 基于指针（或引用）的链式存储。
(2) 基于数组的顺序存储（为了方便计算，根节点会存储在下标为 1 的位置）。

2.3 遍历方法
(1) 前序：当前节点 -> 左子树 -> 右子树。
(2) 中序：左子树 -> 当前节点 -> 右子树。
(3) 后序：左子树 -> 右子树 -> 当前节点。

2.4 分类
(1) 满二叉树：叶子节点全都在最底层，除了叶子节点以外，每个节点都有左右两个子节点。
(2) 完全二叉树：最后一层的叶子节点都靠左排列，且除了最后一层之外，其他层的节点个数达到最大（用数组存储时最节省空间）。
(3) 二叉搜索树：树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
(4) 平衡二叉树：二叉树中任意一个节点的左右子树的高度相差不能大于 1。
(5) 平衡二叉搜索树（AVL树）：既满足平衡二叉树的定义，又满足二叉搜索树的特点（但是很多平衡二叉搜索树其实并没有严格符合上面的定义，例如红黑树）。可以解决普通二叉搜索树在频繁插入和删除过程中，出现的时间复杂度退化的问题。

2.5 二叉搜索树
(1) 中序遍历二叉搜索树，可以输出升序的数据序列，时间复杂度是 O(n)，非常高效。
(2) 在二叉搜索树中，查找、插入、删除等很多操作的时间复杂度都跟树的高度成正比。两个极端情况的时间复杂度分别是 O(n) 和 O(logn)，分别对应二叉树退化成链表的情况和变成完全二叉树的情况。
(3) 二叉搜索树删除非叶子节点时，从该节点的左子树中找到值最大的节点，或者从该节点的右子树中找到值最小的节点，来替换当前节点，两种做法都可以。

2.6 平衡二叉搜索树
(1) 树中每个节点的平衡因子（节点左右子树的高度之差）的取值必须在 {-1, 0, 1} 之内。
(2) 通过旋转操作来维持平衡（左旋、右旋、左右旋、右左旋）。

2.7 红黑树
一种近似平衡的二叉搜索树，能够保证任何一个节点左右子树的高度差小于两倍。主要解决普通二叉搜索树在数据更新的过程中，复杂度退化的问题；避免了平衡二叉搜索树的频繁调整带来的性能问题。插入、删除、查找操作的时间复杂度都是 O(logn)。
(1) 每个节点不是红色就是黑色。
(2) 根节点是黑色的。
(3) 每个叶子节点都是黑色的，且为空节点（不存储数据）。
(4) 任何相邻的节点都不能同时为红色（红色节点是被黑色节点隔开的）。
(5) 任何节点，从该节点到达其可达所有叶子节点的路径中，都包含相同数目的黑色节点。

2.8 思考：为什么常用红黑树而不用平衡二叉搜索树？
(1) 平衡二叉搜索树是严格按照定义的，高度平衡的，所以查找效率很高。但是为了维持高度的平衡，需要存储额外的高度信息，并且每次插入和删除时都有可能对结构做调整，比较耗时。因此对于有频繁插入和删除操作的数据集合，使用平衡二叉搜索树的成本较高。
(2) 红黑树只是做到了近似平衡，并不是严格的平衡，所以在维护平衡的成本上，要比平衡二叉搜索树要低。并且红黑树的插入、删除、查找各种操作性能都比较稳定，能更好地支撑工业级的应用。

3、递归树

3.1 概念
将递归过程层层分解所得到的的树型结构就是递归树，用于分析递归算法的时间复杂度。

3.2 案例分析
(1) 分析快速排序的时间复杂度
每层分区操作所遍历的数据个数总和是 n，只要求出递归树的高度 h，时间复杂度就是 O(h * n)。
假设分区时按照一九开进行拆分，快排的结束条件是待排序的分区大小为 1（对应树中的叶子节点），从根节点 n 到叶子节点 1，最短路径中每次乘以 1/10，直到 1 为止，此时树的最小高度为 log(10)n。以此类推，最大高度为 log(10/9)n。由此可以得出，快速排序的时间复杂度为 O(n * logn)。
(2) 分析台阶走法的时间复杂度
问题：假设有 n 个台阶，每次可以跨 1 个或 2 个台阶，计算总共有多少种走法。
思路：分解到递归树中后，可以看出第k层的加法操作时间消耗是 2^(k-1)，n 个节点，最大路径为 n，最短路径为 n/2，因此时间复杂度就介于 O(2^n) 和 O(2^(n/2)) 之间。
(3) 分析排列组合的时间复杂度
问题：找出 n 个数据的所有排列顺序。
思路：确定其中 1 位数据，将问题变为求解剩下 n-1 个数据的所有排列顺序，逐步分解。时间复杂度为 O(n!)。

图

图的存储方式

邻接矩阵
顶点之间的关系使用二维数组，以矩阵形式来表示。

优点：
(1) 简单、直观，查询效率高。
(2) 方便计算，可以将许多图的运算转换成矩阵之间的运算。
缺点：
(1) 十分浪费存储空间。

邻接表
顶点之间的关系使用链表来表示。

优点：
(1) 存储方式节省空间。
缺点：
(1) 链表不方便查找操作（可以将链表替换成平衡二叉搜索树、跳表、散列表等查询效率高的数据结构）。

1、无向图

1.1 概念
由顶点和连接顶点的边构成的离散结构。

1.2 特性
(1) 图中的元素称为“顶点”。
(2) 边：图中一个顶点与其他任意顶点建立的关系。
(3) 顶点的度：跟该顶点相连接的边的条数。

2、有向图

2.1 概念
在无向图的基础上，边有方向的图。

2.2 特性
(1) 顶点的入度：表示有多少条边指向该顶点。
(2) 顶点的出度：表示有多少条边以该顶点为起点，指向其他顶点。

3、带权图

3.1 概念
边有权重的图。

堆

堆是一种抽象的数据结构，可以迅速找到一些数中的最大值或最小值，需要借助其他数据结构进行实现，常见的堆有二叉堆和斐波那契堆。

1. 二叉堆

二叉堆是堆的一种常用且简单的实现形式，但并不是最优的实现形式。

1.1 概念
二叉堆是一种特殊的二叉树。
(1) 二叉堆是一个完全二叉树。
(2) 二叉堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
(3) 每个节点的值都大于等于子树中每个节点值的堆，叫“大顶堆”，反之叫“小顶堆”。

1.2 存储形式
(1) 使用数组进行存储，因为二叉堆是完全二叉树，用数组存储时可以节省空间，且用下标就可以找到节点。
(2) 索引为i的节点的左孩子节点的索引是 2*i+1，右孩子节点的索引是 2*i+2。
(3) 索引为 i 的节点的父结点的索引是 (i-1)/2 再取整。

1.3 基本操作（默认为“大顶堆”）
(1) 取最大值
直接返回根节点即可，时间复杂度是 O(1)。
(2) 插入（从下往上进行堆的调整）
在数组末尾添加元素，让新插入的节点与父节点对比大小，如果不满足子节点小于等于父节点的大小关系，就互换两个节点，一直重复这个过程，直到父子节点满足关系为止。时间复杂度仅与树的高度有关，为 O(logn)。
(3) 删除堆顶元素（从上往下进行堆的调整）
删除堆顶元素后，将堆中最后一个元素移动到堆顶，然后从上往下判断父子节点的关系，不满足的进行互换（与较大的孩子节点进行互换），重复该过程，直到父子节点满足关系为止。这样可以保证不出现数组的“空洞”，满足完全二叉树的特性。时间复杂度仅与树的高度有关，为 O(logn)。

1.4 应用场景
(1) 优先级队列（合并有序小文件、高性能定时器）。
(2) 求 Top k 问题（维护一个大小为 k 的小顶堆，遍历数据，将满足条件的存入堆中，堆满时要删除堆顶元素）。
(3) 求中位数（先排序，再使用 2 个堆存储数据，1 个大顶堆存前面部分，1 个小顶堆存后面部分）。

1.5 思考：现有一个包含 10 亿个搜索关键词的日志文件，如何快速获取到 Top 10 最热门的搜索关键词（单机、内存仅 1 GB）？
(1) 使用哈希算法，将数据进行分片。创建 n 个空文件，将关键词计算得到哈希值，将哈希值对 n 取模，得到文件编号，最终目的是要将相同关键词存在同一个文件中。
(2) 使用散列表，依次遍历 n 个文件，记录关键词的出现个数；每次遍历完 1 个文件，都用堆存储该文件中 Top 10 的关键词。
(3) 将所有文件中的 Top 10 关键词整合，再从这其中求出 Top 10 的关键词。

并查集

并查集是一种抽象的数据结构，主要用于解决“组团”或“配对”这种类型的问题。

基本操作

1、makeSet(s)：建立新的并查集，其中包含 s 个单元素集合。
2、unionSet(x, y)：把元素 x 和元素 y 所在的集合合并；要求 x 和 y 所在的集合不相交，如果相交则不合并。
3、find(x)：找到元素 x 所在的集合的代表；该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下即可。

代码模板

class UnionFind {
public:
    UnionFind(vector<vector<char>>& grid) {
        count = 0;
        int m = grid.size();
        int n = grid[0].size();
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    parent.push_back(i * n + j);
                    ++count;
                } else {
                    parent.push_back(-1);
                }
                rank.push_back(0);
            }
        }
    }
    
    int find(int i) {
        if (parent[i] != i) {
            parent[i] = find(parent[i]);
        }
        
        return parent[i];
    }    
    
    void unite(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx != rooty) {
            if (rank[rootx] < rank[rooty]) {
                swap(rootx, rooty);
            }
            parent[rooty] = rootx;
            if (rank[rootx] == rank[rooty]) rank[rootx] {
                += 1;
            }
            --count;
        }
    }
    
    int getCount() const {
        return count;
    }
    
private:
    vector<int> parent;
    vector<int> rank;
    int count;
};