DSA cracker

作者：lurf21

基本概念

数据结构三要素

• 逻辑结构（集合、线性、树、图）
• 存储结构（顺序、链式）
• 数据运算（建立、清除、求长、判空、判满、获取、更新、插入、删除、查找、遍历）

从逻辑上可以把数据结构分为线性结构和非线性结构两大类。

渐进时间复杂度

• 本质：在规模足够大的情况下，算法的运行时间如何随着规模而增长。

• Big O notation：渐进上界，用于最坏情况的复杂度分析。

• \[ O(1)<O(\log n)<O(\sqrt{n})<O(n)<o(n\log n)<O(n^2)<O(n^3)<O(2^n)<o(n!) \]

• Big Omega：渐进下界，Big Theta：渐进紧界

空间复杂度分析方法与时间复杂度类似。

向量

扩容复杂度

• 每次扩容一倍：总复杂度：\(2N\)，均摊复杂度：\(N\)
• 每次扩固定容量 x：总复杂度：\(\frac{N^2}{2x}\)，均摊复杂度：\(\frac{N}{2x}\)

有序向量唯一化

• 低效：\(O(n^2)\)
• 高效：\(O(n)\)，利用有序性

列表

与向量的区别：向量是全局坐标地址访问，列表是局部邻域关系访问

无序列表唯一化：\(O(n^2)\)

有序列表唯一化：\(O(n)\)

栈

后进先出

应用：递归嵌套、栈式计算、逆序输出、试探回溯、DFS（进制转换、括号匹配、利用前缀/后缀表达式求值）

后缀表达式：从左往右依次将操作数入栈，遇到操作符将栈顶的两个元素计算后结果入栈。

前缀表达式：从右往左依次将操作数入栈，遇到操作符将栈顶的两个元素计算后结果入栈。

栈混洗

• 给定入栈顺序，考虑问题：出栈序列共有多少种可能；求出所有出栈序列；给出一个出栈序列，栈的容量至少为多少；确定某个序列是否可以经原序列栈混洗得到。

• 卡特兰数：\(C_n=\frac{(2n)!}{n!(n+1)!}\)

• 栈和队列的共同点：都只允许在端点处插入和删除元素

队列

先进先出

应用：离散事件模拟、二项式展开系数、BFS

循环队列

• front、rear
• \(current:i,\ previous:(i-1+N)\%N,\ next:(i+1)\%N\)
• 队满：(rear+1)%size==front
• 队空：rear==front
• 队列长度：(rear-front+size)%size
• 入队：rear=(rear+1)%size
• 出队：front=(front+1)%size

树

基本概念

• 根，父亲，祖父，孩子，兄弟（共同的父亲），堂兄弟（共同的祖父），祖先，后代

• 叶节点，内部节点，链路

• 节点数，边数（节点数减一），深度（从根到 A 经过的边数），高度（从 A 到 A 的叶子节点中所经过的边数最大值）（单节点的树高度为 0，空节点树高度为 -1），树的度数（树内各节点度数的最大值）

• \[ height(T) \ge height(v) + depth(v) \]

• 二叉树：每个节点至多有两个孩子节点的树，并且区分左右孩子节点。

• 完全二叉树：除了最后一层外，其他各层全是满的，并且最后一层的节点尽可能往左靠。第 \(i\) 层的最大节点数：\(2^i\)；n 个节点的完全二叉树的高度：\(\lfloor \log_2n \rfloor\)
• 满二叉树：所有叶子节点都处于最底层的二叉树（树中所有层都是满的）。节点总数：\(2^{h+1}-1\)，叶节点数：\(2^h\)，内部节点数：\(2^h-1\)；\(n\) 个节点的满二叉树的高度：\(h=\log_2(n+1)-1\)
• 真二叉树：每个节点的孩子数目为 0 个或 2 个
• 平衡二叉树：树中任意节点的左右子树的高度差不超过 k（通常 k 为 1）
• 森林：由若干棵树组成的集合，可理解为森林的每棵树都是兄弟

二叉树性质

