数据结构与算法完整笔记

总览

索引

章	主题	英文	对应 Hot100
0	绪论与复杂度	Intro & Complexity	贯穿全部
1	线性表：数组与链表	Array & Linked List	数组、链表题
2	栈与队列	Stack & Queue	括号、单调栈、最小栈
3	哈希表	Hash Table	两数之和、异位词、连续序列
4	字符串基础技巧	String Techniques	子串、回文、前缀
5	树与二叉树	Tree & Binary Tree	遍历、路径、构造
6	二叉搜索树	BST	验证 BST、第 K 小
7	AVL / 红黑树 / Splay	Balanced BSTs	进阶理论
8	堆与优先队列	Heap & PQ	TopK、合并 K 链表
9	多路搜索树与 Trie	B/B+ & Trie	单词类扩展
10	图（含 DFS/BFS/Dijkstra 详解）	Graph	岛屿、拓扑、BFS
11	查找与排序概要	Search & Sort	二分、颜色分类
12	分治与主定理	D&C & Master Theorem	归并思想类
13	动态规划（重难点加强）	Dynamic Programming	爬楼到编辑距离、背包
14	贪心与回溯	Greedy & Backtracking	跳跃、排列组合
15	P 与 NP	Complexity Theory	理论边界
16	Hot100 知识点总表	Hot100 Map	全文检索
17	综合计算题	Exercises	考试向
18	专题补强	Advanced Topics	单调栈、最短路、选型

绪论

定义

数据结构（Data Structure）：相互之间存在一种或多种特定关系的数据元素的集合，以及定义在该集合上的操作。

算法（Algorithm）：求解一类问题的有限指令序列，须满足：有穷性、确定性、可行性、输入、输出。

抽象数据类型（ADT, Abstract Data Type）：由数据对象、数据关系及一组基本操作构成的数学模型，强调“做什么”而非“怎么存”。

逻辑结构与存储结构

分类	英文	说明
集合结构	Set	元素仅同属一集合
线性结构	Linear	一对一：表、栈、队列
树形结构	Tree	一对多
图形结构	Graph	多对多
顺序存储	Sequential	连续内存，如数组
链式存储	Linked	指针/引用连接结点
索引存储	Indexed	附加索引表
散列存储	Hashed	由关键字直接定位

渐进记号

设 $f,g:\mathbb{N}\to\mathbb{R}^+$。

$O$（上界）：$f(n)=O(g(n))$ 当存在常数 $c>0,n_0$，使 $n\ge n_0\Rightarrow f(n)\le c\cdot g(n)$
$\Omega$（下界）：$f(n)=\Omega(g(n))$ 当 $g(n)=O(f(n))$
$\Theta$（紧界）：同时为 $O$ 与 $\Omega$
$o$（严格上界）：对任意 $c>0$，最终有 $f(n)<c\cdot g(n)$
$\omega$（严格下界）：对称定义

常见阶（由慢到快）：$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!)$。

时间与空间复杂度

时间复杂度（Time Complexity）：基本操作执行次数关于输入规模 $n$ 的量级，通常取最坏或平均情况。
空间复杂度（Space Complexity）：算法额外占用的辅助空间量级（不含输入本身时称辅助空间）。
均摊分析（Amortized Analysis）：对操作序列总代价求平均，常用聚合、记账、势能法（Splay、动态数组扩容）。

▸计算约定

比较、赋值、算术各计 $O(1)$；递归深度计入空间；哈希表平均 $O(1)$、最坏 $O(n)$（除非说明完美哈希或最坏保证结构）。

计算题：复杂度判定

▸例 0.1

下列代码的时间复杂度？

for i = 1 to n:        # 外层循环：i 取 1..n，共 n 轮
    j = 1              # 每轮将 j 重置为 1
    while j < n:       # 内层：j 未达 n 则继续
        j = j * 2      # j 每次翻倍 → 约 log2 n 次后退出

解：外层 $n$ 次，内层 $j$ 每次翻倍，约 $\log_2 n$ 次，故 $\Theta(n\log n)$。

▸例 0.2

$T(n)=2T(n/2)+n$，$T(1)=1$。用展开法求闭式。

解： $T(n)=n+2\cdot(n/2)+4\cdot(n/4)+\cdots=n\log_2 n+T(1)\cdot n=\Theta(n\log n)$（亦可用主定理，见第 12 章）。

数组

定义

数组（Array）：相同类型元素的连续存储序列，支持按下标 $O(1)$ 随机访问。

动态数组（Dynamic Array / Vector）：可自动扩容的数组，均摊 $O(1)$ 尾部插入。

操作与复杂度

操作	平均	最坏	说明
按下标访问	$O(1)$	$O(1)$
尾插（动态）	均摊 $O(1)$	$O(n)$	扩容时拷贝
任意位置插入/删除	$O(n)$	$O(n)$	需搬移元素
按值查找	$O(n)$	$O(n)$	无序
有序二分查找	$O(\log n)$	$O(\log n)$

代码：动态数组扩容思想

▸扩容思想

动态数组在元素个数达到容量时按倍数申请更大连续空间并拷贝旧数据；因扩容次数为对数级，连续尾插的均摊时间仍为 $O(1)$。

Python：

class DynamicArray:
    """手写动态数组：用底层定长列表 + 逻辑长度，模拟 vector 扩容。"""

    def __init__(self):
        # _a：底层存储槽位；初始只开 1 格，避免空数组时无法扩容
        self._a = [None] * 1
        # _n：已存放的有效元素个数（逻辑长度）
        self._n = 0
        # _cap：底层槽位数（物理容量）；始终满足 _n <= _cap
        self._cap = 1

    def append(self, x):
        # 满员时先扩容：容量翻倍，保证后续多次尾插不必立刻再扩
        if self._n == self._cap:
            self._resize(2 * self._cap)
        # 在逻辑末尾写入新元素（下标恰好为当前长度）
        self._a[self._n] = x
        # 逻辑长度 +1；均摊意义下多数次 append 不触发拷贝
        self._n += 1

    def _resize(self, new_cap):
        # 申请更大的新数组；旧数组稍后被 GC 回收
        b = [None] * new_cap
        # 仅拷贝有效前缀 [0, _n)，无效槽位不必搬
        for i in range(self._n):
            b[i] = self._a[i]
        # 切换底层指针并更新容量；_n 不变
        self._a, self._cap = b, new_cap

    def __getitem__(self, i):
        # 只允许访问逻辑区间；越界抛 IndexError，与内置 list 语义一致
        if not 0 <= i < self._n:
            raise IndexError
        return self._a[i]

    def __len__(self):
        # len(obj) 走逻辑长度，而非底层容量
        return self._n

C：

#include <stdlib.h>  /* malloc / realloc / free */
#include <string.h>  /* 本示意未用；实际可配合 memcpy 做块拷贝 */

/* 动态数组：指针 + 长度 + 容量三元组 */
typedef struct {
    int *a;      /* 堆上连续 int 缓冲 */
    int n, cap;  /* n：有效个数；cap：已分配槽位数 */
} DynArr;

void da_init(DynArr *d) {
    d->cap = 1;              /* 初始容量 1 */
    d->n = 0;                /* 尚无元素 */
    /* 分配 1 个 int 的空间；失败时生产代码应判空 */
    d->a = (int*)malloc(sizeof(int));
}

void da_append(DynArr *d, int x) {
    if (d->n == d->cap) {
        d->cap *= 2;  /* 容量翻倍：扩容次数 O(log n) */
        /* realloc：尽量原地扩展，否则搬到新地址并释放旧块 */
        d->a = (int*)realloc(d->a, d->cap * sizeof(int));
    }
    /* 先写入 a[n]，再 n++；等价于尾插 */
    d->a[d->n++] = x;
}

/* 释放堆缓冲，避免泄漏；结构体本身若在栈上则不必 free(d) */
void da_free(DynArr *d) { free(d->a); }

C++：

#include <vector>  // 标准动态数组容器

// 声明可扩容的 int 序列；默认空，容量由实现管理
std::vector<int> v;
// 尾部插入：空间不足时内部扩容（常见因子 1.5 或 2）并搬移
v.push_back(x);
// 按下标 O(1) 随机访问；要求 0 <= i < v.size()
v[i];
// 说明：连续 push_back 的均摊时间为 O(1)，与上文手写扩容同一思想

使用示例与 Hot100 映射

双指针（对撞/快慢）：盛水容器、移动零、三数之和
前缀积/差分数组：除自身乘积
原地交换与环：旋转图像、下一个排列
二分边界：搜索旋转数组、查找首末位置

▸例 1.1 均摊分析

从空表连续 append $n$ 次，容量 $1,2,4,\ldots,2^{k}$（$2^{k-1}<n\le 2^k$）。拷贝总次数 $<1+2+4+\cdots+2^{k-1}<n$，均摊每次 $O(1)$。

链表

定义

链表（Linked List）：由结点通过指针串联的线性结构。结点含数据域与指针域。

单链表（Singly Linked List）：仅后继指针
双向链表（Doubly Linked List）：前驱+后继
循环链表（Circular Linked List）：尾指向头
哨兵结点（Sentinel / Dummy）：简化头尾边界处理

操作与复杂度

操作	单链表	说明
头插/头删	$O(1)$
按值/按下标查找	$O(n)$
已知结点后插入	$O(1)$	需持有前驱才能删当前（单链表）
删已知结点（双向）	$O(1)$

代码：单链表基本操作

▸链表操作要点

反转依赖「保存后继 → 改指前驱 → 三指针前移」；合并用哨兵简化空头；判环与找入口分别对应 Floyd 相遇与二次同速行走。

Python：

class ListNode:
    """单链表结点：值 + 后继指针。"""

    def __init__(self, val=0, next=None):
        self.val = val    # 数据域
        self.next = next  # 指向下一结点；尾结点为 None


def reverse_list(head):
    """原地反转：三指针迭代，边走边改 next。"""
    prev, cur = None, head  # prev 为已反转段头；cur 为待处理结点
    while cur:
        nxt = cur.next      # 先记下原后继，否则改指后丢失
        cur.next = prev     # 当前结点改指已反转段
        prev, cur = cur, nxt  # 整段前移：新 prev 是刚处理完的结点
    return prev  # 原尾变成新头


def merge_two(l1, l2):
    """合并两条有序链表为一条有序链（升序）。"""
    dummy = ListNode(0)  # 哨兵：避免单独处理「结果头」为空的情况
    p = dummy            # p 始终指向结果链当前尾
    while l1 and l2:
        # 取较小结点接到结果尾，并前进该源链表
        if l1.val <= l2.val:
            p.next, l1 = l1, l1.next
        else:
            p.next, l2 = l2, l2.next
        p = p.next  # 结果尾前移
    # 剩余非空段整段挂上（另一条已空）
    p.next = l1 or l2
    return dummy.next  # 哨兵的下一结点才是真正的头


def has_cycle(head):
    """Floyd 判环：快指针每次两步，慢指针一步；能相遇则有环。"""
    slow = fast = head
    while fast and fast.next:
        # 快指针需保证 fast.next 非空，才能迈两步
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True  # 同一对象相遇 ⇒ 存在环
    return False  # 快指针撞到末尾 ⇒ 无环


def detect_cycle(head):
    """找环入口：先相遇，再从头与相遇点同速走，再次相遇处即入口。"""
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            p = head
            # 数学关系：头到入口距离 = 相遇点再走若干圈后到入口的距离
            while p is not slow:
                p, slow = p.next, slow.next
            return p  # 入口结点
    return None  # 无环

C：

#include <stdlib.h>  /* NULL / 内存相关 */

/* 单链表结点 */
typedef struct Node {
    int val;           /* 数据 */
    struct Node *next; /* 后继；尾为 NULL */
} Node;

Node *reverse_list(Node *head) {
    Node *prev = NULL, *cur = head;  /* 已反转头、当前结点 */
    while (cur) {
        Node *nxt = cur->next;  /* 备份后继 */
        cur->next = prev;       /* 改指前驱 */
        prev = cur;             /* 已反转段头更新 */
        cur = nxt;              /* 处理下一结点 */
    }
    return prev;  /* 新头 */
}

int has_cycle(Node *head) {
    Node *slow = head, *fast = head;  /* 同起点 */
    while (fast && fast->next) {
        slow = slow->next;           /* 慢：一步 */
        fast = fast->next->next;     /* 快：两步 */
        if (slow == fast) return 1;  /* 指针相等 ⇒ 有环 */
    }
    return 0;  /* 走到链尾 ⇒ 无环 */
}

C++：

struct ListNode {
    int val;
    ListNode *next;
    // 构造：写入值，后继默认空指针
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *cur = head;  // 已反转头、当前
    while (cur) {
        ListNode *nxt = cur->next;  // 保存原后继
        cur->next = prev;           // 反转指向
        prev = cur;                 // 前移已反转头
        cur = nxt;                  // 处理下一结点
    }
    return prev;  // 新链表头
}

经典技巧（Hot100）

技巧	英文	题例
反转	Reverse	206
双指针合并	Two-pointer merge	21, 23
快慢指针判环	Floyd cycle	141, 142
双指针找交点	Intersection	160
前后指针删倒数第 N	Remove Nth	19
模拟加法	Digit add	2

▸例 1.2 环入口证明要点

设头到环入口 $a$，入口到相遇点 $b$，环长 $c$。快慢相遇时慢走 $a+b$，快走 $a+b+kc$，且快走路程为慢的 2 倍：$a+b+kc=2(a+b)\Rightarrow a=kc-b$。故从头与从相遇点同速走，必在入口相遇。

栈

定义

栈（Stack）：后进先出（LIFO, Last In First Out）的线性结构。仅在栈顶进行插入（push）与删除（pop）。

操作与复杂度

操作	时间	空间（整体）
push / pop / top	$O(1)$	$O(n)$ 存 $n$ 个元素
判空	$O(1)$

代码

▸栈与最小栈

普通栈仅维护一端；最小栈用同步辅助栈在每次 push/pop 时更新「当前栈内最小值」，使 getMin 为 $O(1)$。

Python：

class Stack:
    """用列表模拟栈：尾部视为栈顶（LIFO）。"""

    def __init__(self):
        self._a = []  # 底层列表；仅在尾端 push/pop

    def push(self, x):
        self._a.append(x)  # 入栈：追加到尾部，摊还 O(1)

    def pop(self):
        return self._a.pop()  # 出栈：删并返回尾元素；空栈会抛异常

    def top(self):
        return self._a[-1]  # 查看栈顶，不删除

    def empty(self):
        return not self._a  # 空列表为假 ⇒ 栈空为 True


# 最小栈：同步维护当前最小值
class MinStack:
    """主栈存元素；辅助栈 mn[i] = 主栈前 i+1 个元素中的最小值。"""

    def __init__(self):
        self.st, self.mn = [], []  # st：数据；mn：同步最小值

    def push(self, x):
        self.st.append(x)
        # 新最小值 = min(x, 旧栈顶最小值)；空辅助栈时即为 x
        self.mn.append(x if not self.mn else min(x, self.mn[-1]))

    def pop(self):
        # 两栈同步弹出，保证 mn 顶始终对应当前 st 的全局最小
        self.st.pop()
        self.mn.pop()

    def top(self):
        return self.st[-1]  # 数据栈顶

    def getMin(self):
        return self.mn[-1]  # 辅助栈顶 = 当前最小值，O(1)

C：

#define MAXN 10000  /* 静态容量上限；生产环境可改为动态扩容 */

/* top 为栈顶下标；-1 表示空栈 */
typedef struct { int a[MAXN]; int top; } Stack;

void init(Stack *s) { s->top = -1; }           /* 置空 */
void push(Stack *s, int x) { s->a[++s->top] = x; }  /* 先 ++top 再写入 */
int pop(Stack *s) { return s->a[s->top--]; }   /* 读出后 top-- */
int peek(Stack *s) { return s->a[s->top]; }    /* 只读栈顶 */
int empty(Stack *s) { return s->top < 0; }     /* top<0 ⇒ 空 */

C++：

#include <stack>           // 标准栈适配器（默认底层 deque）

std::stack<int> st;        // 声明空栈
st.push(1);                // 入栈：元素 1 成为新栈顶
st.top();                  // 返回栈顶引用/值，不弹出
st.pop();                  // 弹出栈顶（无返回值；需先 top 再 pop）
st.empty();                // 是否为空；空为 true

应用

括号匹配（Valid Parentheses）
表达式求值（中缀转后缀 + 后缀求值）
单调栈（Monotonic Stack）：每日温度、柱状图最大矩形、接雨水
函数调用 / DFS 显式栈
浏览器前进后退、撤销

▸例 2.1 单调栈：下一个更大元素

数组 $[2,1,2,4,3]$，从右往左维护递减栈。对每个下标弹掉 $\le$ 当前值的栈顶，栈顶即为右侧第一个更大者；再压入当前。时间 $O(n)$，每个元素至多入出栈一次。

队列

定义

