数据结构与算法

Ch.1 算法分析 Algorithm Analysis

（笔记的元知识，评估所有算法的标尺）

复杂度分析：
时间复杂度、空间复杂度
最好、最坏、平均情况
证明与求解：
归纳证明、循环不变式
递归式与求解：代入法、递归树法、主定理
理论下限：
排序的下限复杂度证明
分析方法：
摊还分析 (Amortized Analysis)

Ch.2 线性结构 Linear Structures

（基于数组、链表、栈、队列的算法与技巧）

数组 (Array)：
前缀和、差分数组
双指针技术 (Two Pointers / Sliding Window)
In-place Hashing (原地哈希)
链表 (Linked List)：
Floyd's Cycle-Finding (龟兔赛跑)
栈 (Stack)：
调度站算法 (Shunting-yard)
单调栈 (Monotonic Stack)
队列 (Queue)：
单调队列 (Monotonic Queue)

Ch.3 分治 Divide & Conquer

（将大问题分解为小问题，分别解决后再合并）

排序与选择：
归并排序 (Merge Sort)
快速排序 (Quick Sort) 与 随机快排
快速选择 (Quick Select) 与 随机化选择
MoM (Median of Medians)
查找：
二分查找 (Binary Search)
三分法 (Ternary Search)
数学与数值：
快速幂、快速乘
多项式与快速傅里叶变换 (FFT)
计算几何：
最近点对 (Closest Pair of Points)

Ch.4 树 Tree

搜索树：
二叉搜索树 (BST)
红黑树 (Red-Black Tree)
B树 (B-Tree)
堆：
（二叉）堆 / 优先队列
斐波那契堆 (Fibonacci Heap)
区间与查询 (基于分治思想)：
线段树 (Segment Tree)、懒标记、可持久化
van Emde Boas树 (vEB Tree)
树状数组 (Fenwick Tree / BIT)
树上算法与技巧：
倍增表 (LCA, Kth Ancestor)
(注：树形DP 见“动态规划”)

树的基本概念

Predecessor

前驱（Predecessor）的意思是在遍历中，位于当下遍历的前一个节点，所以前驱节点不一定是该节点的父节点。

Lowest Common Ancestor最小公共祖先

最近公共祖先(Lowest Common Ancestor, LCA)

Binary Search Tree

BST基本概念

A *Binary Search Tree (BST)* is a type of binary tree data structure in which each node contains a unique key and satisfies a specific ordering property:

All nodes in the left subtree of a node contain values *strictly less* than the node’s value.
All nodes in the right subtree of a node contain values *strictly greater* than the node’s value.

换句话说，在BST中，任意一个节点的左子树中的全部nodes都必须比该节点小；右子树则都必须比该节点大。

AVL Tree

BST构建的时候不调整自身结构，第一个insert的元素自然就被当做root，从而会导致退化为链表的风险，比如：

上面这棵树和链表没有任何区别。

我们通过旋转的方式来调整平衡，旋转主要有两种：左旋和右旋。这里要注意，旋转只改变局部关系，而不影响更高层级的关系，所以只有要旋转的对象是root的时候，整棵树才会旋转。

例：

这棵树右侧太深，我们对7进行旋转；由于旋转只改变局部关系，因此我们只看node 7的部分：

这里我们把要旋转的7称为x，那么有：

RightRotate(x):
    y = x.left
    x.left = y.right
    y.right = x

由于这里y.right不存在，所以旋转后如下：

把新的局部根节点5接回原本的tree：

         2
       /  \
      0    5
     / \  / \
   -1  1  4  7
            / \
           3   9

这样就得到了旋转后的tree。

当左子树过重的时候，称为LL型失衡：

可以看到上面这棵树左子树高度为4，右子树为1，差3，严重失衡，需要右旋。

当右子树过重的时候，称为RR型失衡：

这种情况需要左旋。

LR型失衡：

节点 50 的左子树太高（左=3，右=1），但失衡出现在左子树的右侧（40→35→37）。

RL型失衡：

。。。

Red-Black Tree

红黑树是一种特殊的BST，因此BST的性质在红黑树中也是可以使用的。

注意RB Tree中的叶子节点指的是NIL（Null）节点，也称为哨兵节点（Sentinel Node）。

红黑树必须满足以下要求：

每个节点要么是红色，要么是黑色
Root是黑色
NIL节点是黑色
如果一个节点是红色的，那么他的两个子节点都是黑色的
从任意一个节点到其所有叶子节点的路径上，黑色节点的数量相同，这一数量称为该节点的黑高（Black Height）。

Ch.5 图 Graph

搜索与遍历 (基于DFS/BFS)：
拓扑排序 (Topological Sort)
连通分量、强连通分量 (Tarjan, Kosaraju)
割点与桥 (Tarjan)
欧拉回路 (Hierholzer 算法)
最短路径：
Dijkstra 算法 (Paradigm: 贪心)
(Bellman-Ford, Floyd-Warshall 见“动态规划”)
流与匹配：
最大流 (Ford-Fulkerson, Edmonds-Karp)
二分图与匹配 (匈牙利, Hopcroft-Karp)
图专用结构：
并查集 (Disjoint Set) (含路径压缩、按秩合并)
启发式搜索 (Paradigm: Heuristic)：
A*, D*, IDA*