• 在第 \(i(i\geq 0)\) 层至多有 $ 2^{i} $ 个节点。
• 深度为 \(k(k\geq 0)\) 的二叉树至多有 \(2^{k+1}-1\) 个节点，至少有 \(k+1\) 个节点。
• 对一棵二叉树，若度为 2 的点有 \(n_2\) 个，叶节点有 \(n_0\)，则 \(n_0=n_2+1\)。
• 树中节点数 = 总分叉数 + 1
• \(n\) 个节点的二叉树的形态数：卡特兰数（\(C_n\)）

表示方法

• 父亲表示法：记录父亲的索引。在查询节点孩子及兄弟时，效率不理想
• 孩子表示法：记录孩子的链表。在查询节点父亲及根节点时，需遍历整个表，效率不理想
• 父亲+孩子表示法：每个节点所具有的孩子数量可能差异巨大，动态增加、删除，更新和维护树的拓扑时效率低
• 长子+兄弟表示法：该转换保留了节点间的层级和兄弟关系，为一一映射每个节点仅需维护最多两个邻域: 孩子与下一兄弟。任意多叉树（有根有序）可转化为二叉树
• 顺序（向量）表示

二叉树的遍历

• BFS（层次遍历）：从根开始一层层往下，每层中从左到右
• DFS（前中后指的是根的位置）
  • 前序遍历（根左右）：绕着树的外围跑一圈
  • 中序遍历（左根右）：顺次掉落
  • 后序遍历（左右根）：从左到右剪葡萄

二叉树重构

• 前序/后序+中序可重构：定位 root 可重构树根，并区分左右子树，进而区分左子树和右子树根，递归直至整棵树的重构
• 前序+后序不可以重构，若树的每个节点都有偶数(0 或 2)个孩子，则可重构
• 前序序列固定，有卡特兰数种可能的中序序列，等效于给定 \(n\) 个节点的二叉树形态数

哈夫曼树（最优编码树）

• 带权路径长度（WPL）
  • 节点：节点路径长度与节点权重之积
  • 树：所有叶子节点的带权路径长度之和
• 对于给定一组具有确定权值的叶结点，可以构造出不同的二叉树，其中，WPL 最小的二叉树称为哈夫曼树
• 构造方法：排序和合并两种操作循环
• \(k\) 个叶子节点的哈夫曼树，节点总数为 \(n=n_0+n_1+n_2=n_0+n_2=k+(k-1)=2k-1\)。由此易得 \(n\) 个节点的哈夫曼苏有 \(\frac{n+1}{2}\) 个叶子节点
• 哈夫曼编码
  • 定长编码解码无歧义，变长编码解码有歧义
  • 前缀无歧义编码：利用前缀二叉树，任何字符编码都不是其他字符的前缀
  • 前缀二叉树：字符为二叉树叶子节点，左孩子路径标注 1，右孩子路径标注 0，解码时逐个扫描比特沿二叉树路径到达叶子节点解码。

二叉搜索树

• 二叉搜索树是一种二叉树的树形数据结构，其定义如下：

  1. 空树是二叉搜索树。
  2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于等于其根节点的值。
  3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于等于其根节点的值。
  4. 二叉搜索树的左右子树均为二叉搜索树。

• 对一棵二叉搜索树进行中序遍历，可以按从小到大的顺序，将各结点关键码排列起来，所以也称二叉排序树

• 任意一棵二叉树是二叉搜索树，当且仅当其中序遍历序列单调非降

• 搜索：从根结点开始，逐层向下比较判断（递归或迭代均可），若当前节点为空，返回 NULL；若当前节点大于目标关键码，继续搜索右子树；若当前节点小于目标关键码，继续搜索左子树；否则表示命中，返回该节点地址。本质是剪枝的思想。

• 插入：插入新元素前须搜索该元素是否已存在，若是则不再插入；若搜索不成功，把新节点加到搜索停止的地方。新元素的插入总是作为叶子节点插入。插入总能保证二叉搜索树特性。