队列（Queue）：先进先出（FIFO, First In First Out）。队尾入队（enqueue），队头出队（dequeue）。

双端队列（Deque）：两端均可进出。

优先队列（Priority Queue）：按优先级出队，常用堆实现（见第 8 章）。

循环队列（Circular Queue）：数组实现时用模运算避免假溢出。

操作与复杂度

操作	时间
enqueue / dequeue / front	$O(1)$（循环数组或链表）

代码：循环队列

▸循环队列

用定长数组加 head/tail 与模运算复用槽位；size 区分「空」与「满」，避免仅靠头尾相等时的歧义。

Python：

class CircularQueue:
    """定长循环队列：下标对 k 取模，实现环形复用。"""

    def __init__(self, k):
        self.a = [0] * k          # 底层环形缓冲，长度固定为 k
        self.k = k                # 容量上限
        self.head = self.tail = self.size = 0
        # head：队头下标（出队端）
        # tail：下一个入队位置（队尾后一位）
        # size：当前元素个数；用于区分空/满

    def enQueue(self, val):
        if self.size == self.k:
            return False          # 已满，拒绝入队
        self.a[self.tail] = val   # 写入当前尾槽
        # 尾指针环形前进；% k 保证落在 [0, k)
        self.tail = (self.tail + 1) % self.k
        self.size += 1
        return True

    def deQueue(self):
        if self.size == 0:
            return False          # 空队列，无法出队
        # 逻辑删除队头：仅前移 head，旧值可被后续入队覆盖
        self.head = (self.head + 1) % self.k
        self.size -= 1
        return True

    def Front(self):
        # 空则约定返回 -1；否则读 head 处元素
        return -1 if self.size == 0 else self.a[self.head]

C：

/* 循环队列控制块：缓冲由调用方分配并挂到 a */
typedef struct {
    int *a, k, head, tail, size;
    /* a：缓冲；k：容量；head/tail：头与下一尾；size：元素数 */
} CQ;

int enQueue(CQ *q, int val) {
    if (q->size == q->k) return 0;       /* 满：失败 */
    q->a[q->tail] = val;                 /* 写入尾槽 */
    q->tail = (q->tail + 1) % q->k;      /* 环形前进 */
    q->size++;                           /* 计数 +1 */
    return 1;                            /* 成功 */
}

C++：

#include <queue>   // FIFO 队列适配器
#include <deque>   // 双端队列容器

std::queue<int> q;   // 单向队列：只能 front 出、back 入
std::deque<int> dq;  // 双端：两端均可 push/pop，常作单调队列底层

Hot100 相关

BFS 层序：二叉树层序、岛屿、单词接龙
双端队列优化：滑动窗口最值（扩展）

哈希表

定义

哈希表（Hash Table / Hash Map）：通过哈希函数 $h(k)$ 将关键字映射到桶（bucket），实现接近 $O(1)$ 的查找、插入、删除。

哈希函数（Hash Function）：将关键字映射到 ${0,1,\ldots,m-1}$。理想情况接近均匀随机。

装填因子（Load Factor） $\alpha=n/m$（元素数/桶数）。过大时需再散列（rehash）。

冲突处理

方法	英文	要点
拉链法	Chaining	每桶一条链表/树；平均链长 $\alpha$
线性探测	Linear Probing	$(h+i)\bmod m$
二次探测	Quadratic Probing	$(h+i^2)\bmod m$
双重哈希	Double Hashing	$(h_1+i\cdot h_2)\bmod m$

成功查找平均（拉链，均匀假设）：$1+\alpha/2$ 量级；开放定址依赖 $\alpha$，需 $\alpha<1$。

代码：拉链法示意

▸拉链法哈希

关键字经哈希映射到桶下标；冲突时在同一桶的链表（此处用列表）中顺序查找、更新或头插/尾插。

Python：

class HashMap:
    """拉链法哈希表示意：每桶一个 list，元素为 (key, val) 元组。"""

    def __init__(self, m=16):
        self.m = m  # 桶数；越大冲突越少，但空间更多
        # 每个桶初始化为空列表；注意勿写成 [[]]*m（会共享同一 list）
        self.buckets = [[] for _ in range(m)]

    def _h(self, key):
        # 内置 hash 再对桶数取模，得到 [0, m) 的桶下标
        return hash(key) % self.m

    def put(self, key, val):
        b = self.buckets[self._h(key)]  # 定位目标桶
        for i, (k, _) in enumerate(b):
            if k == key:
                b[i] = (key, val)  # 已存在：原地更新值
                return
        b.append((key, val))  # 不存在：挂到链尾（也可头插）

    def get(self, key, default=None):
        # 只遍历该 key 所在桶，平均链长约 α = n/m
        for k, v in self.buckets[self._h(key)]:
            if k == key:
                return v
        return default  # 未命中

    def remove(self, key):
        b = self.buckets[self._h(key)]
        for i, (k, _) in enumerate(b):
            if k == key:
                b.pop(i)  # 从链中删除该结点
                return

C：

#define M 10007  /* 桶数：常取质数以改善分布 */

/* 拉链结点：键值 + 指向同桶下一结点 */
typedef struct HNode {
    int key, val;
    struct HNode *next;
} HNode;

HNode *table[M];  /* 全局桶数组；未初始化时为 NULL（文件作用域） */

int h(int key) {
    /* (key%M+M)%M：把负数 key 也映射到非负桶下标 */
    return (key % M + M) % M;
}

void put(int key, int val) {
    int i = h(key);
    /* 先沿链查找：命中则更新 */
    for (HNode *p = table[i]; p; p = p->next)
        if (p->key == key) { p->val = val; return; }
    /* 未命中：头插新结点到桶 i */
    HNode *n = (HNode*)malloc(sizeof(HNode));
    n->key = key;
    n->val = val;
    n->next = table[i];  /* 新结点指向原链头 */
    table[i] = n;        /* 桶头改为新结点 */
}

int get(int key, int *found) {
    for (HNode *p = table[h(key)]; p; p = p->next)
        if (p->key == key) {
            *found = 1;   /* 输出参数：标明命中 */
            return p->val;
        }
    *found = 0;  /* 未找到 */
    return 0;    /* 返回值无意义，靠 found 判断 */
}

C++：

#include <unordered_map>  // 哈希映射（平均 O(1) 查改）
#include <unordered_set>  // 哈希集合（仅存键）

std::unordered_map<int, int> mp;  // 键→值 的空表
mp[2] = 0;                        // operator[]：无则插入，有则赋值
if (mp.count(7)) {}               // count：存在返回 1，否则 0（不插入）
mp.erase(2);                      // 按键删除；不存在则无操作

Hot100 映射

题	模式
1 两数之和	值→下标
49 字母异位词分组	排序键或计数元组→列表
3 无重复最长子串	滑动窗口 + 字符上次下标
128 最长连续序列	集合判起点
347 TopK 高频	计数 + 堆/桶

▸例 3.1

$m=5$，$h(k)=k\bmod 5$，插入 $12,22,7,32$。拉链后桶 $2$：$12\to 22\to 32$，桶 $2$ 另有 $7$（$7\bmod 5=2$）。查找 $32$ 最多比较 3 次；$\alpha=4/5$。

字符串技巧

与 Hot100「字符串 / 字符串处理」对应的核心范式（结构仍依赖数组、哈希、双指针、DP）。

范式	英文	代表题
滑动窗口	Sliding Window	3
中心扩展 / DP	Palindrome	5
排序或计数作键	Anagram key	49
栈	Stack	20
双指针反转	Two pointers	344, 151
纵向扫描	LCP	14

最长回文子串（中心扩展）复杂度： 中心 $2n-1$ 个，每次 $O(n)$，总 $O(n^2)$，空间 $O(1)$。

▸中心扩展

每个下标作为奇回文中心，每对相邻下标作为偶回文中心；向两侧扩展至字符不等，取所有扩展结果中最长者。

Python 中心扩展骨架：

def longest_palindrome(s):
    """枚举全部回文中心，扩展得到候选子串，保留最长。"""

    def expand(l, r):
        # 从 [l, r] 向两侧扩展；初始 l==r 为奇回文，r==l+1 为偶回文
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1  # 左边界外移
            r += 1  # 右边界外移
        # 循环结束时 s[l] 与 s[r] 已不匹配（或越界），
        # 合法闭区间为 [l+1, r-1]，切片写作 s[l+1:r]
        return s[l + 1:r]

    ans = ""  # 当前已知最长回文；空串长度 0
    for i in range(len(s)):
        # 以 i 为中心的奇数长度回文；以 i 与 i+1 为中心的偶数长度回文
        a, b = expand(i, i), expand(i, i + 1)
        # key=len：按长度取最大；长度相同则保留先出现者（稳定于 max 语义）
        ans = max(ans, a, b, key=len)
    return ans

树与二叉树

定义

树（Tree）：有限结点集，满足：有且仅有一个根；其余结点分为互不相交的子树。

二叉树（Binary Tree）：每个结点至多两个子结点，区分为左孩子与右孩子（有序）。

满二叉树（Full / Proper）：每个结点 0 或 2 个孩子（教材定义不一，考研常指：深度为 $k$ 且有 $2^k-1$ 个结点的树为满二叉树）。

完全二叉树（Complete Binary Tree）：深度为 $h$ 时，前 $h-1$ 层满，第 $h$ 层结点靠左连续排列。

平衡二叉树（Height-Balanced）：任意结点左右子树高度差绝对值不超过某常数（AVL 为 1）。

基本性质

设二叉树结点数 $n$，边数 $e$，叶结点数 $n_0$，度为 2 结点数 $n_2$：

$e=n-1$
$n_0=n_2+1$（二叉树）
深度为 $h$ 的二叉树至多 $2^h-1$ 个结点（根深度计 1 时）
具有 $n$ 个结点的完全二叉树深度为 $\lfloor\log_2 n\rfloor+1$
完全二叉树下标（根为 1）：左孩子 $2i$，右孩子 $2i+1$，父 $\lfloor i/2\rfloor$

存储

顺序存储：适合完全二叉树（堆）
二叉链表：left / right（可加 parent）
线索二叉树（Threaded）：空指针指向中序前驱/后继

遍历

遍历	英文	顺序
先序	Preorder	根-左-右
中序	Inorder	左-根-右
后序	Postorder	左-右-根
层序	Level-order	BFS

由先序+中序或后序+中序可唯一还原二叉树（Hot100-105）。

代码：结点与遍历

▸遍历骨架

递归版把“空树返回空序列”作为基准情形；迭代中序用栈模拟沿左链下探；层序用队列按层弹出，同层结点个数用当轮 len(q) 固定。对称判定把左右子树当作镜像对一起比较。

Python：

from collections import deque  # 双端队列：层序遍历需要 O(1) 队首弹出

class TreeNode:
    """二叉链表结点：值 + 左孩子指针 + 右孩子指针。"""

    def __init__(self, val=0, left=None, right=None):
        self.val = val      # 结点关键字 / 载荷
        self.left = left    # 左子树根；无左孩子则为 None
        self.right = right  # 右子树根；无右孩子则为 None

def preorder(root):
    # 先序：根 → 左 → 右；空树贡献空列表，便于列表拼接
    if not root:
        return []
    # [根] 与左、右子树先序结果顺序拼接
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):
    # 中序：左 → 根 → 右；BST 上可得非降序列
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):
    # 后序：左 → 右 → 根；常用于“先处理孩子再处理根”（如删树）
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

def inorder_iter(root):
    # 迭代中序：显式栈代替递归系统栈
    res, st, cur = [], [], root  # res 结果；st 待回访栈；cur 当前指针
    while cur or st:             # 还有未走完的左链，或栈里还有待输出结点
        while cur:               # 一路向左压栈，模拟递归下探
            st.append(cur)
            cur = cur.left
        cur = st.pop()           # 左子树已空，弹出即为“该输出的根”
        res.append(cur.val)
        cur = cur.right          # 转向右子树，继续同一套左链下探
    return res

def level_order(root):
    # 层序（BFS）：按层收集，返回 List[List[val]]
    if not root:
        return []
    q, ans = deque([root]), []   # 队列初含根；ans 存各层列表
    while q:
        level = []
        # 关键轮开始时队列长度 = 当前层结点数，必须先取出再循环
        for _ in range(len(q)):
            u = q.popleft()      # 队首出队（FIFO）
            level.append(u.val)
            if u.left:
                q.append(u.left)   # 下一层候选：先左后右
            if u.right:
                q.append(u.right)
        ans.append(level)
    return ans

def max_depth(root):
    # 最大深度：空树 0；否则 1 + 左右子树深度较大者
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

def is_symmetric(root):
    # 镜像对称：根的左右子树互为镜像
    def eq(a, b):
        # 双侧皆空：对称成立
        if not a and not b:
            return True
        # 恰一侧空：结构不对称
        if not a or not b:
            return False
        # 值相等，且 a 左对 b 右、a 右对 b 左（交叉比较）
        return a.val == b.val and eq(a.left, b.right) and eq(a.right, b.left)
    # 把整棵树与自身作镜像比较；空根亦对称
    return eq(root, root)

C：

/* 二叉链表结点：值 + 左右孩子指针（前向声明式自引用结构体） */
typedef struct TNode {
    int val;
    struct TNode *left, *right;  /* 空孩子用 NULL */
} TNode;

/* 中序递归：左 → 访问根 → 右 */
void inorder(TNode *r) {
    if (!r) return;          /* 基准：空指针直接返回 */
    inorder(r->left);        /* 先完整遍历左子树 */
    /* visit r->val */       /* 访问点：打印或写入结果数组 */
    inorder(r->right);       /* 再遍历右子树 */
}

/* 最大深度：与 Python 版同一递推 */
int max_depth(TNode *r) {
    if (!r) return 0;        /* 空树深度 0 */
    int L = max_depth(r->left);   /* 左子树深度 */
    int R = max_depth(r->right);  /* 右子树深度 */
    return 1 + (L > R ? L : R);   /* 取较大者再加根这一层 */
}

C++：