Ch.6 散列结构 Hash-based

散列表 (Hash Table)
字符串哈希 (Rabin-Karp) (Paradigm: 随机)

Ch.7 字符串 String

专用数据结构：
Trie树 (字典树)
Aho-Corasick自动机 (AC 自动机)
后缀数组 SA
后缀自动机 SAM
字符串匹配：
Boyer-Moore (BM 算法) (Paradigm: 启发式)
(KMP, Z-Algorithm 见“动态规划”)

Trie

Boore-Moore

Boyer-Moore 多数投票算法 (Boyer-Moore Majority Vote Algorithm)用于解决一个经典问题： 在一个序列中查找出现次数超过一半（\(> N/2\)）的元素 ，这个元素被称为“多数元素”（Majority Element）。

算法的核心思想是“成对抵消”。我们维护一个候选元素 candidate 和一个计数器 counter。

遍历序列，如果 counter 为 0，我们将当前元素设为 candidate，counter 设为 1。
如果 counter 不为 0，我们将当前元素与 candidate 比较：
如果相同，counter 加 1。
如果不同，counter 减 1（相当于将当前元素与一个 candidate 实例“配对抵消”了）。

由于多数元素出现的次数超过了所有其他元素出现次数的总和，它在“抵消”掉所有其他元素后，最后一定会剩下。

这个算法在第一遍扫描后 只能找出一个候选者 。这个候选者是唯一可能的多数元素，但不能保证它一定是。例如，在 [1, 2, 3] 中，最后剩下的候选者是 3，但它不是多数元素。

因此，算法需要第二遍扫描来验证这个候选者的出现次数是否真的超过了 \(N/2\)。

Misra-Gries

Misra-Gries 算法 (多候选Boyer-Moore, Multi-candidate Boyer-Moore) 用于解决更通用的问题： 在一个序列中查找所有出现次数超过 \(N/k\) 的元素 。

当 \(k=2\) 时，这个问题就退化为上面的 Boyer-Moore 多数投票算法（查找 \(> N/2\) 的元素）。

核心思想（“分组-抵消”）：

这个算法是 Boyer-Moore 思想的推广。我们不再是维护 1 个候选者，而是维护 \(k-1\) 个候选者和它们各自的计数器。我们通常使用一个哈希表（Map）来存储这 \(k-1\) 对 (candidate, counter)。

遍历序列，对于当前元素 element：
如果 element 已经在我们的 \(k-1\) 个候选者中，将其对应的 counter 加 1。
如果 element 不在候选者中，并且我们的候选者列表未满（即少于 \(k-1\) 个）：将 element 加入列表，counter 设为 1。
如果 element 不在候选者中，并且候选者列表已满（已有 \(k-1\) 个）：我们将所有 \(k-1\) 个候选者的 counter 都减 1。
- 在减 1 后，如果某个候选者的 counter 变为 0，就将其从候选者列表中移除。

为什么这样可行？

当列表已满且遇到一个新元素时，我们将所有 \(k-1\) 个候选者的计数器都减 1。这个操作相当于将这个新元素与 \(k-1\) 个不同的候选者（共 \(k\) 个元素）“分组抵消”。

任何一个出现次数超过 \(N/k\) 的元素，它“参与抵消”的次数，也绝对不会超过其他所有元素“参与抵消”的次数总和。因此，它一定能保证在第一遍扫描后，仍然留在我们的 \(k-1\) 个候选者列表中（或者说，它的计数器不会被减到 0 并被移除）。

重要提示：

和 Boyer-Moore 一样，第一遍扫描只提供了 候选者 。列表（Map）中最后剩下的元素，是唯一可能出现次数超过 \(N/k\) 的元素。

我们必须进行 第二遍扫描 ，来精确统计这些候选者的实际出现次数，并筛选出真正超过 \(N/k\) 的元素。

Ch.8 贪心 Greedy

（每一步都做出当前看起来最好的选择，以期望达到全局最优）

区间调度 (Interval Scheduling)
分数背包问题 (Fractional Knapsack)
霍夫曼编码 (Huffman Coding)
图贪心算法：
Prim 算法（最小生成树）
Kruskal 算法（最小生成树）
(注：Dijkstra 算法是贪心，但按问题归类在“图 - 最短路径”中)

Ch.9 回溯 Backtracking

（通过系统地探索所有可能的候选解，并在不满足条件时“回溯”）

基础问题：
N皇后问题 (N-Queens)
排列 / 组合 / 子集 (Permutations / Combinations / Subsets)
哈密顿回路 (Hamiltonian Path)
高级搜索策略：
迭代加深 (Iterative Deepening Search)
剪枝策略与搜索优化
Dancing Links (用于解决 精确覆盖)

Ch.10 动态规划 Dynamic Programming

（通过解决重叠子问题，并存储结果来避免重复计算）