• 删除：删除节点后要保持二叉搜索树特性难

  • 被删节点位于叶子，只需将其父节点指向它的指针清零，再释放它即可
  • 被删节点左子树为空，用被删节点右子树顶替，再释放它即可
  • 被删节点右子树为空，用被删节点左子树顶替，再释放它即可
  • 被删除节点左右子树都不为空，以在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删节点中，再递归处理该节点的删除

• \(n\) 个不同节点最多构建卡特兰数种不同的二叉搜索树

• 树高与性能

  • 二叉搜索树的搜索（查找）、插入、删除复杂度皆为 \(O(h)\)
  • 最好情况：按照完全二叉树的层次遍历输入时，树高 \(h=\lfloor \log n\rfloor\)
  • 最坏情况：按关键码大小顺序输入构建二叉搜索树时，树高 \(h=n\)
  • 随机生成：二叉搜索树平均高度 \(\Theta(\log n)\)
  • 随机组成：二叉搜索树平均高度 \(\Theta(\sqrt{n})\)

• 两棵二叉搜索树的中序遍历序列相同，则称它们彼此等价

• 局部调整：使二叉搜索树在动态增减过程中保持适度平衡（调整为等价的平衡二叉搜索树）。“矮胖”的身材更好。zig，zag，zagzig，zigzag，上下可变，左右不乱。

• 平衡二叉搜索树

  • 每个节点左子树和右子树高度差至多等于 1

  • 平衡因子：左右子树高度差 \(balFac(v)=height(lc(v))-height(rc(v))\)

• AVL 树

  • 平衡因子受限的二叉搜索树（各节点 balFac 绝对值不超过 1）
  • 适度平衡：规模为 n 的 AVL 树，\(height(AVL)=O(\log n)\)，在高度给定的情况下，节点规模 \(n = \Omega(2^{height(AVL)})\)
  • 失衡与重平衡：在每插入一个节点或删除一个节点时，检查平衡性，找到插入删除导致的最小失衡子树，并进行局部调整保持平衡

高级搜索树

• 伸展树

• B 树

  • 所有叶节点深度相同，如果根节点不是叶子节点，那么它至少有两个子节点

  • 除叶子节点外，节点的度数比关键码个数多 1

  • 节点分支数允许范围：\(\left[\lceil\frac{m}{2}\rceil,m\right]\)

  • 每个非根节点的关键码个数：\(\left[\lceil\frac{m}{2}\rceil-1,m-1\right]\)

  • 下层与上层分支数之差等于本层关键码数

  • 树高（\(N\) 为关键码总数）\(\log_m(N+1)\leq h\leq \log_{\lceil\frac{m}{2}\rceil}\lfloor\frac{N+1}{2}\rfloor+1\)

• 红黑树

• \(k-\mathrm{d}\) 树

  • 目的：范围查询，进行高维几何搜索
  • 核心思想：每次选取一个维度进行划分。每次切分都在中位点（对应坐标居中点），保证全树不高于 \(O(\log n)\)
  • 查询：递归+剪枝
  • 构建时间复杂度：\(O(n\log n)\)

堆

堆（二叉堆）

• 以数组（向量）为存储结构；以完全二叉树为逻辑结构
• 每个顶点的值大于或等于其左右孩子的值：大顶堆
• 每个顶点的值小于或等于其左右孩子的值：小顶堆

优先级队列

• 不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素
• 以二叉堆实现可以得到最优的效率
  • insert()：堆上滤，\(O(\log n)\)
  • getMax()：取堆顶，\(O(1)\)
  • delMax：删除堆顶，置换 -下滤，\(O(\log n)\)
• 优先级队列默认采用大顶堆，根节点为极大值点。
• 插入：上滤。直接在向量末尾插入，若新节点大于其父节点，与父节点值进行互换，其它节点不受影响。迭代此过程，直到满足堆序性要求。实际可缓存新插入节点值，上滤改变每个需要调整节点值，最后用新值取代终止节点值。Parent(i) = (i - 1) >> 1
• 删除：置换+下滤。使用最后一个元素取代根节点值，把原堆顶置于向量最末。比较新根节点的两个孩子，与其大的孩子交换迭代该过程，直至全树满足堆序性要求。lc(i) = (i >> 1) + 1，rc(i) = (i >> 1) + 2
• 构建：堆合并（Floyd 算法）\(O(n)\)
• 堆排序：\(O(n\log n)\)