// 与 LeetCode 风格一致的二叉树结点
struct TreeNode {
    int val;
    TreeNode *left, *right;  // 孩子指针；无孩子为 nullptr
    // 构造函数：初始化列表设定值，左右默认空
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 层序遍历：std::queue<TreeNode*> q; 入队根后 while (!q.empty()) 弹队首、推孩子
// 中序迭代：可用 std::stack<TreeNode*> 模拟上文 Python 的 st

Hot100 二叉树题型归类

类型	题号要点
遍历	94 中序，102 层序，103 锯齿，199 右视图，637 层均值，987 垂直
深度/直径	104 最大深，111 最小深，543 直径
路径	112/113 路径和，124 最大路径和，257 所有路径，563 坡度
结构判定	101 对称，993 堂兄弟，662 最大宽度
BST	98 验证，108 有序数组建树，230 第 K 小
构造/序列化	105 前中构树，297 序列化，116 next 指针
LCA	236 最近公共祖先

▸例 5.1

$n$ 个结点的二叉树，高度最低为多少？

解：完全（或满）时最低，高度 $\Theta(\log n)$；最坏退化为链，高度 $\Theta(n)$。

二叉搜索树

定义

二叉搜索树（BST, Binary Search Tree）：二叉树，对任意结点，左子树一切关键字 $<$ 该结点，右子树一切关键字 $>$ 该结点（或 $\le/\ge$ 依约定，通常禁止重复或规定一侧）。

中序遍历得递增序列。

操作与复杂度

操作	平均	最坏（退化链）
查找/插入/删除	$O(\log n)$	$O(n)$
找 min/max	$O(h)$	$O(n)$
建树（随机插入）	期望高度 $O(\log n)$

代码

▸BST 不变量

对任意结点，左子树关键字均小于该结点、右子树均大于该结点。查找/插入沿比较链下降；删除有孩子时常用右子树最小结点（中序后继）顶替后再删后继。

Python：

def bst_search(root, key):
    # 迭代查找：沿 BST 序下降，直到命中或走到空
    while root and root.val != key:
        # 严格小于走左，否则走右（相等已在 while 条件排除）
        root = root.left if key < root.val else root.right
    return root  # 命中返回结点；否则 None

def bst_insert(root, key):
    # 递归插入：空位处新建结点并挂回父的 left/right
    if not root:
        return TreeNode(key)  # 找到插入点
    if key < root.val:
        root.left = bst_insert(root.left, key)
    elif key > root.val:
        root.right = bst_insert(root.right, key)
    # key == root.val：本实现忽略重复，直接返回
    return root  # 一路把可能更新的子树根传回

def bst_min(root):
    # 最小值在最左叶：不断走 left
    while root.left:
        root = root.left
    return root

def bst_delete(root, key):
    # 递归删除：先定位，再按孩子数分支处理
    if not root:
        return None
    if key < root.val:
        root.left = bst_delete(root.left, key)
    elif key > root.val:
        root.right = bst_delete(root.right, key)
    else:
        # 命中待删结点
        if not root.left:
            return root.right   # 无左：右子树（可空）直接顶替
        if not root.right:
            return root.left    # 无右：左子树顶替
        # 双孩子：取右子树最小（中序后继）覆盖当前值
        succ = bst_min(root.right)
        root.val = succ.val
        # 再在右子树中删除那个后继结点（后继至多有右孩子）
        root.right = bst_delete(root.right, succ.val)
    return root

def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
    # 带开区间 (lo, hi) 约束验证：每个结点值必须落在祖先给出的范围内
    if not root:
        return True
    if not (lo < root.val < hi):
        return False  # 越界则非 BST
    # 左子树上界收紧为 root.val；右子树下界收紧为 root.val
    return (is_valid_bst(root.left, lo, root.val)
            and is_valid_bst(root.right, root.val, hi))

def kth_smallest(root, k):
    # 中序第 k 小：迭代中序，每弹出一个结点 k 减一
    st, cur = [], root
    while True:
        while cur:
            st.append(cur)
            cur = cur.left
        cur = st.pop()
        k -= 1
        if k == 0:
            return cur.val  # 中序第 k 个即为答案
        cur = cur.right

C：

/* 递归插入：在空指针处 malloc 新结点并返回给父指针赋值 */
TNode *bst_insert(TNode *r, int key) {
    if (!r) {
        TNode *n = (TNode*)malloc(sizeof(TNode));
        n->val = key;
        n->left = n->right = NULL;  /* 新叶左右皆空 */
        return n;
    }
    if (key < r->val)
        r->left = bst_insert(r->left, key);   /* 挂到左 */
    else if (key > r->val)
        r->right = bst_insert(r->right, key); /* 挂到右 */
    /* 相等：不插入，保持原树 */
    return r;
}

/* 迭代查找：比较下降，命中或走到 NULL */
TNode *bst_search(TNode *r, int key) {
    while (r && r->val != key)
        r = key < r->val ? r->left : r->right;
    return r;  /* 非 NULL 即找到 */
}

C++：

#include <set>   // 有序集合，底层多为红黑树
#include <map>   // 有序键值映射，同样常为红黑树

std::set<int> s;   // 元素唯一且有序
s.insert(3);       // 插入 3；已存在则无效果（set）
s.count(3);        // 存在返回 1，否则 0（C++20 亦可用 contains）
s.erase(3);        // 按值删除；查找/插删均摊 O(log n)
// 对比：需要“键→值”时用 std::map<K,V>；仅需有序唯一键用 set

▸例 6.1

依次插入 $5,3,7,2,4,6,8$ 得较平衡形态；若插入顺序为 $1,2,3,4,5$ 则退化为右链，查找 $O(n)$。故需平衡 BST。

AVL 树

定义

AVL 树（Adelson-Velsky and Landis Tree）：任一结点左右子树高度差的绝对值 $\le 1$。平衡因子 $bf=h_L-h_R\in{-1,0,1}$。

高度 $h$ 满足与 Fibonacci 相关下界，故 $h=O(\log n)$。

旋转

失衡类型	英文	操作
LL	Left-Left	右旋
RR	Right-Right	左旋
LR	Left-Right	先左旋再右旋
RL	Right-Left	先右旋再左旋

代码：旋转与插入

▸AVL 旋转

每个结点维护高度 h。插入后自下而上更新；若平衡因子绝对值大于 1，按 LL/RR 单旋或 LR/RL 双旋恢复。右旋以左孩子为新根，左旋以右孩子为新根；先更新原子树根高度，再更新新根。

Python：

class AVLNode:
    """AVL 结点：在 BST 结点上额外存子树高度 h。"""

    def __init__(self, val):
        self.val = val
        self.left = self.right = None  # 初始为叶
        self.h = 1                     # 单结点高度计 1

def height(n):
    # 空树高度约定为 0，避免对 None 解引用
    return n.h if n else 0

def update(n):
    # 由孩子高度重算：h = 1 + max(左, 右)
    n.h = 1 + max(height(n.left), height(n.right))

def balance_factor(n):
    # bf = h_L - h_R；AVL 要求 |bf| <= 1
    return height(n.left) - height(n.right)

def rotate_right(y):
    # 右旋（LL）：y 为失衡点，x = y.left 升为新根
    x, t2 = y.left, y.left.right  # t2 原是 x 的右子树，旋后挂到 y 左
    x.right, y.left = y, t2       # x 右指 y；y 左接 t2
    update(y)   # 先更新降下去的 y
    update(x)   # 再更新新根 x（依赖 y 的新高度）
    return x    # 返回新的子树根给上层挂接

def rotate_left(x):
    # 左旋（RR）：与右旋对称，y = x.right 升为新根
    y, t2 = x.right, x.right.left
    y.left, x.right = x, t2
    update(x)
    update(y)
    return y

def avl_insert(root, key):
    # 先按 BST 插入，再在回溯路径上旋转修复
    if not root:
        return AVLNode(key)
    if key < root.val:
        root.left = avl_insert(root.left, key)
    elif key > root.val:
        root.right = avl_insert(root.right, key)
    else:
        return root  # 重复键不插入
    update(root)
    bf = balance_factor(root)
    # LL：左左，一次右旋
    if bf > 1 and key < root.left.val:
        return rotate_right(root)
    # RR：右右，一次左旋
    if bf < -1 and key > root.right.val:
        return rotate_left(root)
    # LR：左右，先对左孩子左旋，再对根右旋
    if bf > 1 and key > root.left.val:
        root.left = rotate_left(root.left)
        return rotate_right(root)
    # RL：右左，先对右孩子右旋，再对根左旋
    if bf < -1 and key < root.right.val:
        root.right = rotate_right(root.right)
        return rotate_left(root)
    return root  # 仍平衡则直接返回

C：结构体增加 int h;，旋转逻辑与上相同（指针版）。

C++：

// 标准库不提供现成 AVL；教学可手写旋转，工程有序表多用红黑树实现的 map/set
#include <map>
std::map<int, int> mp;  // 键有序映射；插入/查找/删除 O(log n)
// mp[k] = v;  mp.count(k);  mp.erase(k);
// 若必须严格 AVL 平衡（更少旋转偏向查找），需自维护结点高度与旋转函数

复杂度

查找/插入/删除最坏均为 $O(\log n)$。

红黑树

定义

红黑树（Red-Black Tree）：自平衡 BST，结点着红或黑，满足：

每个结点非红即黑
根为黑
每个叶（NIL）为黑
红结点两孩子必黑（无相邻红）
任一结点到其后代 NIL 的简单路径黑结点数相同（黑高）

结论：$h\le 2\log_2(n+1)$，操作 $O(\log n)$。

与 AVL 对比

	AVL	红黑树
平衡	更严	略松
插入	至多 2 次旋转	旋转+变色
删除	可能多次旋转	工程上常更优
应用	对查找极敏感场景	`std::map`、`TreeMap`、CFS

插入修复概要

新结点着红；若父红，视叔结点：叔红则变色上移；叔黑则按形态旋转改色。

代码

▸红黑结点

新插入结点通常先着红色以少破坏黑高；nil 哨兵代表空叶且为黑。完整插入/删除还需旋转与 fixup（变色），此处仅给出结点结构与 BST 式查找。

Python（结点与查找）：

BLACK, RED = 0, 1  # 颜色枚举：黑=0，红=1

class RBNode:
    """红黑树结点：关键字、颜色、左右孩子与父指针（便于旋转上溯）。"""

    def __init__(self, key, color=RED):
        self.key = key
        self.color = color  # 新结点默认红
        # 孩子与父；实际实现中空孩子常指向统一的 nil 哨兵
        self.left = self.right = self.parent = None

def rb_search(root, key, nil):
    # 与 BST 查找相同，但用 is not nil 判断“空”，而非 None
    while root is not nil and key != root.key:
        root = root.left if key < root.key else root.right
    return root  # 命中返回结点；否则为 nil

C++：

#include <map>
#include <set>
// libstdc++ / libc++ 中 map、set、multimap、multiset 通常为红黑树
std::map<int, int> mp;  // 有序键值映射；单次操作 O(log n)
std::set<int> st;       // 有序唯一键集合
// mp.insert({k, v});  auto it = mp.find(k);  st.lower_bound(x);

C：教学实现需完整旋转与 fixup；内核有现成 RB 实现可参考。

▸黑高

黑高 $bh$ 的子树至少 $2^{bh}-1$ 个内部结点；又 $bh\ge h/2$，故 $h=O(\log n)$。

▸例 7.1

依次插入 $1..n$ 不会退化成链：变色与旋转维持对数高度。

Splay 树

定义

伸展树（Splay Tree）：经 Splay 将访问结点旋至根的自调整 BST，不存平衡因子，利用访问局部性。

伸展

情形	名称	操作
父为根	Zig	单旋
与父同侧	Zig-Zig	先祖后父（顺序异于 AVL）
与父异侧	Zig-Zag	先父后祖

复杂度

单次最坏 $O(n)$；均摊 $O(\log n)$（势能 $\Phi=\sum\log size(v)$）。

代码骨架

▸Splay 单旋

伸展通过一系列旋转把访问结点抬到根。下列 rotate_right_splay 是带父指针的右旋：更新孩子、父、以及整棵树的 root 引用。Zig / Zig-Zig / Zig-Zag 由多次此类旋转组合而成。

Python：

def rotate_right_splay(root, y):
    # 右旋：x = y.left 升为子树新根；保持 parent 指针一致
    x = y.left
    y.left = x.right                 # y 接手 x 的原右子树
    if x.right:
        x.right.parent = y           # 若该子树非空，其父改为 y
    x.parent = y.parent              # x 接管 y 原来的父
    if not y.parent:
        root = x                     # y 曾是整树根 → 新根为 x
    elif y is y.parent.left:
        y.parent.left = x            # y 是左孩子 → 父的左改挂 x
    else:
        y.parent.right = x           # 否则挂到父的右
    x.right = y                      # x 的右孩子变为 y
    y.parent = x                     # y 的父变为 x
    return root                      # 可能已更换的整树根
# 查找：先按 BST 下降到目标（或失败位置），再对其做 splay 旋至根
# 插入/删除：修改结构后同样 splay，利用局部性把热点留在根附近

C / C++： 竞赛中常手写 splay 维护序列（分裂、合并、区间翻转）。

堆与优先队列

定义

堆（Heap）：满足堆序性质的完全二叉树。

大根堆（Max-Heap）：父 $\ge$ 子
小根堆（Min-Heap）：父 $\le$ 子

优先队列（Priority Queue）：每次取出优先级最高（或最低）元素的 ADT，常用二叉堆实现。

数组下标从 $0$ 起：左 $2i+1$，右 $2i+2$，父 $\lfloor(i-1)/2\rfloor$。

操作与复杂度

操作	时间	说明
找最值	$O(1)$	堆顶
插入 push	$O(\log n)$	上浮 sift-up
删除堆顶 pop	$O(\log n)$	下沉 sift-down
建堆 heapify	$O(n)$	Floyd：自底向上
堆排序	$O(n\log n)$	原地，不稳定

代码：小根堆

▸二叉堆下标

数组下标从 0 起：左孩子 2i+1，右孩子 2i+2，父 (i-1)//2。上浮修复插入，下沉修复删除堆顶；Floyd 建堆从最后一个非叶向下沉，总复杂度 $O(n)$。

Python：

import heapq  # 标准库：默认小根堆；heappush / heappop / heapify

# 手写小根堆：完全二叉树的数组实现
class MinHeap:
    def __init__(self):
        self.a = []  # 堆元素序列；a[0] 恒为当前最小

    def _up(self, i):
        # 上浮（sift-up）：新元素与父比较，更小则交换并继续
        while i > 0:
            p = (i - 1) // 2          # 父下标
            if self.a[p] <= self.a[i]:
                break                 # 已满足堆序，停止
            self.a[p], self.a[i] = self.a[i], self.a[p]
            i = p                     # 继续向根方向检查

    def _down(self, i):
        # 下沉（sift-down）：与较小孩子交换，直到局部堆序成立
        n = len(self.a)
        while True:
            l, r, sm = 2 * i + 1, 2 * i + 2, i  # 左右孩子；sm 记最小者下标
            if l < n and self.a[l] < self.a[sm]:
                sm = l
            if r < n and self.a[r] < self.a[sm]:
                sm = r
            if sm == i:
                break                 # 自己最小，堆序已复原
            self.a[i], self.a[sm] = self.a[sm], self.a[i]
            i = sm

    def push(self, x):
        self.a.append(x)              # 先放末尾（保持完全形态）
        self._up(len(self.a) - 1)     # 再上浮到正确位置

    def pop(self):
        if len(self.a) == 1:
            return self.a.pop()       # 仅一元素：直接弹出
        top = self.a[0]               # 保存堆顶
        self.a[0] = self.a.pop()      # 末元素填到堆顶，长度 -1
        self._down(0)                 # 从根下沉恢复堆序
        return top

    def peek(self):
        return self.a[0]              # O(1) 查看最小元

def heapify(a):
    """Floyd 建堆：自底向上对每个非叶下沉，总 O(n)。"""
    def down(i, n):
        while True:
            l, r, sm = 2 * i + 1, 2 * i + 2, i
            if l < n and a[l] < a[sm]:
                sm = l
            if r < n and a[r] < a[sm]:
                sm = r
            if sm == i:
                break
            a[i], a[sm] = a[sm], a[i]
            i = sm
    n = len(a)
    # 最后一个非叶下标为 n//2-1；从该处倒序到 0
    for i in range(n // 2 - 1, -1, -1):
        down(i, n)

# 需要大根堆时：存 -x，或自定义比较；标准 heapq 仅小根
def kth_largest(nums, k):
    # 维护大小为 k 的小根堆：堆内为当前最大的 k 个数，堆顶是其中最小 = 第 k 大
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)  # 弹出偏小者，只保留 k 个最大候选
    return h[0]

C：

/* 小根堆下沉：在长度为 n 的数组 a 上，从下标 i 开始恢复堆序 */
void sift_down(int *a, int n, int i) {
    while (1) {
        int l = 2 * i + 1, r = 2 * i + 2, sm = i;
        if (l < n && a[l] < a[sm]) sm = l;  /* 左孩子更小则记录 */
        if (r < n && a[r] < a[sm]) sm = r;  /* 右孩子再比 */
        if (sm == i) break;                 /* 已是三者最小 */
        int t = a[i]; a[i] = a[sm]; a[sm] = t;  /* 交换后继续下沉 */
        i = sm;
    }
}

/* Floyd 建堆：从最后一个非叶结点倒序下沉 */
void heapify(int *a, int n) {
    for (int i = n / 2 - 1; i >= 0; --i)
        sift_down(a, n, i);
}

C++：

#include <queue>   // priority_queue
#include <vector>

// 默认比较 less<T>：堆顶为最大，即大根堆
std::priority_queue<int> maxh;
// 传入 greater<int>：堆顶为最小，即小根堆
std::priority_queue<int, std::vector<int>, std::greater<int>> minh;

maxh.push(3);   // 入堆 O(log n)
maxh.top();     // 查看堆顶 O(1)，不删除
maxh.pop();     // 删除堆顶 O(log n)
// 注意：priority_queue 无随机访问；需要第 k 大等请另建大小受限的堆

使用示例

# 合并 K 个有序链表（Hot100-23）：
#   小根堆存元组 (val, list_id, node)；list_id 打破 val 相同时代比较
#   每次弹出最小结点，若其 next 非空再压入，直至堆空
# TopK 高频（Hot100-347）：
#   先 Counter 统计频次，再维护大小为 K 的小根堆（键为频次），或桶排序 O(n)

▸例 8.1 建堆为何 $O(n)$

高度为 $h$ 的层约 $n/2^{h+1}$ 个结点，每个下沉 $O(h)$。$\sum_{h=0}^{\log n} (n/2^{h+1})\cdot h = O(n)$。

▸例 8.2

数组 $[4,1,3,2,16,9,10,14,8,7]$ 建大根堆后堆顶为 $16$，再连续 pop 得降序，即堆排序。

Hot100

215 第 K 大；347 TopK 高频；23 合并 K 链表。

哈夫曼树与 Trie

哈夫曼树

哈夫曼树（Huffman Tree）：带权路径长度 $WPL=\sum w_i l_i$ 最小的二叉树。构造：每次取最小两棵合并。用于前缀编码（无歧义）。

贪心正确性：最优前缀码中频率最低两字符必为最深兄弟叶。

复杂度：用堆维护，$O(n\log n)$。

Trie（字典树）

Trie / Prefix Tree：每边一个字符，从根到结点表示前缀。插入/查询 $O(L)$（$L$ 为串长）。空间与字符集与结点总数相关。

▸Trie 路径

从根出发，每个字符对应一条边；结点的 end 标记“是否有单词在此结束”。search 要求走到终点且 end 为真；startsWith 只需路径存在。

Python：

class TrieNode:
    """字典树结点：出边字典 + 是否单词结尾。"""