基础模型：
基础DP模型 与 记忆化搜索
Kadane's Algorithm (最大子数组和)
LIS (最长递增子序列)
LCS (最长公共子序列)
LPS 最长回文子序列
Edit Distance (编辑距离)
DP 变体：
背包问题（01、完全、多重、混合）
区间DP
树形DP (最大独立集、树上背包)
状态压缩DP
数位DP
概率DP
DP优化 (如位运算)
字符串 DP：
前缀函数 KMP (KMP 的预处理)
Manacher (最长回文子串)
Z算法 (Z-function)
图 DP：
Bellman-Ford 算法（单源最短路径）
Floyd-Warshall 算法（所有结点对最短路径）

Top-Down (Memoized)

记忆化搜索 是一种 “自顶向下” (Top-Down) 的动态规划实现方式。

它的核心思想是： “用递归来写，用缓存来优化” 。

具体来说：

写出递归函数： 首先，像解决普通递归问题一样，定义一个函数（比如 solve(n)）来解决问题。这个函数会调用自身来解决更小的子问题（比如 solve(n-1) 和 solve(n-2)）。
添加缓存（记忆）： 创建一个数组或哈希表（通常称为 memo 或 dp）来存储已经计算过的子问题的结果。这个缓存需要初始化为一个特殊值（比如 -1），表示“尚未计算”。
查询和存储：
在递归函数的开头，首先检查 缓存：memo[n] 是否已经被计算过？
如果计算过 ，直接返回缓存中的值，不再进行重复计算。
如果没计算过 ，就正常执行递归计算，得到结果 result。
在返回 result 之前， 将其存入缓存 ：memo[n] = result。

例子：斐波那契数列

一个没有记忆化的普通递归：

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2) # 大量的重复计算

使用记忆化搜索：

# 1. 创建缓存
memo = {} 

def fib_memo(n):
    # 3. 检查缓存
    if n in memo:
        return memo[n]

    # 2. 递归逻辑
    if n <= 1:
        result = n
    else:
        result = fib_memo(n-1) + fib_memo(n-2)

    # 3. 存入缓存
    memo[n] = result
    return result

优点：

直观： 代码结构和题目的递归思路完全一致，容易理解和编写。
高效： 只计算真正需要的子问题，避免了不必要的计算。

Bottom-Up (Basic DP)

“基础DP模型” 通常指的是使用 “自底向上” (Bottom-Up) 的迭代方式来实现动态规划。

它的核心思想是： “用循环来写，用数组来递推” 。

它与记忆化搜索的顺序相反：

定义状态 (DP数组)： 创建一个数组（比如 dp[]）。dp[i] 的含义需要被明确定义，它代表了原问题在规模为 i 时的解。
找到边界条件（Base Cases）： 确定最小子问题的解，并用它们来初始化 dp 数组的起始值（例如 dp[0] 和 dp[1]）。
写出状态转移方程： 找到 dp[i] 和它之前的状态（如 dp[i-1], dp[i-2]）之间的关系。这个方程就是DP的核心。
迭代求解：按照子问题从小到大的顺序，使用循环和状态转移方程，依次填满整个 dp 数组。
最终答案： dp 数组的最后一个元素（或某个特定位置的元素）就是原问题的解。

例子：斐波那契数列

定义状态： dp[i] 表示第 i 个斐波那契数。
边界条件： dp[0] = 0, dp[1] = 1。
状态转移方程： dp[i] = dp[i-1] + dp[i-2]
迭代求解：

Python

def fib_dp(n):
    if n <= 1:
        return n

    # 1. 定义状态 (DP数组)
    dp = [0] * (n + 1)

    # 2. 边界条件
    dp[0] = 0
    dp[1] = 1

    # 4. 迭代求解
    for i in range(2, n + 1):
        # 3. 状态转移方程
        dp[i] = dp[i-1] + dp[i-2]

    # 5. 最终答案
    return dp[n]

"基础DP模型" 还包括一些经典的问题类型，例如：

背包问题 (Knapsack)： 如何在有限的背包容量下，装入最有价值的物品。
最长公共子序列 (LCS)： 找到两个字符串中共有的最长的子序列。
最长递增子序列 (LIS)： 找到一个序列中最长的递增子序列。
路径问题 (Path Counting)： 例如在一个网格中，从左上角到右下角有多少条路径。

Ch.11 数值 Numerical

数论：
最大公约数 (欧几里得算法)、最小公倍数
素数筛 (如埃氏筛法)
数论算法 (如模逆元)
数值与代数：
矩阵运算
线性规划 (如单纯形法)
计算几何：
扫描线算法 (Sweep Line)

Ch.12. 高级策略 Advanced Strategies

数据结构的扩张 (Augmenting Data Structures)
分支界限 (Branch and Bound) (e.g., TSP 旅行商问题)
随机与近似：
蒙特卡洛方法 (Monte Carlo)
拉斯维加斯算法 (Las Vegas)
NP完全问题
近似算法
在线学习 (Online Learning)
并发 (Concurrency) (多线程算法)