图

基本概念

• 简单路径：经过的点互相不重复的路径。
• 连通分量：无向图中，若 \(v_i\) 到 \(v_j\) 有路径，则称 \(v_i\) 和 \(v_j\) 是连通的，无向图极大连通子图的集合为连通分量。
• 强连通分量：有向图中，若从 \(v_i\) 到 \(v_j\) 以及从 \(v_j\) 到 \(v_i\) 有路径，则称 \(v_i\) 和 \(v_j\) 是连通的，有向图极大强连通子图的集合为强连通分量。

\(n\) 节点的连通无向图至少有 \(n−1\) 条边（邻接矩阵有 \(2(n−1)\) 个元素），连通有向图至少有 \(n\) 条边。

要保证在任意连接方式下都能连通 \(n\) 个点，至少需要 \(\frac{n(n−1)}{2}+1\) 条边。

\(Topological\ Sorting\)

• 从有向无环图中寻找拓扑序列
• 步骤
  • 选择一个无前驱的结点并输出
  • 从图中删除该结点以及以它为起始点的边
  • 重复上述两步直至剩余的图中不再存在没有前驱的结点
  • 如果还有顶点却没有入度为 0 的顶点，说明有向图有环存在

Prim 算法

• \(O(n^2)\)
• 最小生成树（最小支撑树）
• 最小生成树不唯一，最小生成树代价（树的所有链路权值之和）唯一
• 不断从剩下的边中选一条与当前树中某点距离最短的加入到树中

Kruskal 算法

• \(O(m+p\log m)\)，其中 p 为迭代次数
• 适合稀疏图
• 不断向 T 中添加当前的最短边，如果形成了回路，那么它一定是这个回路的最长边，删掉它，直到达到 \(n-1\) 条边

Dijkstra 算法

• \(O(n^2)\)
• 权值非负单源最短路径问题
• 最短路径树
• 在遍历的过程中不断记录和更新当前到每个点的最短路长度和前驱，并加 flag 防止二次访问，即把已确定的点统一放到一个集合里

Bellman-Ford 算法

• \(O(mn)\)
• 边权为任意实数，无负回路
• 按顺序每次更新都遍历所有点，取当前值与前驱加边权中最小的，直到所有点无变化

Floyd-Warshall 算法

• \(O(n^3)\)
• 任意两点
• 直接暴力三层循环，对权矩阵中所有点，\(if\ d_{ik}+d_{kj}<d_{ij},d_{ij}=d_{ik}+d_{kj}\)

散列

设计准则

• 确定性
• 快速可计算性
• 高空间利用率（装填因子）
• 随机性（均匀性），关键码映射到各桶的概率尽可能为 \(\frac{1}{M}\), 最大限度地避免冲突

散列函数

• 除余法：\(hash =f(key)=key \% M\)，\(M\) 为散列表表长，一般取质数以减小散列冲突
• MAD 法(multiply-add-divide method)：相邻关键码在除余法中依然相邻，连续性导致局部聚集，采用 MAD 法可克服原有方法连续性问题。\(hash=f(key)=(a × key +b) \% M\)
• 数字分析法：抽取关键码的若干位作为散列函数，适用于关键码位数比较多，并且事先知道关键码若干位分布比较均匀的情况
• 平方取中法：适用于关键码位数不大，但不明分布的情况
• 折叠法：将关键码从左至右分为位数相等的几部分，然后将几部分叠加求和，并按照散列表表长取后几位作为地址，适用于关键码位数较大，但不明分布的情况
• 伪随机数法：\(hash=f(key)=rand(key) \% M\)，当关键码长度不等时，采用该方法比较合适

散列冲突排解