    def __init__(self):
        self.ch = {}       # 字符 → 子结点；亦可用长 26 的数组
        self.end = False   # True 表示存在以该结点结尾的完整单词

class Trie:
    def __init__(self):
        self.root = TrieNode()  # 空串对应的根

    def insert(self, word):
        p = self.root
        for c in word:
            # 边不存在则创建，实现前缀共享
            if c not in p.ch:
                p.ch[c] = TrieNode()
            p = p.ch[c]      # 沿边下移
        p.end = True         # 标记单词结束

    def search(self, word):
        p = self.root
        for c in word:
            if c not in p.ch:
                return False  # 中途断边：单词不在树中
            p = p.ch[c]
        return p.end          # 路径在，还须是完整词而非仅前缀

    def startsWith(self, prefix):
        p = self.root
        for c in prefix:
            if c not in p.ch:
                return False
            p = p.ch[c]
        return True           # 只需前缀路径存在，不看 end

C++： 子结点数组 TrieNode* next[26]；C 同理用结构体数组。

B 树与 B+ 树

定义

B 树（B-Tree）：多路平衡查找树，阶为 $m$ 时：根至少 2 子（除非叶）；其余内部结点 $[ \lceil m/2\rceil, m]$ 个子；所有叶同层；结点内关键字有序。

B+ 树（B+ Tree）：关键字全在叶层有序链表；内部结点仅作索引。磁盘/数据库聚簇索引主流结构。

查找 $O(\log_m n)$ 次 IO（树高低）。

图

定义

图（Graph） $G=(V,E)$：顶点集与边集。

术语	英文
有向/无向	Directed / Undirected
权	Weight
度/入度/出度	Degree / In / Out
路径/回路	Path / Cycle
连通/强连通	Connected / Strongly connected
稀疏/稠密	Sparse / Dense
DAG	Directed Acyclic Graph

存储

结构	空间	适场景
邻接矩阵	$O(V^2)$	稠密、判边 $O(1)$
邻接表	$O(V+E)$	稀疏（常用）

遍历

DFS（Depth-First Search）：深度优先，$O(V+E)$
BFS（Breadth-First Search）：广度优先，最短路（无权），$O(V+E)$

代码：邻接表 DFS/BFS

▸图遍历与应用

graph 为邻接表（如 defaultdict(list)）。DFS 递归标记连通可达集；BFS 用队列得层次序。岛屿题把网格当隐式图，淹没 '1' 以免重复计数。课程表用 Kahn 拓扑：入度为 0 入队，若最终取出数等于顶点数则无环。

Python：

from collections import defaultdict, deque
# defaultdict(list)：访问不存在的键时自动得到空列表，便于建邻接表
# deque：双端队列，左端 popleft 为 O(1)，适合 BFS

def dfs_graph(graph, start, visited=None):
    """递归 DFS：收集从 start 出发沿有向/无向边可达的全部顶点。"""
    # 默认参数勿写 visited=set()（可变默认陷阱）；用 None 延迟创建
    if visited is None:
        visited = set()
    visited.add(start)                 # 进入即标记，防环导致无限递归
    for v in graph[start]:             # graph[u] 为 u 的邻居列表
        if v not in visited:           # 未访才下降；已访则跳过
            dfs_graph(graph, v, visited)
    return visited                     # 同一 set 在递归间共享并累积

def bfs_graph(graph, start):
    """迭代 BFS：返回广度优先访问序（同层从左到右取决于邻接表顺序）。"""
    q, seen, order = deque([start]), {start}, []
    # q：待扩展；seen：已入队过；order：出队顺序即 BFS 序
    while q:
        u = q.popleft()                # 队头出队（先进先出）
        order.append(u)
        for v in graph[u]:
            if v not in seen:
                seen.add(v)            # 入队前标记，避免同一点多次入队
                q.append(v)
    return order

def num_islands(grid):
    """Hot100-200：四连通岛屿数；原地把陆地 '1' 改成 '0' 充当 visited。"""
    if not grid:
        return 0
    R, C = len(grid), len(grid[0])     # 行数、列数

    def dfs(i, j):
        # 越界或遇水则停；否则淹没当前格并四向递归扩展
        if i < 0 or j < 0 or i >= R or j >= C or grid[i][j] != '1':
            return
        grid[i][j] = '0'               # 淹没：后续不会再当作新陆地
        for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):  # 右左下上
            dfs(i + di, j + dj)

    cnt = 0
    for i in range(R):
        for j in range(C):
            if grid[i][j] == '1':
                dfs(i, j)              # 新岛屿：一次 DFS 抹平整块连通陆地
                cnt += 1
    return cnt

def can_finish(numCourses, prerequisites):
    """
    Hot100-207：Kahn 拓扑判能否修完全部课程。
    prerequisites 中 [a,b] 表示须先修 b 再修 a，建边 b→a。
    """
    g = defaultdict(list)              # 邻接表：先修 → 后继课
    indeg = [0] * numCourses           # indeg[x] = 指向 x 的边数
    for a, b in prerequisites:
        g[b].append(a)                 # 边 b → a
        indeg[a] += 1                  # a 入度 +1
    # 入度为 0 的课无先修依赖，可立即修
    q = deque([i for i in range(numCourses) if indeg[i] == 0])
    taken = 0
    while q:
        u = q.popleft()
        taken += 1                     # 修完一门
        for v in g[u]:
            indeg[v] -= 1              # 去掉 u→v 后，v 入度减一
            if indeg[v] == 0:
                q.append(v)            # 入度清零方可入队
    return taken == numCourses         # 取出数 < n 说明残留环，无法修完

C：

#define MAXV 1000
/* 链式前向星：head[u] 为 u 的第一条边下标；to/nxt 存边终点与下一条 */
int head[MAXV], to[MAXV * 2], nxt[MAXV * 2], ec;

void add(int u, int v) {
    to[ec] = v;           /* 第 ec 条边指向 v */
    nxt[ec] = head[u];    /* 插入到邻接链表头部 */
    head[u] = ec++;       /* 更新头指针并边计数 +1 */
}

int vis[MAXV];

void dfs(int u) {
    vis[u] = 1;           /* 标记已访问 */
    for (int e = head[u]; e != -1; e = nxt[e])  /* 遍历 u 的出边 */
        if (!vis[to[e]])
            dfs(to[e]);
}
/* 使用前：memset(head, -1, sizeof head); ec = 0; memset(vis, 0, sizeof vis); */

C++：

#include <vector>
#include <queue>

// 邻接表：g[u] 存 u 的所有出边终点
std::vector<std::vector<int>> g(n);  // n 个空 vector
g[u].push_back(v);                   // 加有向边 u→v；无向则再 g[v].push_back(u)
// BFS：std::queue<int> q; 配 vector<int> vis / dist
// DFS：对 g[u] 递归或 stack 迭代

DFS 详解

深度优先搜索（Depth-First Search, DFS）：从起点沿一条路径尽量深入，直至无法前进再回溯；用递归栈或显式栈实现。

性质与复杂度

项目	说明
时间	邻接表 $\Theta(V+E)$；邻接矩阵 $\Theta(V^2)$
空间	递归/栈最坏 $O(V)$（链状）；另加 `vis` 为 $O(V)$
输出	遍历序、连通分量、环、拓扑序、路径存在性等
无权最短路	不能直接当最短路（应用 BFS）

时间戳：disc[u] 首次发现时刻，fin[u] 结束处理时刻。有向图边分类：树边、前向边、后向边（成环）、横向边。

逐步示例

▸DFS 走图

无向图：$0-1,\ 0-2,\ 1-3,\ 2-3$。从 $0$ 出发，邻接表按编号升序。

访问：$0\to 1\to 3\to 2$（由 3 到 2），回溯后 $0$ 的邻居 $2$ 已访问。遍历序示例：$0,1,3,2$。

栈深度峰值与路径长度相关；vis 保证每点入栈/递归一次。

递归与显式栈（三语言）

▸递归 DFS 与显式栈

递归版进入即标记并记录序；迭代版用栈，对邻接表逆序压栈可使弹出顺序贴近递归。无向判环需记录父结点以免把回边当成树边误判。有向拓扑用三色：灰表示递归栈上，再遇灰即为后向边成环；完结后追加，最后整体反转得拓扑序。

Python：

from collections import defaultdict
# 本段：递归 DFS、显式栈 DFS、无向判环、有向三色拓扑

def dfs_recursive(g, u, vis, order):
    """递归 DFS：先访问 u，再深入未访邻居；vis/order 由调用方传入并共享。"""
    vis.add(u)                         # set：O(1) 平均判重
    order.append(u)                    # 先序：进入结点时记录
    for v in g[u]:
        if v not in vis:
            dfs_recursive(g, v, vis, order)

def dfs_iterative(g, start):
    """显式栈 DFS：语义接近递归，但不依赖调用栈深度（适合深图）。"""
    vis, order, st = set(), [], [start]
    while st:
        u = st.pop()                   # 栈顶 = 后进先出
        if u in vis:
            continue                   # 可能被多次压入，弹出时再判
        vis.add(u)
        order.append(u)
        # 逆序压栈：先压的后弹，使邻接顺序与递归 for 正向一致
        for v in reversed(g[u]):
            if v not in vis:
                st.append(v)
    return order

def has_cycle_undirected(n, g):
    """无向图判环：DFS 时若遇到已访且非父结点的邻居，则存在回边（环）。"""
    vis = [False] * n                  # 下标 0..n-1 对应顶点

    def dfs(u, parent):
        vis[u] = True
        for v in g[u]:
            if not vis[v]:
                if dfs(v, u):          # 向子树下降；父为 u
                    return True
            elif v != parent:
                return True            # 已访且非父 → 回边 → 有环
        return False

    for i in range(n):                 # 非连通图：每个分量各搜一次
        if not vis[i] and dfs(i, -1):  # 根的父记为 -1（不存在）
            return True
    return False

def topo_dfs(n, g):
    """有向图 DFS 拓扑排序；发现后向边（环）则返回 None。"""
    WHITE, GRAY, BLACK = 0, 1, 2       # 未访 / 访问中（栈上）/ 已完结
    color = [WHITE] * n
    order = []

    def dfs(u):
        color[u] = GRAY                # 进入递归栈
        for v in g[u]:
            if color[v] == GRAY:
                return False           # 指向栈上结点 = 后向边 → 有环
            if color[v] == WHITE and not dfs(v):
                return False
        color[u] = BLACK
        order.append(u)                # 后序位置记录；全部结束后反转
        return True

    for i in range(n):
        if color[i] == WHITE and not dfs(i):
            return None                # 任一分量有环则整体失败
    order.reverse()                    # 后序反转 = 拓扑序
    return order

C：

#include <stdio.h>
#define MAXV 1005
#define MAXE 200005
/* 链式前向星存图 + 手写栈做迭代 DFS */
int head[MAXV], to[MAXE], nxt[MAXE], ec;
int vis[MAXV], stack_arr[MAXV], top;

void add_edge(int u, int v) {
    to[ec] = v;
    nxt[ec] = head[u];
    head[u] = ec++;
}

void dfs_rec(int u) {
    vis[u] = 1;
    /* visit u：在此处理访问逻辑 */
    for (int e = head[u]; e != -1; e = nxt[e])
        if (!vis[to[e]])
            dfs_rec(to[e]);
}

void dfs_iter(int start) {
    top = 0;
    stack_arr[top++] = start;        /* 起点入栈 */
    while (top) {
        int u = stack_arr[--top];    /* 弹出栈顶 */
        if (vis[u]) continue;        /* 已处理则跳过 */
        vis[u] = 1;
        /* 邻接边依次入栈；若要贴近递归序可反向遍历边表 */
        for (int e = head[u]; e != -1; e = nxt[e])
            if (!vis[to[e]])
                stack_arr[top++] = to[e];
    }
}

C++：

#include <vector>
#include <stack>
using namespace std;

/* 递归 DFS：记录访问序到 order
 * 参数 g 为邻接表；vis[u]==1 表示已访问；order 收集发现序 */
void dfs_rec(int u, vector<vector<int>>& g, vector<int>& vis, vector<int>& order) {
    vis[u] = 1;                 // 进入即标记，防止环上无限递归
    order.push_back(u);         // 先序位置记录（发现时刻）
    for (int v : g[u])          // 遍历 u 的所有出边终点
        if (!vis[v])            // 仅对未访问邻居下降
            dfs_rec(v, g, vis, order);
}

/* 迭代 DFS：邻接表逆序压栈，弹出顺序贴近递归正向遍历
 * 用 std::stack 模拟系统调用栈，避免深图递归爆栈 */
vector<int> dfs_iter(int start, vector<vector<int>>& g) {
    int n = (int)g.size();
    vector<int> vis(n), order;  // vis 默认 0；order 存遍历结果
    stack<int> st;
    st.push(start);             // 起点入栈
    while (!st.empty()) {
        int u = st.top();
        st.pop();               // 取出栈顶（后进先出）
        if (vis[u]) continue;   // 同一点可能被多次压入，弹出时再判
        vis[u] = 1;
        order.push_back(u);
        // 从右往左压：先压的后弹，使弹出顺序 ≈ 递归 for 从左到右
        for (int i = (int)g[u].size() - 1; i >= 0; --i)
            if (!vis[g[u][i]])
                st.push(g[u][i]);
    }
    return order;
}

应用对照

应用	做法	Hot100
连通块 / 岛屿	每未访点开一次 DFS	200
克隆图	DFS/BFS + 哈希映射旧→新	133
判环	无向看父；有向三色	207（亦可用 Kahn）
网格搜索	四向/八向递归	79 单词搜索（回溯式 DFS）

BFS 详解

广度优先搜索（Breadth-First Search, BFS）：按距起点的层数逐层扩展，队列实现。在边权均为 1（或无权）的图上，首次到达即为最短路。

性质与复杂度

项目	说明
时间	邻接表 $O(V+E)$；网格 $O(RC)$
空间	队列最坏 $O(V)$
`dist[v]`	边数意义下的最短距离
`parent[v]`	可回溯最短路径

逐步示例

▸BFS 分层

图：$0-1,\ 0-2,\ 1-3,\ 2-3,\ 3-4$。从 $0$ 出发。

第 0 层：$0$（$dist=0$）
第 1 层：$1,2$（$dist=1$）
第 2 层：$3$（$dist=2$）
第 3 层：$4$（$dist=3$）

$0\to 4$ 最短边数为 3。若用 DFS 可能先走出更长路径，故无权最短路必须用 BFS（或 0-1 BFS / Dijkstra）。

三语言完整实现（含最短路与网格）

▸无权最短路

边权均为 1 时，BFS 首次到达即为最少边数。dist 记距离，parent 可回溯路径。网格与单词接龙把状态空间建成隐式图，同样用队列扩展。

Python：

from collections import deque
# deque：左出右入均为 O(1)，是 BFS 队列的标准选择

def bfs_dist(g, start, n):
    """
    单源无权最短路。
    g：邻接表；start：源点；n：顶点数。
    返回 (dist, parent)：dist[v] 为边数（-1 不可达）；parent 用于还原路径。
    """
    dist = [-1] * n
    parent = [-1] * n                  # 最短路上的前驱；源点保持 -1
    q = deque([start])
    dist[start] = 0                    # 源到自身距离为 0
    while q:
        u = q.popleft()                # 当前层结点出队
        for v in g[u]:
            if dist[v] == -1:          # 首次到达 = 边数意义下最短
                dist[v] = dist[u] + 1  # 父距离 + 1
                parent[v] = u
                q.append(v)            # 入队，待扩展下一层
    return dist, parent

def restore_path(parent, t, start):
    """若起点不可达终点则路径不含 start；否则沿 parent 回溯并反转。"""
    path = []
    while t != -1:
        path.append(t)                 # 从 t 往前回溯
        if t == start:
            break
        t = parent[t]
    path.reverse()                     # 回溯得到逆序，反转成 start→…→t
    return path

def bfs_grid(grid, sr, sc, tr, tc):
    """
    网格最短路：0 可走、1 障碍；四向移动。
    (sr,sc)→(tr,tc) 的最少步数；不可达返回 -1。
    """
    R, C = len(grid), len(grid[0])
    if grid[sr][sc] == 1:
        return -1                      # 起点是障碍，无解
    dist = [[-1] * C for _ in range(R)]  # 二维距离表，-1=未访
    q = deque([(sr, sc)])
    dist[sr][sc] = 0
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))  # 右左下上
    while q:
        r, c = q.popleft()
        if (r, c) == (tr, tc):
            return dist[r][c]          # 终点首次出队时距离即最短
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            # 在界内、可走、且尚未访问
            if (0 <= nr < R and 0 <= nc < C
                    and grid[nr][nc] == 0 and dist[nr][nc] == -1):
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return -1                          # 队列空仍未到终点

