数据结构与算法

算法分析

算法分析关心的，一是解决问题时要占用的空间；二是算法执行所需的时间。

当问题规模为 n 时，解决问题所需的时间是 T(n)。数量级描述的是，当 n 增长时，T(n) 增长最快的部分，常被称作大 O 记法，记作 O(T(n))。算法的性能有时不仅依赖于问题规模，还依赖于数据值。要用最坏情况、最好情况、普通情况来描述性能，以免被某个特例误导。

字母异位词的四种解法：给定两个字符串 s 和 t，判断 t 是否是 s 的字母异位词。

1. 暴力穷举法：用 s 中的字符生成所有的可能，看是否跟 t 匹配，复杂度为 n!，当 n=20 时，有 2432902008176640000 种排列，这是一个比 2^n 还要快得多的增长！！
2. 双层循环：s 的字符逐个与 t 比较，复杂度为 O(n^2)。
3. 排序法：s 和 t 分别排序，再逐个比较。复杂度为 O(nlogn)。
4. 计数法：两个异序词必有相同数目的 a,b,c,... 使用计数器统计每个字符出现的次数，复杂度为 O(n)。

排序

归并排序：将列表一分为二，排序左半边，再排序右半边，最后合并，递归进行。

快速排序：与归并排序的等分操作不同，先选取基准值并分区，对左半区、右半区递归排序。

排序算法的稳定性是指在排序过程中，具有相等键值的元素之间的相对顺序在排序前后是否保持不变。稳定性的其中一个重要意义是保持多重排序的结果。如果数据集根据一个属性已经排序，你可能想根据第二个属性重新排序，同时保持第一个属性的排序结果。

二叉堆、优先队列

优先队列是一种特殊的队列数据结构，其中每个元素都有一个优先级。元素的添加和移除是基于优先级进行的，通常情况下，优先级最高的元素会最先被移除。

它的一个经典实现是二叉堆（通常我们直接用“堆”来代替“二叉堆”），二叉堆使用数组存储元素，并可以以时间复杂度 O(logN) 实现这两个操作。

作为对比，我们考虑除了堆以外的优先队列的实现，可以看到，无论下面哪种实现，都只能保证其中一个操作是 O(1)、另一个操作是 O(N)。

实现方式	插入	移除当前最大元素
无序数组	O(1)，插入到数组末尾	O(N) 遍历找到最大元素、与数组末尾元素交换，删除并返回（选择排序的思想）
有序数组	O(logN) 二分查找合适的位置将元素插入、O(N) 将其后的元素全部后移一个位置，保持数组有序（插入排序的思想）	O(1) 删除末尾元素并返回
无序链表	O(1) 插入到链表头部	O(N) 找到最大元素并删除
有序链表	O(N) 找到合适位置并插入，保持链表有序（头部最大）	O(1) 删除链表头部

定义：一个二叉树是堆有序的，当它每个节点的值都大于（小于）等于它左右子节点的值。

定义：一个二叉堆按照“堆有序的”“完全二叉树”来组织它的节点，并将节点以层序放到数组里（但不使用数组的第一个元素）。

堆的特性：nums[k] 的父节点位于 nums[k/2]；nums[k] 的左右子节点分别是 nums[2k], nums[2k+1]。

为了实现优先队列的两个操作，需要先学习堆的 reheapifying，即，当堆的某些节点违反条件时，我们调整堆使它重新变得有序。

如果一个子节点比父节点大，那么它违反了堆顺序，我们需要将它向上与父节点交换、直到找到比它大的父节点或到达根节点，感官上看这个节点在向上浮，因此这个操作称为 swim。

void swim(int k) {
    while (k > 1 && nums[k/2] < nums[k]) {
        std::swap(nums[k/2], nums[k]);
        k = k / 2;
    }
}

如果一个父节点比任意一个子节点小，那么它违反了堆顺序，我们将它与子节点中较大的一个交换、直到两个子节点都比它小或到达叶子节点，感官上看这个节点在向下沉，因此这个操作称为 sink。

void sink(int k) {
    while (2*k <= N) {
        int j = 2 * k;
        if (j < N) {
            j = nums[j] > nums[j+1] ? j : j+1;
        }
        if (nums[k] < nums[j]) {
            std::swap(nums[k], nums[j]);
            k = j;
        }
    }
}

有了 swim 和 sink，实现优先队列的两个操作变得特别简单！

• insert 就是在数组末尾增加新元素，然后将新元素上浮到合适的位置；
• delMax 就是将堆顶元素移除，将数组末尾的元素放到堆顶，再将它下沉到合适的位置。