• 多槽位法：将各桶分解为更细小的槽位单元(slot)，每一槽位可组织成向量
• 独立链法：将各桶相互冲突的词条串成一个列表
• 公共溢出区法：在原散列表之外另设一词典结构作为公共溢出区，适合冲突数据很少的情况
• 线性试探法：冲突后往后依次试探，查询时逐个按顺序查询
• 平方试探法：可尽快跳离聚集区域的试探
• 双向平方试探方法：平方试探无法遍历散列表所有空桶（即使表长为素数）

串

串匹配

• BF 算法：\(O(mn)\)
• KMP 算法
  • \(O(m+n)\)
  • next 数组：找真前缀和真后缀的交集中最长的长度
  • 改进 next 数组：第 i 位字符若与其 next 数组值索引对应的字符相等，则换 next 值为该位的 next 值，否则直接是原来的 next 值。

排序

名称	平均复杂度	最好复杂度	最差复杂度	空间复杂度	稳定性
冒泡排序	\(O(n^2)\)	\(O(n)\)	\(O(n^2)\)	\(O(1)\)	稳定
选择排序	\(O(n^2)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	不稳定
插入排序	\(O(n^2)\)	\(O(n)\)	\(O(n^2)\)	\(O(1)\)	稳定
希尔排序	\(O(nlog^2n)\)~\(O(n^2)\)	\(O(n^{1.3})\)	\(O(n^2)\)	\(O(1)\)	不稳定
堆排序	\(O(nlogn)\)	\(O(nlogn)\)	\(O(nlogn)\)	\(O(1)\)	不稳定
归并排序	\(O(nlogn)\)	\(O(nlogn)\)	\(O(nlogn)\)	\(O(n)\)	稳定
快速排序	\(O(nlogn)\)	\(O(nlogn)\)	\(O(n^2)\)	\(O(nlogn)\)~\(O(n^2)\)	不稳定
基数排序	\(O(nk)\)	\(O(nk)\)	\(O(nk)\)	\(O(n+k)\)	稳定

排序算法的稳定性：如果在元素序列中有两个元素 r[i] 和 r[j], 它们的排序码 k[i] == k[j] , 且在排序之前, 元素 r[i] 排在 r[j] 前面。如果在排序之后, 元素 r[i] 仍在元素 r[j] 的前面, 则称这个排序方法是稳定的, 否则称这个排序方法是不稳定的

不稳定的排序算法：快些（希）选堆

STL采用的排序算法为快速排序算法

从指标上看，快速排序在与堆排序、归并排序的比较中性能并不占优势，为何快速排序实际中更快？

• 堆排序每次取一个最大值和堆底部的数据交换，重新筛选堆，把堆顶调整到位，有很大可能是依旧调整到堆的底部，然后再次和堆顶最大值交换，再调整下来，堆排序做了许多无用
• 快速排序每下一次寻址都是紧挨当前地址的，而堆排序的下一次寻址和当前地址的距离比较长

k-select

• 任一组可比大小的元素中，找到其中从小到大次序为 k 者
• 中位数：\(k=\lfloor\frac{n}{2}\rfloor\) 时的 k 选取问题
• 中位数应用：分治策略，如 k-dTree 中的空间划分
• \(O(n)\) （基于快速划分）

冒泡排序

• 重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来，大小一样不交换

• 经过 \(i\) 次扫描后，数列的末尾 \(i\) 项必然是最大的 \(i\) 项，因此冒泡排序最多需要扫描 \(n-1\) 遍数组就能完成排序

    void bubbleSort(vector<int> &a) {
        int len = a.size();
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    swap(a[j], a[j + 1]);
                }
            }
        }
    }

选择排序

• 每一次从待排序的元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完

    void selectionSort(vector<int> &a) {
        int len = a.size();
        for (int i = 0, minIndex; i < len - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < len; j++) {
                if (a[j] < a[minIndex])
                    minIndex = j;
            }
            swap(a[i], a[minIndex]);
        }
    }

插入排序