def word_ladder_len(beginWord, endWord, wordList):
    """
    Hot100-127：单词接龙。
    每次只改一个字母，且新词须在字典中；求最短变换「词数」（含起点）。
    把每个单词看成图中顶点，差一字的边权为 1，对隐式图做 BFS。
    """
    bank = set(wordList)               # 哈希集合：O(1) 判合法词
    if endWord not in bank:
        return 0                       # 终点不在字典，无法到达
    q = deque([(beginWord, 1)])        # (当前词, 已用词数)
    seen = {beginWord}                 # 已入队过的词，防重复扩展
    while q:
        w, d = q.popleft()
        if w == endWord:
            return d                   # 首次到达终点：步数最少
        # 枚举每一位替换为 a..z，生成所有可能邻居
        for i in range(len(w)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                nw = w[:i] + c + w[i + 1:]  # 切片拼接出新串
                if nw in bank and nw not in seen:
                    seen.add(nw)
                    q.append((nw, d + 1))
    return 0                           # 队列耗尽仍未到终点

C：

#include <string.h>
#define MAXV 1005
#define MAXE 200005
/* 邻接表 + 数组模拟队列的 BFS 最短路（边权 1） */
int g_head[MAXV], g_to[MAXE], g_nxt[MAXE], g_ec;
int dist_arr[MAXV], q[MAXV];  /* dist_arr[v]==-1 表示未访 */

void bfs(int start, int n) {
    memset(dist_arr, -1, sizeof(int) * n);  /* 全部标为不可达 */
    int qh = 0, qt = 0;                     /* 队头 / 队尾下标 */
    q[qt++] = start;                        /* 入队起点 */
    dist_arr[start] = 0;
    while (qh < qt) {
        int u = q[qh++];                    /* 出队 */
        for (int e = g_head[u]; e != -1; e = g_nxt[e]) {
            int v = g_to[e];
            if (dist_arr[v] == -1) {        /* 首次到达 */
                dist_arr[v] = dist_arr[u] + 1;
                q[qt++] = v;
            }
        }
    }
}

C++：

#include <queue>
#include <vector>
using namespace std;

/* 无权图 BFS：返回 (dist, parent)
 * dist[v]：从 start 到 v 的最少边数；-1 表示不可达
 * parent[v]：最短路上的前驱，便于从终点回溯到起点 */
pair<vector<int>, vector<int>> bfs_dist(const vector<vector<int>>& g, int start) {
    int n = (int)g.size();
    vector<int> dist(n, -1), parent(n, -1);  // 初值 -1 = 未访问/不可达
    queue<int> q;                            // FIFO：保证按层扩展
    q.push(start);
    dist[start] = 0;                         // 源点距离为 0
    while (!q.empty()) {
        int u = q.front();
        q.pop();                             // 取出队头
        for (int v : g[u])
            if (dist[v] == -1) {             // 首次到达：边数意义下必最短
                dist[v] = dist[u] + 1;       // 父层距离 +1
                parent[v] = u;               // 记录前驱
                q.push(v);                   // 入队待扩展
            }
    }
    return {dist, parent};                   // C++17 可结构化绑定接收
}

/* 岛屿数量的 BFS 版：发现陆地后用队列淹没整块连通分量
 * 与 DFS 淹没等价；宽图时 BFS 不占递归栈 */
int numIslands_bfs(vector<vector<char>>& grid) {
    int R = grid.size(), C = grid[0].size(), cnt = 0;
    int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};  // 右/左/下/上
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            if (grid[i][j] != '1') continue;  // 跳过水与已淹没格
            cnt++;                            // 发现新岛屿，计数 +1
            queue<pair<int, int>> q;
            q.push({i, j});
            grid[i][j] = '0';                 // 入队即改成水，充当 visited
            while (!q.empty()) {
                auto [r, c] = q.front();      // C++17 结构化绑定拆 pair
                q.pop();
                for (int k = 0; k < 4; k++) {
                    int nr = r + dr[k], nc = c + dc[k];
                    // 在界内且仍是陆地：淹没并入队
                    if (nr >= 0 && nc >= 0 && nr < R && nc < C
                            && grid[nr][nc] == '1') {
                        grid[nr][nc] = '0';
                        q.push({nr, nc});
                    }
                }
            }
        }
    return cnt;
}

BFS vs DFS 选型

目标	选用
无权最短路 / 最少步数	BFS
连通性、任意路径、拓扑、强连通预备	DFS 常更自然
层序、按距离分层处理	BFS
回溯构造（排列、棋盘）	DFS（搜索树）

Dijkstra 详解

Dijkstra 算法：计算非负权图单源最短路。维护 $dist[v]$，反复取出当前 $dist$ 最小的未确定顶点 $u$，对邻边做松弛（relax）：若 $dist[v] > dist[u]+w(u,v)$ 则更新。

正确性前提

边权 $w\ge 0$。若存在负权，小顶堆“已确定”性质失效，应改用 Bellman-Ford 或 SPFA（注意 SPFA 最坏较差）。

两种实现

实现	时间	适用
朴素：$V$ 次扫最小	$O(V^2+E)$	稠密图
二叉堆 / `priority_queue`	$O((V+E)\log V)$	稀疏图（常用）
Fibonacci 堆（理论）	$O(E+V\log V)$	少见实践

允许堆中同一顶点多条目，弹出时若 $d>dist[u]$ 则跳过（懒删除）。

逐步计算题

▸Dijkstra 手算

顶点 $0..4$，有向边（$u\to v:w$）：$0\to1:2,\ 0\to2:5,\ 1\to2:1,\ 1\to3:2,\ 2\to3:1,\ 2\to4:4,\ 3\to4:2$。源点 $0$。

初值：$dist=[0,\infty,\infty,\infty,\infty]$，取出 $0$
松弛：$dist[1]=2,\ dist[2]=5$
取 $1$（$d=2$）：$dist[2]=\min(5,2+1)=3$，$dist[3]=4$
取 $2$（$d=3$）：$dist[3]=\min(4,3+1)=4$，$dist[4]=7$
取 $3$（$d=4$）：$dist[4]=\min(7,4+2)=6$
取 $4$。最终 $dist=[0,2,3,4,6]$

路径例：$0\to1\to2\to3\to4$ 或 $0\to1\to3\to4$，长度均为 6。

三语言实现

Python（堆优化 + 路径还原）：

import heapq
from collections import defaultdict

def dijkstra(n, edges, src):
    # 堆优化 Dijkstra：稀疏图常用；返回 dist 与 parent（可还原路径）
    g = defaultdict(list)            # 邻接表：g[u] = [(v, w), ...]
    for u, v, w in edges:
        g[u].append((v, w))          # 有向边 u→v 权 w
        # 无向图再加 g[v].append((u, w))
    dist = [float('inf')] * n        # dist[v]：源到 v 的当前最短估计，初值 +∞
    parent = [-1] * n                # parent[v]：最短路上的前驱，便于回溯路径
    dist[src] = 0
    pq = [(0, src)]                  # 小顶堆条目 (当前距离, 顶点)；允许同一顶点多条目
    while pq:
        d, u = heapq.heappop(pq)     # 取出堆中距离最小的候选
        if d > dist[u]:
            continue                 # 懒删除：过期条目（已被更优路径更新过）直接跳过
        for v, w in g[u]:
            nd = d + w               # 经 u 松弛到 v 的新距离
            if nd < dist[v]:
                dist[v] = nd         # 发现更短路径则更新
                parent[v] = u
                heapq.heappush(pq, (nd, v))  # 压入新条目；旧条目稍后被懒删除
    return dist, parent

def dijkstra_dense(n, adj, src):
    """邻接矩阵版：adj[u][v]=权，无边为 INF；O(V^2)，适合稠密图。"""
    INF = float('inf')
    dist = [INF] * n
    used = [False] * n               # used[u]=True 表示 u 已纳入最短路确定集 S
    dist[src] = 0
    for _ in range(n):               # 至多确定 n 个顶点
        u = -1
        for i in range(n):
            # 在未确定顶点中选 dist 最小者（朴素扫一遍代替堆）
            if not used[i] and (u == -1 or dist[i] < dist[u]):
                u = i
        if u == -1 or dist[u] == INF:
            break                    # 剩余顶点皆不可达
        used[u] = True               # 非负权下，此时 dist[u] 已是最终最短路
        for v in range(n):
            # 用 u 的出边松弛：若 u→v 存在且经 u 更优则更新
            if adj[u][v] < INF and dist[v] > dist[u] + adj[u][v]:
                dist[v] = dist[u] + adj[u][v]
    return dist

▸堆优化与稠密版对照

堆版用小顶堆反复取当前最近点，边松弛时压入新距离条目，过期条目靠 d > dist[u] 跳过。稠密版不用堆，每轮线性扫描未确定点中 dist 最小者，时间 $O(V^2)$，边多时往往更快。parent 仅堆版维护，沿前驱回溯可得一条最短路径。

C（稠密图 $O(V^2)$）：

#define INF 0x3f3f3f3f                 /* 常用“无穷大”哨兵，相加不易溢出 int */
int adj[MAXV][MAXV], dist_d[MAXV], used_d[MAXV];
/* adj：邻接矩阵；dist_d：最短路估计；used_d：是否已确定 */

void dijkstra_dense(int n, int src) {
    for (int i = 0; i < n; i++) {
        dist_d[i] = INF;             /* 初值：全部不可达 */
        used_d[i] = 0;               /* 0 = 尚未纳入确定集 */
    }
    dist_d[src] = 0;                 /* 源点到自身距离为 0 */
    for (int it = 0; it < n; it++) { /* 至多做 n 轮“取最近点 + 松弛” */
        int u = -1;
        for (int i = 0; i < n; i++)
            /* 未确定点中选 dist 最小；u<0 表示尚未选定任何人 */
            if (!used_d[i] && (u < 0 || dist_d[i] < dist_d[u]))
                u = i;
        if (u < 0 || dist_d[u] >= INF) break; /* 无候选或其余皆不可达 */
        used_d[u] = 1;               /* 标记 u 已确定（非负权下不再变小） */
        for (int v = 0; v < n; v++)
            /* 松弛：存在边 u→v 且经 u 更优则更新 dist_d[v] */
            if (adj[u][v] < INF && dist_d[v] > dist_d[u] + adj[u][v])
                dist_d[v] = dist_d[u] + adj[u][v];
    }
}

▸C 稠密 Dijkstra

全局数组存放矩阵与结果，调用前须将无边位置填为 INF。0x3f3f3f3f 约为 $10^9$，两数相加仍落在 32 位有符号范围内，适合竞赛写法。逻辑与 Python dijkstra_dense 一致。

C++（堆优化）：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;                /* 边权累加用 64 位，避免溢出 */

vector<ll> dijkstra(int n, vector<vector<pair<int,int>>>& g, int src) {
    // g[u] = {(v, w), ...} 邻接表；返回源 src 到各点最短路
    const ll INF = 4e18;             /* 足够大的正无穷哨兵 */
    vector<ll> dist(n, INF);         /* 初值全部不可达 */
    /* 小顶堆：pair 第一关键字为距离，greater<> 使 top 为最小 */
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    dist[src] = 0;
    pq.push({0, src});               /* 起点入堆 */
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();  /* 结构化绑定取出 (距离, 顶点) */
        if (d > dist[u]) continue;   /* 懒删除：过期距离跳过 */
        for (auto [v, w] : g[u]) {
            if (dist[v] > d + w) {   /* 经 u 松弛 v */
                dist[v] = d + w;
                pq.push({dist[v], v}); /* 压入更新后的距离；旧条目稍后丢弃 */
            }
        }
    }
    return dist;
}

▸C++ `priority_queue` 写法

默认 priority_queue 是大顶堆，须以 greater<> 改为小顶堆。允许同一顶点多次入堆，用 d > dist[u] 过滤陈旧记录，避免在堆中做 decrease-key。与 Python heapq 版同一算法骨架。

与其它最短路对比

算法	负权	单源/全源	典型复杂度
BFS	权须为 1	单源	$O(V+E)$
Dijkstra	不可负	单源	$O((V+E)\log V)$
Bellman-Ford	可，能判负环	单源	$O(VE)$
Floyd	可（无负环）	全源	$O(V^3)$

▸专题补强中的 Dijkstra

后文「专题补强」仍保留另一份堆优化代码，可与本节对照；本节含手算、稠密版与路径还原，更完整。

### 经典算法复杂度

算法	用途	时间
Kahn / DFS 拓扑	DAG 序、判环	$O(V+E)$
Kruskal	MST	$O(E\log E)$ + 并查集
Prim	MST	二叉堆 $O(E\log V)$
Dijkstra	非负权最短路	堆 $O(E\log V)$
Bellman-Ford	负权、判负环	$O(VE)$
Floyd-Warshall	全源	$O(V^3)$

并查集（Union-Find）

路径压缩 + 按秩合并，均摊近乎 $O(\alpha(n))$。

class DSU:
    # 并查集：维护互不相交集合；支持 find（查根）与 union（合并）
    def __init__(self, n):
        self.p = list(range(n))      # p[x]=x 表示 x 为所在树的根；初值各自成集
        self.r = [0] * n             # 秩（近似树高），用于按秩合并

    def find(self, x):
        # 路径压缩：递归找根，并把路径上结点直接挂到根下
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]             # 返回集合代表元

    def union(self, a, b):
        a, b = self.find(a), self.find(b)  # 先找到两边的根
        if a == b:
            return False             # 已在同一集合，合并失败（常用于判环）
        if self.r[a] < self.r[b]:
            a, b = b, a              # 保证 a 为秩较大（或不更小）的根
        self.p[b] = a                # 小树挂到大树下
        if self.r[a] == self.r[b]:
            self.r[a] += 1           # 两树等高时，合并后新根秩 +1
        return True                  # 合并成功

▸路径压缩与按秩合并

find 的路径压缩把查找路径打平；union 按秩把较矮树挂到较高树下。二者合用时，单次操作均摊复杂度接近 $O(\alpha(n))$（阿克曼反函数）。union 返回 False 表示两点原先已连通，Kruskal 判环即依赖此语义。

Hot100 图论

200 岛屿；207 课程表（拓扑）；133 克隆图；127 单词接龙（BFS）。

查找与排序概要

查找

方法	平均	最坏	前提
顺序查找	$O(n)$	$O(n)$	无
二分查找	$O(\log n)$	$O(\log n)$	有序随机访问
分块查找	$O(\sqrt{n})$ 量级		块有序
哈希	$O(1)$	$O(n)$
BST/平衡树	$O(\log n)$	$O(\log n)$ 平衡时

二分模板（找左边界）：

def lower_bound(a, target):
    # 在有序数组 a 上找第一个 >= target 的下标；若不存在则返回 len(a)
    lo, hi = 0, len(a)               # 半开区间 [lo, hi)；初态覆盖整个数组
    while lo < hi:                   # 区间非空则继续二分
        mid = (lo + hi) // 2         # 取中点（向下取整）
        if a[mid] < target:
            lo = mid + 1             # mid 及左侧都 < target，答案在右半
        else:
            hi = mid                 # a[mid] >= target，答案在 mid 或更左
    return lo                        # 收敛后 lo==hi，即为下界位置

▸左边界二分语义

维护不变量：答案始终落在 [lo, hi)。a[mid] < target 时丢弃左半；否则丢弃严格大于 mid 的右半，并保留 mid 作为候选。循环结束时 lo 即第一个不小于 target 的下标，与 C++ std::lower_bound 语义一致。

Hot100：33 旋转数组搜索；34 首末位置；240 二维矩阵搜索。

排序

详见《排序算法详解》。比较排序下界 $\Omega(n\log n)$（决策树）。稳定排序：插入、归并、冒泡、计数等；不稳定：快排、堆排、希尔、选择。

Hot100：75 颜色分类（荷兰国旗三路划分，$O(n)$）；88 合并有序数组。

分治与主定理

定义

分治（Divide and Conquer）：将问题分成若干规模更小的同类子问题，递归求解，再合并结果。典型：归并排序、快速排序、二分、最大子数组（分治版）、Strassen 矩阵乘。

一般递推：

$$T(n)=a,T(n/b)+f(n),\quad a\ge 1,\ b>1$$

其中 $a$ 为子问题个数，$n/b$ 为子问题规模，$f(n)$ 为分治与合并代价。

主定理（Master Theorem）

令 $n^{\log_b a}$ 为临界指数。比较 $f(n)$ 与 $n^{\log_b a}$：

情形	条件	结论
1	$f(n)=O(n^{\log_b a-\varepsilon})$，$\varepsilon>0$	$T(n)=\Theta(n^{\log_b a})$
2	$f(n)=\Theta(n^{\log_b a}\log^k n)$，$k\ge 0$	$k=0$：$T=\Theta(n^{\log_b a}\log n)$；一般 $T=\Theta(n^{\log_b a}\log^{k+1}n)$
3	$f(n)=\Omega(n^{\log_b a+\varepsilon})$ 且正则性 $a f(n/b)\le c f(n)$，$c<1$	$T(n)=\Theta(f(n))$