void insert(int v) {
    ++N; // 新的数组大小
    nums[N] = v;
    swim(N);
}

int delMax() {
    int m = nums[1];
    std::swap(nums[1], nums[N]);
    nums[N] = -1; // 数组末尾元素置为一个非法值
    --N; // 新的数组大小
    sink(1);
    return m;
}

二叉堆主要应用有两个，一是排序方法「堆排序」，二是一种很有用的数据结构「优先级队列」。

堆排序

一种重要的排序算法，堆排序，分为两步，第一步将数组原地构建成堆；第二步排序。

构建堆有两种可能的方案。第一种我们从左往右扫描，将每个元素 swim 到合适的位置，使得当前扫描指针的左边总是堆有序的。还有另一种更聪明的方案，因为数组的每一个位置都可以看作是一个子堆的根节点，所以我们可以从右往左扫描、对每个节点调用 sink，就可以构建以该节点为根的有序子堆。巧妙的是，从数组的中间位置往右，都是大小为 1 的子堆，可以直接跳过，因此我们从数组的中间位置开始向左遍历即可！

排序时，从右往左遍历，每次将当前元素与堆顶元素（它最大）交换，然后将堆顶元素下沉。

void sort(vector<int> &nums) {
    // 1. 构造堆
    int N = nums.size();
    for (int i = N/2; i >= 1; --i) {
        sink(nums, i, N);
    }
    // 2. 排序
    while (N > 1) {
        std::swap(nums[1], nums[N]);
        --N;
        sink(nums, 1, N);
    }
}

快速排序在平均情况下通常比堆排序快，因为它的分区操作在很多情况下能够更好地利用缓存，且实际的操作次数可能更少。快速排序在最坏情况下的性能（O(n^2)）远不如堆排序稳定，但这可以通过选择一个好的枢轴（如随机枢轴或三数中值分割法）来缓解。

• 如果你需要稳定的性能（即避免最坏情况的时间复杂度），如实时系统，堆排序可能是更好的选择。
• 如果你追求平均情况下的性能，并且可以接受偶尔出现的性能下降，快速排序通常是首选。

哈希表

现代 JVM 中，Object.hashCode() 的默认实现不是直接返回对象的内存地址。JVM 的垃圾回收机制在进行压缩时，会移动对象在内存中的位置。如果 hashCode 是实时的内存地址，对象移动后 hashCode 就变了，这违反了 Java 规范（hashCode 在对象生命周期内必须保持不变）。JVM 通常会在对象创建时，生成一个随机数或自增 ID 存入对象头中。Object.hashCode() 实际上返回的是这个存放在对象头里的 ID。

为了将这个巨大的整数映射到哈希表底层有限的数组（假设长度为 n）索引上，主要分为以下步骤：

1. 扰动函数 (Hash Disturbance)。Java HashMap 会对 hashCode 进行一次 “扰动” 处理，将高 16 位和低 16 位进行异或（XOR）运算，目的是混合哈希值的高位和低位，让高位的信息也能影响最终的索引结果，从而减少冲突，hash=hashCode⊕(hashCode>>16)
2. 取模运算 (Modulo Operation)，将大整数转为数组索引，我们需要把这个大的 hash 值映射到数组的长度范围内 [0, length-1]。通常的数学做法是取模，但取模运算相对较慢。为了提高效率，HashMap 强制要求底层数组的长度必须是 2 的整数次幂。当 length 是 2 的幂时，以下等式成立：hash%length==hash&(length−1)

树

• 定义一：树由节点及连接节点的边构成。树有以下属性：有一个根节点；除根节点外，其余节点都与唯一的父节点相连；从根节点到其它每个节点有且仅有一条路径。
• 定义二：一棵树要么为空，要么由一个根节点和零或多颗子树构成。每棵子树的根节点通过一条边连接到父树的根节点。

二叉树

对于一棵树，如果每个节点最多有两个子节点，我们就称这样的树是二叉树。

在一棵树中，根节点的深度为 0，每向下一层，深度就增加 1。因此，树的总深度等于其所有叶子节点中深度最大的值。

满二叉树：Full Binary Tree is a Binary Tree in which every node has 0 or 2 children.

完全二叉树：Complete Binary Tree has all levels completely filled with nodes except the last level and in the last level, all the nodes are as left side as possible.

完美二叉树：Perfect Binary Tree is a Binary Tree in which all internal nodes have 2 children and all the leaf nodes are at the same depth or same level.

平衡二叉树：Balanced Binary Tree is a Binary tree in which height of the left and the right sub-trees of every node may differ by at most 1.

退化二叉树（链表）：Degenerate Binary Tree is a Binary Tree where every parent node has only one child node.