• 每步将一个待排序的元素，按其大小插入已排序序列的适当位置上，直到全部插入完为止

    void insertSort(int arr[], int len) {
        for (int i = 1; i < len; ++i) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

希尔排序

• 在粗尺度进行排序可更有效地减少的逆序对

• 取 gap < n 作为间隔，将 n 个元素等距离分为 gap 组；然后逐渐缩小 gap，直到 gap=1。gap 大时组中元素少，排序速度快；gap 变小，组中元素多，但大多数已经基本有序，所以排序速度依然快

    void shellSort(vector<int> &a) {
        int len = a.size();
        for (int gap = len / 2; gap > 0; gap /= 2) {
            for (int i = 0; i < gap; i++) {
                for (int j = i + gap, temp, preIndex; j < len; j = j + gap) {
                    temp = a[j];
                    preIndex = j - gap;
                    while (preIndex >= 0 && a[preIndex]>temp) {
                            a[preIndex + gap] = a[preIndex];
                            preIndex -= gap;
                    }
                    a[preIndex + gap] = temp;
                }
            }
        }
    }

堆排序

• 把无序数列构建成二叉堆
• 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶

归并排序

• 采用分治递归策略，递归融合两路已排序子序列

• 共要 merge \(\log n\) 次，每次调用复杂度为 \(O(n)\) 的 mergeSort，故时间复杂度为 \(n\log n\)

• \[ \left\{ \begin{array}{lr} T(n)=2\times T(\frac{n}{2})+O(n)\\ T(1)=1 \end{array} \right. \Rightarrow T(n)=O(n\log n) \]

    void merge(int data[], int first, int mid, int last, int sorted[]){
        int i = first, j = mid;
        int k = 0;
        while (i < mid && j < last)
            if (data[i] < data[j])                 // 归并
                sorted[k++] = data[i++];
            else
                sorted[k++] = data[j++];
        while (i < mid) sorted[k++] = data[i++];   // 拷贝两个子序列中的剩余元素
        while (j < last) sorted[k++] = data[j++];
        for (int v = 0; v < k; v++) 
            data[first + v] = sorted[v];       // 将排序后结果覆盖原数组
    }
    void mergeSort(int data[], int first, int last, int sorted[]){
        if (first + 1 < last){
            int mid = (first + last) / 2;
            mergeSort(data, first, mid, sorted);
            mergeSort(data, mid, last, sorted);
            merge(data, first, mid, last, sorted);
        }
    }

快速排序

    int partition(vector<int> &a, int left, int right) {
        int pivot = a[right];
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (a[j] <= pivot) {
                i++;
                swap(a[i], a[j]);
            }
        }
        swap(a[i + 1], a[right]);
        return i + 1;
    }

    void quickSort(vector<int> &a, int left, int right) {
        if (left < right) {
            int mid = partition(a, left, right);
            quickSort(a, left, mid - 1);
            quickSort(a, mid + 1, right);
        }
    }

    void qSort(vector<int> &a) {
        quickSort(a, 0, a.size() - 1);
    }

基数排序

    void radixSort(vector<int> &a) {
        int len = a.size();
        if (len < 2)
            return;
        int Max = a[0];
        for (int i = 1; i < len; i++) {
            Max = max(Max, a[i]);
        }
        int maxDigit = log10(Max) + 1;
        int mod = 10, div = 1;
        vector<int> bucketList[10];
        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            for (int j = 0; j < len; j++) {
                int num = (a[j] % mod) / div;
                bucketList[num].push_back(a[j]);
            }
            int index = 0;
            for (int j = 0; j < 10; j++) {
                int tlen=bucketList[j].size();
                for (int k = 0; k < tlen; k++)
                    a[index++] = bucketList[j][k];
                bucketList[j].clear();
            }
        }
    }

查找/搜索

顺序查找

二分查找

• 折半查找

• 二叉树查找

    int binarySearch(int[] nums, int target) {
        int left = 0; 
        int right = nums.length - 1;
        while(left <= right) {
            int mid = (right + left) / 2;
            if(nums[mid] == target)
                return mid; 
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            }
        return -1;
    }

分块查找

哈希查找

注意事项

• 无序和有序向量的区别
• 区分有向图和无向图

本站总访问量次

评论