（教材对情形 2 常写 $f=\Theta(n^{\log_b a})$ 则 $T=\Theta(n^{\log_b a}\log n)$。）

经典例子

算法	递推	$\log_b a$	结果
二分查找	$T=T(n/2)+O(1)$	$0$	$\Theta(\log n)$
归并排序	$T=2T(n/2)+O(n)$	$1$	$\Theta(n\log n)$
朴素递归斐波那契（坏）	$T=T(n-1)+T(n-2)+O(1)$	非主定理形	$\Theta(\phi^n)$
草莓矩阵乘 Strassen	$T=7T(n/2)+O(n^2)$	$\log_2 7$	$\Theta(n^{\log_2 7})$

代码：分治最大子数组

Python：

def max_crossing(a, lo, mid, hi):
    # 求「必跨越 mid」的最大子段和：左端在 [lo,mid]、右端在 [mid+1,hi]
    s = 0
    left_sum = float('-inf')         # 从 mid 向左延伸的最大连续和
    for i in range(mid, lo - 1, -1): # 含 mid，向左扫到 lo
        s += a[i]
        left_sum = max(left_sum, s)  # 记录向左任意长度的最佳前缀
    s = 0
    right_sum = float('-inf')        # 从 mid+1 向右延伸的最大连续和
    for i in range(mid + 1, hi + 1):
        s += a[i]
        right_sum = max(right_sum, s)
    return left_sum + right_sum      # 跨越中点的最优 = 左最佳 + 右最佳

def max_subarray(a, lo, hi):
    # 分治：区间 [lo, hi] 内最大子数组和（闭区间下标）
    if lo == hi:
        return a[lo]                 # 单元素：最优即自身
    mid = (lo + hi) // 2
    return max(
        max_subarray(a, lo, mid),           # 完全在左半
        max_subarray(a, mid + 1, hi),       # 完全在右半
        max_crossing(a, lo, mid, hi),       # 跨越中点
    )
# T(n)=2T(n/2)+O(n)=Theta(n log n)；Kadane 为 O(n) DP

▸分治最大子数组

最优子段要么全在左、要么全在右、要么跨越中点。跨越情形用两次线性扫描合并，单层 $O(n)$；递推符合主定理情形 2，总时间 $\Theta(n\log n)$。若只需最大和，Kadane 动态规划可达线性时间。

C：

#include <limits.h>
/* 返回三者最大值，供分治合并时比较左 / 右 / 跨越 */
int max3(int a, int b, int c) {
    int t = a > b ? a : b;           /* 先取 a、b 较大者 */
    return t > c ? t : c;            /* 再与 c 比较 */
}
int max_crossing(int *a, int lo, int mid, int hi) {
    /* 必含 a[mid] 与右侧至少一格的跨越中点最大和 */
    int s = 0, left = INT_MIN, right = INT_MIN; /* INT_MIN 作负无穷初值 */
    for (int i = mid; i >= lo; --i) { /* 从 mid 向左累加，更新左最佳 */
        s += a[i];
        if (s > left) left = s;
    }
    s = 0;
    for (int i = mid + 1; i <= hi; ++i) { /* 从 mid+1 向右累加，更新右最佳 */
        s += a[i];
        if (s > right) right = s;
    }
    return left + right;             /* 左右最佳之和即跨越和 */
}
int max_subarray(int *a, int lo, int hi) {
    if (lo == hi) return a[lo];      /* 递归边界：单元素区间 */
    int mid = (lo + hi) / 2;         /* 中点划分 */
    return max3(max_subarray(a, lo, mid),           /* 左半最优 */
                max_subarray(a, mid + 1, hi),       /* 右半最优 */
                max_crossing(a, lo, mid, hi));      /* 跨越中点最优 */
}

▸C 版与 Python 对照

算法步骤一一对应：max_crossing 两次单向扫描，max_subarray 三路取最大。INT_MIN 对应 Python 的 float('-inf')；全为负时仍能正确返回最大的单个元素（由边界与扫描共同保证）。

C++： 与 C 相同逻辑，可用 std::numeric_limits<int>::min() 与 std::max。

▸例 12.1

$T(n)=4T(n/2)+n^2$。$\log_2 4=2$，$f(n)=n^2=\Theta(n^{\log_b a})$，情形 2，$T=\Theta(n^2\log n)$。

▸例 12.2

$T(n)=2T(n/2)+n^2$。$\log_2 2=1$，$f=n^2=\Omega(n^{1+\varepsilon})$，且 $2(n/2)^2=n^2/2\le c n^2$，情形 3，$T=\Theta(n^2)$。

▸例 12.3

$T(n)=T(n/2)+1$ → $\Theta(\log n)$；$T(n)=9T(n/3)+n$ → $\log_3 9=2$，$f=O(n^{2-\varepsilon})$，情形 1，$T=\Theta(n^2)$。

动态规划

定义

动态规划（Dynamic Programming, DP）：将问题划分为重叠子问题，通过填表（或记忆化）复用结果，并具有最优子结构。

步骤：刻画状态 → 转移方程 → 边界 → 计算顺序 → 复杂度。

与分治区别：分治子问题通常不重叠；DP 子问题高度重叠。

常见类型

类型	英文	Hot100 代表
线性 DP	Linear	70 爬楼，198 打家劫舍，53 最大子数组
背包/完全背包	Knapsack	322 零钱，279 完全平方
区间/序列	LCS/LIS/Edit	1143，300，72
股票类	Stock	121
字符串分割	Word Break	139
树形 DP	Tree DP	124 最大路径和

经典方程与代码

爬楼梯 / 斐波那契型： $dp[i]=dp[i-1]+dp[i-2]$，$O(n)$ 时间 $O(1)$ 空间。

▸经典线性与双串 DP

下列实现把多道 Hot100 题压成滚动变量或二维表：爬楼与打家劫舍只保留常数个前驱状态；Kadane 用「以当前结尾」与全局最优双变量；零钱为完全背包最少件数；LIS 朴素为 $O(n^2)$；编辑距离与 LCS 同属双串填表模板。

Python：

def climb(n):
    # 爬楼梯：到达 n 阶的方法数 = 到达 n-1 与 n-2 之和（每次跨 1 或 2 阶）
    if n <= 2:
        return n                 # 边界：1→1，2→2；n=0 时按题意另议
    a, b = 1, 2                  # a=dp[i-2]，b=dp[i-1]；滚动省掉 O(n) 数组
    for _ in range(3, n + 1):    # 从第 3 阶递推到第 n 阶
        a, b = b, a + b          # 同步赋值：新 a←旧 b，新 b←旧 a+旧 b
    return b                     # 循环结束时 b = dp[n]

def max_subarray_kadane(nums):
    # Kadane：最大子数组和；cur 表示以当前位置结尾的最优，best 为全局最优
    best = cur = nums[0]         # 必须用首元素初始化，避免全负时误用 0
    for x in nums[1:]:
        cur = max(x, cur + x)    # 要么单独开新段，要么接在旧段后
        best = max(best, cur)    # 用 cur 更新全局答案
    return best                  # 时间 O(n)，额外空间 O(1)

def rob(nums):
    # 打家劫舍：相邻房屋不可同时取；滚动 prev2=dp[i-2]，prev1=dp[i-1]
    prev2 = prev1 = 0            # 空前缀价值为 0（房屋下标从左扫到右）
    for x in nums:
        # 不偷当前：prev1；偷当前：prev2+x；取较大者作为新的 prev1
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1                 # 扫完即整条街最优

def coin_change(coins, amount):
    # 零钱兑换：完全背包最少硬币数；无解返回 -1
    INF = amount + 1             # 上界哨兵：合法答案至多 amount 枚 1 元
    dp = [0] + [INF] * amount    # dp[0]=0；其余先置 INF 表示尚不可达
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                # 用一枚面值 c 转移到 x：件数 = dp[x-c]+1
                dp[x] = min(dp[x], dp[x - c] + 1)
    # 仍为 INF 表示凑不出
    return dp[amount] if dp[amount] < INF else -1  # O(amount * |coins|)

def length_of_LIS(nums):
    # O(n^2) DP；另有 O(n log n) 贪心+二分（见后文 LIS_nlogn）
    n = len(nums)
    dp = [1] * n                 # dp[i]：以 nums[i] 结尾的 LIS 长度，至少为 1
    for i in range(n):
        for j in range(i):       # 枚举所有严格小于 nums[i] 的前驱
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp) if dp else 0  # 空数组约定 0；否则取所有结尾中的最大长度

def edit_distance(a, b):
    # Levenshtein：将 a 变为 b 的最少插入/删除/替换次数
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]  # dp[i][j]：a[:i] 与 b[:j]
    for i in range(m + 1):
        dp[i][0] = i             # b 为空：删掉 a 的前 i 个字符
    for j in range(n + 1):
        dp[0][j] = j             # a 为空：插入 b 的前 j 个字符
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # 字符相同：无需操作
            else:
                # 删 a[i-1] / 插入 b[j-1] / 替换，三者取最小再 +1
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]              # 时间与空间 O(mn)；空间可压成两行

def LCS(a, b):
    # 最长公共子序列长度（可不连续，须保持相对次序）
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]  # 第 0 行/列表示空前缀，LCS=0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1  # 匹配：公共长度 +1
            else:
                # 不匹配：丢掉 a 或 b 的当前字符，取较大
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

C：

int climbStairs(int n) {
    /* 爬楼梯：与 Python climb 同递推；a、b 滚动保存相邻两项 */
    if (n <= 2) return n;
    int a = 1, b = 2, t;         /* t 为临时和，避免覆盖丢失 */
    for (int i = 3; i <= n; i++) {
        t = a + b;               /* 新值 = 前两项之和 */
        a = b;                   /* 窗口右移 */
        b = t;
    }
    return b;                    /* b == 到达 n 阶的方法数 */
}

int maxSubArray(int* nums, int n) {
    /* Kadane：nums 为长度 n 的数组；best/cur 含义同 Python 版 */
    int best = nums[0], cur = nums[0];
    for (int i = 1; i < n; i++) {
        /* 三元：单独开段 nums[i]，或接在 cur 后 */
        cur = nums[i] > cur + nums[i] ? nums[i] : cur + nums[i];
        if (cur > best) best = cur;
    }
    return best;
}

C++：

int coinChange(vector<int>& coins, int amount) {
    // 完全背包最少枚数；初值 amount+1 作 INF 哨兵（合法解 ≤ amount）
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;                   // 凑 0 元需要 0 枚
    for (int x = 1; x <= amount; x++)
        for (int c : coins)
            if (c <= x)
                dp[x] = min(dp[x], dp[x - c] + 1);  // 枚举最后一枚硬币
    // 仍大于 amount 表示不可达
    return dp[amount] > amount ? -1 : dp[amount];
}

复杂度分析要点

状态数 $\times$ 单状态转移代价。编辑距离状态 $O(mn)$、转移 $O(1)$ → 时间 $O(mn)$、空间可压到 $O(\min(m,n))$。

▸例 13.1

背包容量 $W$，物品 $n$，0-1 背包二维 $O(nW)$；滚动数组压成一维时须逆序更新容量，防重复选用。

▸例 13.2

LIS：$O(n^2)$ 的 $dp[i]=$ 以 $i$ 结尾的最长；维护 tails 数组二分得 $O(n\log n)$。

适用条件与建模步骤

判定能否使用 DP 的常用清单：

最优子结构（Optimal Substructure）：最优解包含子问题的最优解。
重叠子问题（Overlapping Subproblems）：递归树中同一状态被反复求解。
能定义状态与转移，且无“后效性”（当前决策只依赖状态所概括的信息）。

建模固定五步：状态含义 → 转移方程 → 边界 → 计算顺序（拓扑）→ 答案位置/回溯方案。

记忆化 vs 递推

	记忆化搜索（Top-down）	递推填表（Bottom-up）
写法	递归 + `@cache` / 数组标记	循环按依赖填表
优点	只算到的状态、贴近公式	无栈溢出、易压空间
空间	递归栈 + 表	表（可滚动）

Python 记忆化示例（爬楼）：

▸记忆化搜索

@lru_cache(None) 把 (n,) 映射到返回值并缓存；同一 n 只真正计算一次。递归式直接对应转移 $f(n)=f(n-1)+f(n-2)$，与自底向上滚动变量等价，但依赖调用栈。

from functools import lru_cache  # 标准库：函数结果按参数哈希缓存

@lru_cache(None)                 # None = 无上限缓存；亦可用 maxsize=...
def climb_memo(n):
    # Top-down：先问子问题，再合并；命中缓存则直接返回
    if n <= 2:
        return n                 # 基准情形，停止递归
    return climb_memo(n - 1) + climb_memo(n - 2)  # 状态转移；子结果自动入库

背包九讲要点（科班）

设容量 $W$，物品 $i$ 重量 $w_i$、价值 $v_i$。

0-1 背包

每件至多选一次：

$$dp[i][j]=\max(dp[i-1][j],\ dp[i-1][j-w_i]+v_i)\quad (j\ge w_i)$$

一维优化：for i; for j=W..w_i: dp[j]=max(dp[j], dp[j-w_i]+v_i)（逆序）。

完全背包

每件无限件：一维正序 for i; for j=w_i..W，使 dp[j-w_i] 已含本物品。

多重背包

每件最多 $k_i$ 件：二进制拆分转 0-1，或单调队列优化。

Python（0-1 与完全）：

▸一维背包循环方向

0-1 背包对容量逆序枚举，使 dp[j-w] 仍是「未选当前物品」的旧值，保证每件至多一次。完全背包正序枚举，使 dp[j-w] 已含当前物品，从而允许同件多次使用。

def knapsack_01(W, w, v):
    # 0-1 背包：容量 W；w[i]/v[i] 为第 i 件重量与价值；每件至多一次
    n = len(w)
    dp = [0] * (W + 1)           # dp[j]：容量恰为 j（或≤j）时的最大价值
    for i in range(n):
        # 逆序：从 W 降到 w[i]，避免本轮刚写入的 dp[j-w] 被再次使用
        for j in range(W, w[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - w[i]] + v[i])  # 不选 / 选第 i 件
    return dp[W]

def knapsack_complete(W, w, v):
    # 完全背包：每件可用无限次；一维正序是关键
    dp = [0] * (W + 1)
    for i in range(len(w)):
        for j in range(w[i], W + 1):  # 正序：dp[j-w[i]] 可能已含物品 i
            dp[j] = max(dp[j], dp[j - w[i]] + v[i])
    return dp[W]

C++：

int knapsack01(int W, vector<int>& w, vector<int>& v) {
    // 与 Python knapsack_01 同义：一维逆序 0-1 背包
    vector<int> dp(W + 1, 0);    // 初值 0：容量不足时价值为 0
    for (size_t i = 0; i < w.size(); ++i)
        for (int j = W; j >= w[i]; --j)  // j 从大到小，防同件复用
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    return dp[W];
}

C：同理用一维数组 dp[W+1]，注意循环边界。

▸背包填表

$W=5$，物品 $(w,v)=(2,3),(3,4),(4,5)$，0-1。

物品 1 后：$dp=[0,0,3,3,3,3]$
物品 2 后：$j=5\leftarrow \max(3,0+4)=4$；$j=3\leftarrow4$ → $[0,0,3,4,4,7]$
物品 3：$j=5\leftarrow\max(7,3+5)=8$？$5-4=1$ 处为 0，故 $\max(7,5)=7$；$j=4\leftarrow\max(4,5)=5$。
最终最优 7（物品 1+2）。若误用完全背包正序，可能重复选同一件，结果不同——务必分清模型。

Hot100 DP 逐题强化

下列与既有代码互补：补齐状态定义、边界与复杂度；未重复删除前文实现。

70 爬楼梯

状态：$dp[i]=$ 到达 $i$ 阶方法数
转移：$dp[i]=dp[i-1]+dp[i-2]$
边界：$dp[1]=1,dp[2]=2$
复杂度：$O(n)/O(1)$

121 买卖股票一次

维护历史最低价 $mn$，答案 $\max(price-mn)$
或 $dp[i][0]$ 持有、$dp[i][1]$ 未持有（通用股票 DP 框架的一维退化）
$O(n)/O(1)$

53 最大子数组和（Kadane）

$f[i]=\max(a[i],\ f[i-1]+a[i])$，答案 $\max f[i]$
全负时取最大元素；勿把 $f$ 初始化为 0

198 打家劫舍

$dp[i]=\max(dp[i-1],\ dp[i-2]+nums[i])$
环形房屋（213）拆成「不偷第一」与「不偷最后」两次

279 完全平方数

完全背包：物品为 $1^2,2^2,\ldots$，求凑成 $n$ 的最少个数
$dp[x]=\min_j dp[x-j^2]+1$，$O(n\sqrt{n})$

139 单词拆分