二叉搜索树 (BST)

二叉搜索树：指一棵空树或者具有下列性质的二叉树

1. 若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不为空，则右子树上所有节点的值均大于或等于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；

既有链表高效插入的特性，又有有序数组二分查找的特性，但最坏情况下退化成链表。

• 平衡的 BST 确保了树的高度尽可能低，从而减少在搜索过程中需要比较的节点数。对搜索、找最小或最大元素、前驱后继查找、范围查询等操作能够提供对数时间复杂度的性能。
• 如果 BST 不平衡，它可能会退化成一个链表结构，特别是在连续插入有序数据时。在这种情况下，树的高度与节点数相同，导致所有操作的时间复杂度退化为 O(n)。

红黑树

AVL tree:

• named after inventors Adelson-Velsky and Landis
• self-balancing binary search tree
• 它通过严格的平衡条件确保树的高度始终保持在 O(log n)，从而保证插入、删除和查找操作的时间复杂度为 O(log n)
• 插入、删除的维护成本比红黑树高，适合读多写少的场景

红黑树：

• 红黑树是一种近似平衡的二叉搜索树，它通过确保从根到叶子的所有路径上不会有两个连续的红节点来弱化平衡条件。
• 红黑树的平衡操作相对简单，任何不平衡都会在三次旋转之内解决，通常只需要一次或两次旋转。
• 红黑树在插入和删除操作上比 AVL 树更高效，因为它不需要严格的平衡，但查找操作可能比 AVL 树慢，因为它允许更大的高度差。
• 红黑树的所有操作在最坏的情况下都可以在 O(log n) 完成。

// 定义节点颜色的枚举
enum Color { RED, BLACK };

// 红黑树的节点结构
template <typename T>
struct RBTreeNode {
    T value;                 // 节点存储的值
    Color color;             // 节点的颜色
    RBTreeNode *left;        // 指向左子节点的指针
    RBTreeNode *right;       // 指向右子节点的指针
    RBTreeNode *parent;      // 指向父节点的指针