$dp[i]=$ 前缀 $s[:i]$ 可否拆分
$dp[0]=\mathrm{True}$；$dp[i]=\bigvee_{j<i}(dp[j]\land s[j:i]\in wordDict)$
$O(n^2\cdot L)$ 量级（视字典实现）

Python：

▸单词拆分布尔 DP

dp[i] 表示前缀 s[:i] 能否由字典拼出。枚举分割点 j：若前缀已可拆且 s[j:i] 在字典中，则 dp[i] 为真并提前结束内层。字典转 set 使成员判定平均 $O(1)$。

def word_break(s, wordDict):
    # 139：判断 s 能否拆成 wordDict 中单词的拼接（可复用）
    words = set(wordDict)        # 哈希集合：加速 s[j:i] in words
    n = len(s)
    dp = [False] * (n + 1)       # dp[i] ↔ 前缀长度 i 是否可达
    dp[0] = True                 # 空前缀约定可拆
    for i in range(1, n + 1):
        for j in range(i):       # 尝试所有分割点 j（左段长度 j）
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break            # 找到一种合法切分即可
    return dp[n]                 # 整串对应 dp[n]

300 最长递增子序列 LIS

$O(n^2)$：$dp[i]=1+\max{dp[j]:j<i,a[j]<a[i]}$
$O(n\log n)$：tails[k]= 长度为 $k+1$ 的增子序列最小尾；二分更新

▸LIS 贪心加二分

tails 始终有序：对新元素 x，用 bisect_left 找第一个 $\ge x$ 的位置。若在末尾则扩展长度；否则用更小的 x 替换该位置尾，为后续更长序列留余地。len(tails) 即 LIS 长度（不必还原序列）。

import bisect                      # 对有序序列做二分查找/插入位置

def LIS_nlogn(nums):
    # O(n log n)：维护「各长度下最小可能尾」数组 tails
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)  # 第一个 ≥ x 的下标；严格递增用 left
        if i == len(tails):
            tails.append(x)        # x 比所有尾都大：LIS 长度 +1
        else:
            tails[i] = x           # 用更小尾替换，保持 tails 非降且尽量小
    return len(tails)

322 零钱兑换

完全背包最少件数；$dp[0]=0$，其余 $+\infty$；无解返回 $-1$

72 编辑距离

$dp[i][j]=$ $a[:i]$ 与 $b[:j]$ 最小编辑
相等：$dp[i-1][j-1]$；否则 $1+\min($删,插,改$)$
空间可两行滚动

C++：

▸编辑距离二维表

边界：空串与另一串的距离等于长度（全删或全插）。字符相等时沿对角线继承；否则在删除、插入、替换三种代价中取最小并加一。min({...}) 为 C++11 初始化列表重载。

int minDistance(string a, string b) {
    // 72：a 变为 b 的最少编辑次数（与 Python edit_distance 同转移）
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));  // (m+1)×(n+1) 表
    for (int i = 0; i <= m; i++) dp[i][0] = i;  // 删完 a 的前 i 个
    for (int j = 0; j <= n; j++) dp[0][j] = j;  // 插入 b 的前 j 个
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1];    // 匹配：无代价
            else
                // 删 a[i-1] / 插 b[j-1] / 替换，取最小 +1
                dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
    return dp[m][n];
}

1143 最长公共子序列 LCS

$a[i]=b[j]$：$dp[i-1][j-1]+1$；否则 $\max(dp[i-1][j],dp[i][j-1])$
与编辑距离同属「双串 DP」模板

124 树形 DP：最大路径和

对结点 $u$：向下贡献 $\max(0,\mathrm{gain}(left))+\max(0,\mathrm{gain}(right))+u.val$ 更新全局
向父返回：$u.val+\max(0,\mathrm{gain}(left),\mathrm{gain}(right))$
时间 $O(n)$

▸树形路径和

gain(u) 返回「从 u 出发向下单支」的最大贡献（负贡献截断为 0）。路径可以在 u 处「拐弯」同时吃左右，故用 u.val+L+R 刷新全局；返回父结点时只能选左右中较大的一支，否则路径无法成简单路径。

def max_path_sum(root):
    # 124：二叉树任意路径（至少一结点）的最大权值和
    ans = float('-inf')          # 全局答案；用 -inf 以正确处理全负树

    def gain(u):
        nonlocal ans             # 闭包写外层 ans
        if not u:
            return 0             # 空子树对父无正贡献
        L = max(0, gain(u.left))   # 左支负则弃用（等价于不走左边）
        R = max(0, gain(u.right))
        ans = max(ans, u.val + L + R)  # 以 u 为最高点的路径
        return u.val + max(L, R)       # 向上只延伸一支

    gain(root)
    return ans

区间 DP 与状态压缩（进阶）

区间 DP：枚举长度与左右端点，如矩阵链乘、戳气球、回文分割相关。

$$dp[l][r]=\min_{k} / \max_{k}, f(dp[l][k],dp[k][r],\ldots)$$

复杂度常 $O(n^3)$。

状压 DP：状态用比特表示子集，如旅行商 $dp[S][i]=$ 走过集合 $S$ 且位于 $i$ 的最短路，$O(n^2 2^n)$。

数位 DP：按数字位计数，记忆化 (pos, tight, ...)，竞赛常用。

双串 / 网格 DP 模板（C）

▸C 语言 LCS 填表

使用静态二维数组避免大栈分配；!i || !j 对应空前缀边界。字符相等时对角线加一，否则取上方与左方较大者。返回 dp[m][n] 即为最长公共子序列长度。

/* LCS 长度：与前文 Python LCS 同转移；a、b 为以 '\0' 结尾的 C 字符串 */
int lcs(char *a, char *b) {
    int m = strlen(a), n = strlen(b);  /* 两串长度 */
    static int dp[1005][1005];         /* 静态区：容量按题目上界约定 */
    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= n; j++) {
            if (!i || !j)
                dp[i][j] = 0;          /* 任一侧为空前缀：LCS=0 */
            else if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;  /* 匹配 */
            else
                /* 不匹配：取删左或删右的较大长度 */
                dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
        }
    return dp[m][n];
}

网格路径数（障碍）： $dp[i][j]=dp[i-1][j]+dp[i][j-1]$（可走时），$O(RC)$。

常见陷阱

陷阱	说明
初始化错误	求 min 时非 0 位置应置 INF；Kadane 勿从 0 起若全负
0-1 / 完全循环方向	逆序防重复用；正序允许多次用
状态维数不够	股票「第几次交易」需加一维；环形房屋需拆分
后效性	状态未记录必要历史则转移错误
复杂度漏算转移	LIS 朴素内层 $O(n)$ 不可省

DP 计算题

▸例 DP-1 填表：LCS

$a=\mathrm{ABCBDAB}$，$b=\mathrm{BDCABA}$。$dp[7][6]$ 为多少？

解：经典结果为 $4$（如 BCBA / BDAB）。可按转移逐步填 $7\times 6$ 表验证。

▸例 DP-2 编辑距离

$a=\mathrm{kitten}$，$b=\mathrm{sitting}$。最小编辑？

解： $3$（$k\to s$，$e\to i$，末尾 $+\mathrm{g}$）。

▸例 DP-3 完全背包

硬币 $[1,2,5]$，金额 $11$，最少枚数？

解： $5+5+1$ 共 3 枚；$dp[11]=3$。

▸例 DP-4 复杂度

区间 DP 枚举 $len=1..n$，$l=0..n-len$，$k=l..r$，总时间？

解： $\Theta(n^3)$。

▸例 DP-5 与分治对比

斐波那契递归无记忆：$T(n)=\Theta(\phi^n)$；DP/记忆化后？

解：状态 $O(n)$、转移 $O(1)$，总 $\Theta(n)$。重叠子问题是关键。

贪心

定义

贪心（Greedy）：每步选当前最优，期望全局最优。需证明：贪心选择性质 + 最优子结构（交换论证或成熟定理如拟阵）。

问题	Hot100	要点
跳跃游戏	55/45	维护最远可达
合并区间	56/57	排序后线性合并
股票一次	121	维护历史最低

Python：

▸跳跃与区间合并

can_jump 维护最远可达下标，一旦当前下标越界则失败。jump 在「当前步覆盖区间」扫完时被迫迈下一步并刷新覆盖终点。merge_intervals 先按左端排序，再线性合并与末段相交的区间。

def can_jump(nums):
    # 55：能否从下标 0 跳到末尾；nums[i] 为该位置最大跳跃长度
    reach = 0                    # 当前已知最远可达下标
    for i, x in enumerate(nums):
        if i > reach:
            return False         # 走到不可达位置：整体失败
        reach = max(reach, i + x)  # 用本格刷新最远覆盖
    return True                  # 整段扫描未失败即成功

def jump(nums):
    # 45：到达末尾的最少跳跃次数（保证可达）
    end = far = steps = 0        # end=当前步覆盖右端；far=下一步最远；steps=步数
    for i in range(len(nums) - 1):  # 末格无需再跳
        far = max(far, i + nums[i])  # 在覆盖内更新下一跳能到的最远
        if i == end:
            steps += 1           # 覆盖耗尽：必须再跳一次
            end = far            # 新覆盖延伸到 far
    return steps

def merge_intervals(intervals):
    # 56：合并所有重叠区间；输入为 [start, end] 列表
    intervals.sort()             # 默认按左端、再右端排序
    ans = []
    for s, e in intervals:
        if not ans or ans[-1][1] < s:
            ans.append([s, e])   # 与末段不相交：新开一段
        else:
            ans[-1][1] = max(ans[-1][1], e)  # 相交：扩展末段右端
    return ans

回溯

定义

回溯（Backtracking）：在解空间树上 DFS，构造候选解，不合法则撤销（undo）。用于排列、组合、子集、棋盘搜索。

模板：path + 选择列表 + 结束条件；注意去重（排序后同层跳过）。

Python：

▸回溯三件套

共同模式：维护 path，递归前做选择、递归后撤销。全排列用 used 标记下标；子集用 start 保证元素相对次序且每层可跳过；组合总和允许重复选同一下标（dfs(i, ...)），候选先排序以便剪枝。

def permute(nums):
    # 46：全排列；used[i] 标记 nums[i] 是否已在当前 path 中
    ans, path, used = [], [], [False] * len(nums)

    def dfs():
        if len(path) == len(nums):
            ans.append(path[:])  # 拷贝一份，避免后续 pop 污染
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue         # 已选用过的下标
            used[i] = True
            path.append(x)       # 做选择
            dfs()
            path.pop()           # 撤销选择
            used[i] = False

    dfs()
    return ans

def subsets(nums):
    # 78：所有子集（幂集）；start 限制只从右侧选取，避免排列重复
    ans, path = [], []

    def dfs(start):
        ans.append(path[:])      # 每个结点都是合法子集（含空集）
        for i in range(start, len(nums)):
            path.append(nums[i])
            dfs(i + 1)           # 下一层从 i+1 起，元素不可复用
            path.pop()

    dfs(0)
    return ans

def combination_sum(cands, target):
    # 39：组合总和；同一数字可无限次；结果去重靠「只选 ≥ start 的下标」
    cands.sort()                 # 排序后可用「超过剩余即 break」剪枝
    ans, path = [], []

    def dfs(start, left):
        if left == 0:
            ans.append(path[:])  # 剩余为 0：找到一组
            return
        for i in range(start, len(cands)):
            if cands[i] > left:
                break            # 后续更大，无需再试
            path.append(cands[i])
            dfs(i, left - cands[i])  # 传 i 而非 i+1：允许重复本元素
            path.pop()

    dfs(0, target)
    return ans

C / C++： 用数组 path[] 与 used[]，递归参数传递 len；C++ 可用 vector 传引用并 pop_back。

Hot100：17 电话字母；22 括号生成；46 全排列；78/90 子集；39 组合总和；79 单词搜索；131 分割回文。

复杂度：排列 $O(n\cdot n!)$；子集 $O(n\cdot 2^n)$。

P 与 NP

定义

在判定问题（答案为是/否）框架下：

类	英文全称	含义
P	Polynomial time	存在确定性图灵机多项式时间算法
NP	Nondeterministic Polynomial	“是”实例存在多项式长度证据且可在多项式时间验证
NP-Hard	NP-困难	所有 NP 问题可多项式归约到该问题
NP-Complete (NPC)	NP-完全	属于 NP 且为 NP-Hard

关系：$P\subseteq NP$（是否 $P=NP$ 为公开问题）。若任一 NPC 属于 P，则 $P=NP$。

经典 NPC 问题

SAT / 3-SAT、哈密顿回路、团、顶点覆盖、图着色、旅行商判定版、子集和、背包判定版、精确覆盖等。

归约（Reduction）

若问题 $A$ 多项式时间归约到 $B$（$A\le_p B$），则 $B$ 至少与 $A$ 一样难。证明 NPC：证在 NP + 某已知 NPC $\le_p$ 本问题。

应对策略

精确指数算法、近似算法、FPT、启发式、限制特殊图类。数据结构课程侧：理解“为何不用暴力搜索所有排列当 $n$ 大”，以及 DP/贪心适用边界。

▸例 15.1

最短路（非负）在 P（Dijkstra）；最长简单路径为 NPC。二者仅“最长/最短”之别，复杂度天壤。

▸例 15.2

2-SAT $\in$ P（蕴含图强连通）；3-SAT 为 NPC。

Hot100 知识点总表

按《Leetcode Hot100 题解整理》分类，映射到本文结构与核心知识点（检索用）。

数组与哈希

题	知识点
1 两数之和	哈希表一次遍历
15 三数之和	排序 + 双指针 + 去重
11 盛水容器	对撞双指针
3 无重复最长子串	滑动窗口 + 哈希下标
5 最长回文子串	中心扩展 / DP
88 合并有序数组	双指针从后往前
283 移动零	快慢指针
448 消失的数字	原地哈希 / 下标标记
238 除自身乘积	前缀积
48 旋转图像	转置 + 翻转
31 下一个排列	邻项交换字典序
33 搜索旋转数组	二分 + 有序半区
34 查找首末位置	二分边界
75 颜色分类	三路划分

链表

206 反转；21 合并两表；141/142 环与入口；160 相交；19 删倒数 N；2 两数相加；23 合并 K 表（堆）。

字符串

20 括号（栈）；49 异位词分组（哈希）；14 LCP；344/151 反转。

动态规划

70，121，53，198，279，139，300，322，72，1143。

二叉树

94，104，101，102，108，98，236，124，105，103，199，297，230，113，116，257，111，112，543，637，993，563，662，987。

回溯

17，22，46，78，90，39，79，131。

贪心 / 矩阵

55，45，56，57，54，48，240，128。

图

200，207，133，127。

堆

215，347，23。

栈

20，155，739，84，42。

综合计算题

▸题 A 复杂度

1
2
3

for i = 1..n:              # 外层：i 从 1 到 n
  for j = 1..i:            # 中层：j 从 1 到 i，随 i 变长
    for k = 1..100: work() # 内层固定 100 次常数工作

解： $100\cdot\sum_{i=1}^n i=\Theta(n^2)$。

▸题 B 主定理

$T(n)=3T(n/4)+n\log n$。$\log_4 3\approx 0.792$，$f(n)=n\log n=\Omega(n^{0.792+\varepsilon})$，需检验正则性；$a f(n/b)=3\cdot(n/4)\log(n/4)= (3n/4)\log(n/4)$，对大 $n$ 小于 $c n\log n$（$c<1$），情形 3，$T=\Theta(n\log n)$。

▸题 C 二叉树性质

完全二叉树第 $i$ 结点（根为 1）的父、左、右？叶结点下标范围？

解：父 $\lfloor i/2\rfloor$，左 $2i$，右 $2i+1$；叶从 $\lfloor n/2\rfloor+1$ 到 $n$。

▸题 D AVL

最少结点的高度为 3 的 AVL 树有多少结点？（根高计法：高度 0 单结点）

解： $n_h=1+n_{h-1}+n_{h-2}$，$n_0=1,n_1=2$，则 $n_2=4,n_3=7$。高度定义若不同，按教材递推一致即可。

▸题 E 红黑树

证明：红黑树中不存在两条连续红边（性质 4），并说明黑高相同如何限制高度。

解：性质 4 直接禁止红-红；最长路径红黑交替故长度 $\le 2\times$ 最短路径黑结点数，得 $h=O(\log n)$。

▸题 F 堆

证明 Floyd 建堆 $O(n)$（见例 8.1）。另：在大根堆中插入比堆顶大的元素后，比较次数上界？

解：上浮至多 $\lfloor\log_2 n\rfloor$ 次交换/比较量级 $O(\log n)$。

▸题 G 哈希

装填因子 $\alpha=0.75$，拉链法，均匀假设下成功查找平均链探查次数约为？

解：约 $1+\alpha/2=1.375$（具体公式依教材：$1+\alpha/2$ 为常见成功查找期望）。

▸题 H 图

$|V|=n,|E|=m$ 的稀疏图，邻接表 BFS 复杂度？拓扑排序如何判有环？

解： $O(n+m)$；Kahn 算法结束后入队顶点数 $<n$ 则有环。

▸题 I DP

编辑距离 $m=n$，时间空间？如何压空间？

解：时间 $O(n^2)$；空间两行滚动 $O(n)$。

▸题 J P/NP

说明“验证哈密顿回路证书”为何在多项式时间，而“寻找”难。

解：证书为 $n$ 个顶点排列，检查相邻边存在与是否排列即可 $O(n+m)$；搜索空间 $n!$ 无已知多项式算法（NPC）。

复杂度速查

结构/算法	查找	插入	删除	备注
动态数组	$O(n)$ 按值	尾均摊 $O(1)$	$O(n)$	按下标 $O(1)$
单链表	$O(n)$	头 $O(1)$	$O(n)$
栈/队列	—	$O(1)$	$O(1)$
哈希表	均 $O(1)$	均 $O(1)$	均 $O(1)$	最坏 $O(n)$
BST	均 $O(\log n)$	同	同	最坏 $O(n)$
AVL/RB	$O(\log n)$	$O(\log n)$	$O(\log n)$	最坏保证
Splay	均摊 $O(\log n)$	同	同	单次最坏 $O(n)$
二叉堆	最值 $O(1)$	$O(\log n)$	$O(\log n)$	建堆 $O(n)$
Trie	$O(L)$	$O(L)$	$O(L)$
图 BFS/DFS	—	—	—	$O(V+E)$

专题补强

表达式求值（栈）

中缀转后缀（Shunting-yard）后用栈求值；或双栈直接算中缀。

▸后缀（逆波兰）求值

自左向右扫描记号：遇操作数则压栈；遇二元运算符则弹出栈顶两个操作数，先弹出者为右操作数 $b$、后弹出者为左操作数 $a$，将 $a,\mathrm{op},b$ 的结果再压回。扫描结束时栈中仅余最终结果。时间 $O(n)$，辅助栈空间 $O(n)$。除法截断方向依题约定（常见为向零取整）。

Python（后缀求值）：

def eval_rpn(tokens):
    """逆波兰表达式求值：tokens 为字符串列表，如 ["2","1","+","3","*"]。"""
    st = []  # 操作数栈：仅存已算出的中间整数结果
    for t in tokens:
        # 当前记号为四则运算符之一（题设操作数不以纯 "+"/"-" 等形式出现）
        if t in '+-*/':
            # 先弹出的是右操作数 b，后弹出的是左操作数 a（栈顶靠近运算符右侧）
            b, a = st.pop(), st.pop()
            if t == '+':
                st.append(a + b)           # 加法：a + b
            elif t == '-':
                st.append(a - b)           # 减法：左减右，顺序不可颠倒
            elif t == '*':
                st.append(a * b)           # 乘法
            else:
                # 除法：Python3 的 / 得浮点，再 int() 向零截断，贴近多数 OJ 约定
                st.append(int(a / b))
        else:
            # 非运算符：视为整数字面量，压入操作数栈
            st.append(int(t))
    # 合法表达式结束时栈中恰有一个元素，即求值结果
    return st[-1]

C：

#include <string.h>  /* strcmp */
#include <stdlib.h>  /* atoi */

/* tokens：长度为 n 的 C 字符串数组；返回逆波兰求值结果 */
int evalRPN(char** tokens, int n) {
    int st[10000], top = -1;  /* 手写栈：st[0..top] 为有效区；top==-1 表示空 */
    for (int i = 0; i < n; i++) {
        char *t = tokens[i];
        /* 下列空块仅作「单字符算符」示意；负数与算符冲突时需按题保证或另写判定 */
        if (t[1]=='\0' && (t[0]=='+'||t[0]=='-'||t[0]=='*'||t[0]=='/') && !(t[0]=='-' && t[1])) {
            /* 单字符运算符；实际需区分负数，竞赛中按题输入保证 */
        }
        /* 教学实现：用 strcmp 精确匹配四则字符串 */
        if (!strcmp(t,"+")||!strcmp(t,"-")||!strcmp(t,"*")||!strcmp(t,"/")) {
            /* 弹出右操作数 b、左操作数 a；top-- 为出栈 */
            int b = st[top--], a = st[top--];
            if (!strcmp(t,"+")) st[++top]=a+b;       /* 先 ++top 再写入，等价压栈 */
            else if (!strcmp(t,"-")) st[++top]=a-b;  /* 左减右 */
            else if (!strcmp(t,"*")) st[++top]=a*b;
            else st[++top]=a/b;                      /* C 整除：向零截断（C99 起） */
        } else {
            /* 操作数字符串 → 整数后压栈 */
            st[++top]=atoi(t);
        }
    }
    return st[top];  /* 栈顶即为最终值；调用方应保证表达式合法 */
}

C++： std::stack<long>，tokens 为 vector<string>，逻辑同 Python。

单调栈：接雨水与柱状图

接雨水（42） 按行/按列/单调栈/双指针。单调栈法：维护高度递增下标栈，凹槽面积累加。

▸单调栈接雨水与柱状图

接雨水： 栈中下标对应高度严格递增。当当前柱 $h[i]$ 高于栈顶柱时，栈顶可作为凹槽底；再取新栈顶为左壁、$i$ 为右壁，横宽为 $i-\mathrm{left}-1$，高为 $\min(h[\mathrm{left}],h[i])-\mathrm{bottom}$，累加到答案。每个下标至多入出栈一次，时间 $O(n)$。

柱状图最大矩形： 两端加高度 0 哨兵后，维护高度严格递增的下标栈。当 $h[i]$ 小于栈顶高度时，弹出柱 $j$ 作为矩形高，右边界为 $i$、左边界为新栈顶，宽为 $i-\mathrm{st.top}-1$，更新全局最大面积。

Python：

def trap(height):
    """接雨水：单调递增下标栈，按「凹槽底」逐层累加可接水量。"""
    st, ans = [], 0  # st：下标栈；ans：累计接水格数
    for i, h in enumerate(height):
        # 当前柱高于栈顶柱 → 栈顶可作底，被左右更高柱夹住形成凹槽
        while st and h > height[st[-1]]:
            bottom = height[st.pop()]  # 弹出凹槽底的高度
            if not st:
                break  # 左侧无壁，无法形成封闭凹槽
            left = st[-1]  # 新栈顶为左壁下标
            # 高：左右壁较矮者减去底；宽：左右壁之间的空档格数
            ans += (min(height[left], h) - bottom) * (i - left - 1)
        st.append(i)  # 当前下标入栈，保持栈内高度非降/递增态势
    return ans

def largest_rectangle(heights):
    """柱状图中最大矩形（84）：两端哨兵简化边界处理。"""
    # 左右各补高度 0：保证所有真实柱最终都会被弹出并参与面积计算
    h = [0] + heights + [0]
    st, ans = [], 0  # st：下标单调递增（对应高度）；ans：历史最大面积
    for i, x in enumerate(h):
        # 当前高度 x 小于栈顶柱高 → 栈顶柱不能再向右延伸，结算以其为高的最大矩形
        while st and h[st[-1]] > x:
            j = st.pop()  # j：作为矩形高度的那根柱下标
            # 右边界为 i，左边界为新栈顶；宽 = i - st[-1] - 1
            ans = max(ans, h[j] * (i - st[-1] - 1))
        st.append(i)  # 下标入栈，维持 h[st] 严格递增
    return ans

C++：

// 接雨水：逻辑同 Python 版 trap；stack 存下标
int trap(vector<int>& height) {
    stack<int> st;   // 单调递增下标栈
    int ans = 0;     // 累计接水量
    for (int i = 0; i < (int)height.size(); ++i) {
        // 当前柱更高：弹出凹槽底并与左壁、右壁（i）结算一层水
        while (!st.empty() && height[i] > height[st.top()]) {
            int bottom = height[st.top()]; st.pop();  // 凹槽底高度
            if (st.empty()) break;                    // 无左壁则无法蓄水
            int left = st.top();                      // 左壁下标
            // 面积 = 高度差 × 左右壁之间空档宽度
            ans += (min(height[left], height[i]) - bottom) * (i - left - 1);
        }
        st.push(i);  // 当前下标入栈
    }
    return ans;
}

C：用数组模拟栈即可，复杂度均为 $O(n)$ 时间、$O(n)$ 空间。

Dijkstra（非负权最短路）

▸堆优化 Dijkstra

维护 $dist[v]$ 为源点到 $v$ 的当前最短路上界。优先队列每次取出 $dist$ 最小的顶点 $u$ 做松弛：对邻边 $(u,v,w)$，若 $dist[v]>dist[u]+w$ 则更新并重新入堆。允许同一顶点多次入堆，弹出时若 $d>dist[u]$ 则丢弃陈旧记录。要求边权非负；时间 $O((V+E)\log V)$（二叉堆）。

Python：

import heapq
from collections import defaultdict

def dijkstra(n, edges, src):
    """
    非负权有向图单源最短路。
    n：顶点数（编号 0..n-1）；edges：边列表 (u,v,w)；src：源点。
    返回 dist 数组；不可达保持 +inf。
    """
    g = defaultdict(list)  # 邻接表：g[u] = [(v, w), ...]
    for u, v, w in edges:
        g[u].append((v, w))  # 有向边 u→v 权 w；无向图需再追加 (u,w) 到 g[v]
    dist = [float('inf')] * n  # 最短路上界，初值无穷大
    dist[src] = 0              # 源点到自身距离为 0
    pq = [(0, src)]            # 小根堆元素：(当前距离估计, 顶点)
    while pq:
        d, u = heapq.heappop(pq)  # 取出当前堆中距离最小的记录
        if d > dist[u]:
            continue  # 陈旧条目：u 已有更优 dist，跳过
        for v, w in g[u]:
            # 松弛：经 u 到 v 是否更短
            if dist[v] > d + w:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))  # 新估计入堆（可存多份）
    return dist  # O((V+E) log V)

C++：

// g：邻接表，g[u] 存 {v, w}；返回各点最短路（不可达为 INF）
vector<long long> dijkstra(int n, vector<vector<pair<int,int>>>& g, int src) {
    const long long INF = 1e18;           // 足够大的「无穷」哨兵
    vector<long long> dist(n, INF);       // 最短路上界
    // greater<>：小顶堆，按 pair 第一关键字（距离）升序
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    dist[src]=0; pq.push({0, src});       // 源点初始化
    while (!pq.empty()) {
        auto [d,u]=pq.top(); pq.pop();    // 取出当前最小距离记录
        if (d > dist[u]) continue;        // 陈旧记录直接丢弃
        for (auto [v,w]: g[u]) if (dist[v] > d + w) {
            dist[v]=d+w;                  // 松弛成功
            pq.push({dist[v], v});        // 压入新估计
        }
    }
    return dist;
}

C：邻接表 + 手写二叉堆，或稠密图用 $O(V^2)$ 数组版 Dijkstra。

Kruskal MST

▸Kruskal 最小生成树

将边按权升序排列，依次尝试加入：若两端点尚不连通（并查集 union 成功），则纳入 MST，否则丢弃以免成环。至多取 $n-1$ 条边即可停止。正确性依赖贪心选择性质；时间主导项为排序 $O(E\log E)$，并查集近似 $O(E\alpha(n))$。

def kruskal(n, edges):
    """
    Kruskal 最小生成树。
    n：顶点数；edges：边列表，每项 (w, u, v) 表示权 w 的无向边。
    返回 (总权值, MST 边列表)；图不连通时边数会少于 n-1。
    """
    # edges: (w,u,v)
    edges = sorted(edges)  # 按权升序；元组首元素为 w，直接 sorted 即可
    dsu = DSU(n)           # 并查集：判定两点是否已在同一连通分量（见前文）
    mst, total = [], 0     # mst：选中边；total：权值和
    for w, u, v in edges:
        # union 成功表示原先不连通，加入该边不会成环
        if dsu.union(u, v):
            mst.append((u, v, w))
            total += w
            # 树有 n-1 条边即生成树完成，可提前结束
            if len(mst) == n - 1:
                break
    return total, mst  # O(E log E)

递归与时间空间

递归式除主定理外，可用展开法、树图法、Akra-Bazzi。空间复杂度含递归栈深度：平衡递归 $O(\log n)$，链状 $O(n)$。尾递归可优化为迭代（视语言与编译器）。

▸题 K 递归空间

归并排序辅助数组 $O(n)$，递归深度 $O(\log n)$，总空间 $O(n)$。快排期望栈深 $O(\log n)$，最坏 $O(n)$（可通过与较短边优先递归改善）。

稀疏矩阵

三元组顺序表 (row, col, val) 或行逻辑链接。转置、加法、乘法注意复杂度与稠密矩阵 $O(n^3)$ 乘法的对比；极度稀疏时链表/哈希存非零元。

线索二叉树要点

利用空指针域存放中序前驱/后继线索，加 ltag/rtag 区分孩子与线索。中序遍历可 $O(1)$ 辅助空间完成（相对显式栈）。

数据结构选型

需求	倾向
随机下标访问	数组 / vector
任意位置频繁插入删除	链表（实际缓存差，常不如 vector）
端点操作	栈 / 队列 / deque
关键字查找	哈希（无序）/ 平衡树（有序）
动态最值 / TopK	堆
前缀匹配	Trie
区间最值（静态）	ST 表；动态 → 线段树 / 树状数组
连通分量合并	并查集
外存有序索引	B+ 树

补充计算题

▸题 L Splay 均摊直觉

为何 Zig-Zig 先转祖父再转父，而非两次单旋到根？

解：该顺序使势能下降更显著，保证均摊 $O(\log n)$；若只用 Zig 到根，均摊界会变坏。

▸题 M 哈希最坏

开放定址 $\alpha\to 1$ 时查找如何退化？拉链法如何缓解？

解：探测序列变长，接近 $O(n)$；拉链可在长链改用 BST/RB（Java 8 HashMap），或再散列降低 $\alpha$。

▸题 N 0-1 背包

$n=3$，$W=5$，$(w,v)= (2,3),(3,4),(4,5)$。$dp$ 一维逆序更新最终最优值？

解：最优为物品 1+2：$w=5,v=7$。

▸题 O 拓扑

课程数 4，先修 [[1,0],[2,0],[3,1],[3,2]]。一种合法修课顺序？

解：如 $0,1,2,3$ 或 $0,2,1,3$（Kahn 多解）。

三语言对照备忘

结构	Python	C	C++
动态数组	`list`	自写 / 可变长数组	`vector`
栈	`list` append/pop	数组+top	`stack`
队列	`deque`	循环数组	`queue` / `deque`
哈希	`dict` / `set`	自写链地址	`unordered_map` / `set`
有序映射	`SortedDict` 等	自写 BST/RB	`map` / `set`
堆	`heapq`	自写	`priority_queue`
链表/树题	自定义 class	struct + 指针	struct / 智能指针

刷题时以 Python 快速验证思路，用 C/C++ 练指针与复杂度常数；课程作业常要求 C 手写结构体实现。

复习路线

线性结构与复杂度记号 → 栈队列应用（括号、单调栈）
哈希 + 双指针 + 滑动窗口（Hot100 数组篇）
链表题型套路 → 二叉树遍历与递归树 DP
BST → AVL/RB/Splay 性质题 → 堆与 TopK
图 BFS/DFS/拓扑 → 并查集
分治与主定理计算题 → DP 状态设计 → 贪心证明意识 → P/NP 概念
对照本文 Hot100 总表查漏，详解见 Leetcode100 专文

本文与《排序算法详解》《Leetcode Hot100 题解整理》互补：结构与理论以本文为准，排序细节与逐题题解见另两文。

秋月春风

明月守灯寻长梦，梦长寻灯守月明

明月守灯寻长梦，梦长寻灯守月明

秋月春风

总览

索引

绪论

定义

逻辑结构与存储结构

渐进记号

时间与空间复杂度

计算题：复杂度判定

数组

定义

操作与复杂度

代码：动态数组扩容思想

使用示例与 Hot100 映射

链表

定义

操作与复杂度

代码：单链表基本操作

经典技巧（Hot100）

栈

定义

操作与复杂度

代码

应用

队列

定义

操作与复杂度

代码：循环队列

Hot100 相关

哈希表

定义

冲突处理

代码：拉链法示意

Hot100 映射

字符串技巧

树与二叉树

定义

基本性质

存储

遍历

代码：结点与遍历

Hot100 二叉树题型归类

二叉搜索树

定义

操作与复杂度

代码

AVL 树

定义

旋转

代码：旋转与插入

复杂度

红黑树

定义

与 AVL 对比

插入修复概要

代码

Splay 树

定义

伸展

复杂度

代码骨架

堆与优先队列

定义

操作与复杂度

代码：小根堆

使用示例

Hot100

哈夫曼树与 Trie

哈夫曼树

Trie（字典树）

B 树与 B+ 树

定义

图

定义

存储

遍历

代码：邻接表 DFS/BFS