    // 构造函数
    RBTreeNode(T val) : value(val), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

红黑树如何保持弱平衡（黑色完美平衡）：

• 红黑树的每个节点都有一个颜色属性，红色或黑色。颜色本身并不代表节点的具体特性，而是作为维护树结构平衡的一种标记。
• 红黑树的任意一个节点到叶子节点的所有路径上的黑色节点数量必须相同。这个性质被称为“黑色完美平衡”。通过这个性质，红黑树保证了最长路径不会超过最短路径的两倍，避免了最坏情况下的线性时间操作。
• 如果没有红色节点，每次插入或删除操作都可能需要大量的节点旋转来维持树的平衡，因为每次变动都必须严格遵守黑色节点的平衡规则。
• 红色节点的引入减少了必要的旋转次数，因为它们允许在局部区域暂时违反黑色完美平衡的性质。这种违反可以在后续的操作中通过颜色变化和少量的旋转来修正。

图

图是用来建模具有多对多关系的实体集合的一种非常强大的工具。

图由节点和连接这些节点的边组成。图可以是有向的（箭头指向一个方向）或无向的（没有箭头，表示双向关系），并且可以包含环（一个节点通过边与自身连接）和/或并行边（两个节点之间有多条边）。

图在解决实际应用中的许多问题方面都非常有用，包括但不限于：社交网络、网络拓扑、地图和导航、项目管理（PERT 或甘特图）、知识图谱。

图论的算法，如最短路径、连通性检测、网络流分析等，都是为了解决这些领域中的具体问题。

有两种非常著名的图的抽象数据类型：邻接矩阵和邻接表。

如果用顶点组成二维数组，某两个顶点之间有边的地方标记为 1，没有边的地方标记为 0，这种表示图的方法就称为邻接矩阵法。

显然，无向图对应的矩阵是一个以主对角线为对称轴，各元素对应相等的矩阵。

与无向图不同的是，因为有向图的方向性，在这个有向图中，B 到 A 之间有一条有向边，但 A 到 B 之间却没有边。

如果边之间带了权值，那么图 1 和图 2 的表格中的 1（能到达）就可以用权值来代替，而 0（不能到达）就用 ∞ 代替（这里注意，因为权值有可能是 0，所以不能到达改用 ∞ 表示）。

邻接矩阵的优点是简单，缺点是它应用在大部分现实问题时都是很“稀疏”的，浪费大量存储空间。只有当图中的每一个点与其他的所有点都连接时，邻接矩阵才会被填满。

邻接表将顶点用一个一维数组存储，图中每个顶点 Vi 的所有邻接点构成一个链表，由于邻接点的个数不确定，所以我们选择用单链表来存储。

有向图的邻接表结构也是类似的，以下是“把顶点当弧尾”建立的邻接表，这样很容易就可以得到每个顶点的出度。

• 弧（Arc）：就是这条有向边本身。
• 弧尾（Tail）：是箭的尾部，在逻辑上，它代表起点。
• 弧头（Head）：是箭的头部，也就是箭头指向的地方，在逻辑上，它代表终点。

如何高效刷题

建议的刷题顺序是：

数组、链表

先学习像数组、链表这种基本数据结构的常用算法。这些小而美的算法经常让你大呼精妙，能够有效培养你对算法的兴趣。

• 链表常考的技巧就是双指针
• 二分搜索可以看作两端向中心的双指针
• 所有 "nSum" 问题都可以先排序、然后双指针快速计算结果
• 滑动窗口，典型的快慢双指针，快慢指针中间就是滑动的“窗口”，主要用于解决子串问题
• 回文串，使用双指针从两端向中心检查
• 前缀和技巧，维护一个 preSum 数组，避免每次都对子数组遍历
• 差分数组技巧，维护一个 diff 数组，避免每次都对子数组进行增减操作

二叉树

学会基础算法之后，应该先刷二叉树。二叉树解题的思维模式分两类，

1. 是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。
2. 是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。

这两类思路分别对应着回溯算法核心框架和动态规划核心框架。不少二叉树的题目是可以同时使用这两种思路来求解的。例如前中后序遍历问题可以用遍历、也可以用分解（但一般我们用遍历）。

回溯算法用于解决排列/组合/子集问题。DFS 算法是在遍历「节点」，回溯算法是在遍历「树枝」。解决一个回溯问题，实际上就是一个决策树的遍历过程，你只需要思考 3 个问题：

1. 路径：也就是已经做出的选择。
2. 选择列表：也就是你当前可以做的选择。
3. 结束条件：也就是到达决策树底层，无法再做选择的条件。

动态规划问题的一般形式就是求最值，重叠子问题、最优子结构、状态转移方程就是动态规划三要素。

• 子序列问题：最长递增子序列、最大子数组、最长公共子序列、编辑距离
• 背包问题
• 股票买卖问题，我们发现了三个状态，使用了一个三维数组。
• 打家劫舍系列总共有三道，难度设计非常合理，层层递进。第一道是比较标准的动态规划问题，而第二道融入了环形数组的条件，第三道更绝，把动态规划的自底向上和自顶向下解法和二叉树结合起来
• 贪心算法

无论使用哪种思维模式，你都需要思考：如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。二叉树的所有问题，就是让你在前中后序位置注入巧妙的代码逻辑。

快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后序遍历。

• 先构造分界点，然后去左右子数组构造分界点，你看这不就是一个二叉树的前序遍历吗？
• 先对左右子数组排序，然后合并，你看这是不是二叉树的后序遍历框架？

甚至可以说，只要涉及递归，都可以抽象成二叉树的问题。递归是解决问题的一种方法，它将问题不断地分解成更小的子问题，直到子问题可以用普通的方法解决。递归会使用一个不断调用自己的函数。递归三原则：1. 退出条件；2. 不断向退出条件靠近；3. 递归调用自己。

BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。BFS 应用的常见场景就是在一副图中找最短路径。BFS 空间复杂度高，而 DFS 的空间复杂度较低。

二叉树的遍历：DFS、BFS，把其扩展到图，如环判断、拓扑排序、二分图判定，就用到了 DFS 算法；再比如 Dijkstra 算法模板，就是改造版 BFS 算法加上一个类似 dp table 的数组。

图

• 判断是否存在环，有向无环图 (DAG, Directed acyclic graph)
• DFS: 词梯问题
• BFS: 骑士周游问题
• 拓扑排序

设计类

• LRU: 哈希表+双向链表；key 到 node 的哈希表、node 的双向链表。
• LFU: 哈希表；key 到 node 的哈希表、key 到 freq 的哈希表、freq 到 key 的哈希表。
• 前缀树：相同前缀的字符串集中在 Trie 树中的一个子树上，给字符串的处理带来很大的便利
• 求数据流的中位数：使用两个优先队列，大顶堆+小顶堆。
• 单调栈：每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减），只处理一类典型的问题，比如「下一个更大元素」
• 单调队列：队列中的元素全都是单调递增（或递减）的，主要用来辅助解决滑动窗口相关的问题
• 队列实现栈、栈实现队列
• 设计推特（朋友圈时间线）：把合并多个有序链表的算法和面向对象设计结合起来了

数学题

位运算、阶乘、素数、求模、幂运算、随机数、概率