数据结构从零到一

21 章完整教程 · 从数组到图论 · 从零基础到面试通关

零基础友好 · 每个概念都讲透 · 配有生活类比 · 全程 Python 代码 · 涵盖排序/查找/DP/贪心/回溯 · 含高级数据结构 · 面试题实战

第一章:开篇——为什么要学数据结构?

1.1 什么是数据结构?

一句话:数据结构就是数据的"摆放方式"。同样的数据,摆放方式不同,操作效率天差地别。

类比:数据结构 = 收纳方式

想象你有一堆衣服要收纳:

• 随手扔进衣柜 → 找某件衣服要翻半天(无结构)
• 按季节叠好分层放 → 很快就能找到(有序结构)
• 按颜色挂起来 → 一目了然(索引结构)

数据结构就是决定"数据怎么放",从而决定"查找/插入/删除有多快"。

1.2 数据结构 vs 算法

数据结构是"数据怎么存",算法是"数据怎么算"。两者密不可分:

数据结构 + 算法 = 程序 举例:在通讯录中查找一个人 数据结构选择:数组 → 需要逐个遍历(慢) 数据结构选择:哈希表 → 直接定位(快) 同样的"查找"算法,数据结构不同,效率完全不同!
对比数据结构算法
关注点数据怎么存、怎么组织数据怎么处理、怎么算
类比仓库的货架布局取货/发货的流程
例子数组、链表、树、图排序、搜索、动态规划

1.3 学了能干嘛?

1
面试敲门砖——大厂面试几乎必考数据结构与算法。LeetCode 上 2000+ 题目,核心就是数据结构。
2
写出高效程序——选对数据结构,程序速度可能差 1000 倍。数据库索引用 B+ 树、缓存用哈希表、任务调度用堆……
3
理解底层原理——Python 的 list 底层是动态数组、dict 底层是哈希表。懂了数据结构,你就懂了它们为什么快。
4
培养算法思维——遇到问题时能想到"该用什么结构来组织数据",这是程序员的核心能力。

1.4 学习路线图

第1-2章
基础概念什么是数据结构 + 时间复杂度(约 2 小时)
第3-6章
线性结构数组、链表、栈、队列(约 4 小时)
第7章
哈希表哈希函数、冲突处理(约 2 小时)
第8-11章
树与堆二叉树、BST、平衡树、堆(约 5 小时)
第12-13章
图论图的表示、DFS、BFS、最短路径(约 4 小时)
第14-18章
经典算法排序、查找、分治、贪心、回溯(约 5 小时)
第19-21章
进阶与实战动态规划、高级数据结构、面试题(约 6 小时)
预计总时长:35-40 小时 每天学 2 小时,大约 3 周可以完成。每个数据结构都配有完整 Python 代码实现,建议自己敲一遍运行。

1.5 本章小结

本章要点回顾 • 数据结构 = 数据的组织方式,决定操作效率
• 数据结构 + 算法 = 程序
• 学数据结构 = 面试通关 + 写出高效代码 + 理解底层原理
• 本教程用 Python 讲解,零基础友好

第二章:前置知识——时间复杂度与大O

2.1 为什么需要时间复杂度?

同一段逻辑,用不同写法,运行时间可能差几万倍。我们需要一种方式来衡量算法的快慢,而不依赖于具体的电脑。

类比:时间复杂度 = 考试评分标准

判断一个算法好不好,不能靠"感觉快不快",得有一个标准。时间复杂度就是这个标准——它告诉你:当数据量变大时,运行时间会怎样变化?

2.2 大 O 表示法

常见时间复杂度(从快到慢): O(1) 常数时间 —— 不管数据多大,时间都一样 O(log n) 对数时间 —— 数据翻倍,时间只多一步 O(n) 线性时间 —— 数据翻倍,时间翻倍 O(n log n) 线性对数 —— 比线性稍慢一点 O(n^2) 平方时间 —— 数据翻倍,时间变 4 倍 O(2^n) 指数时间 —— 数据每多 1,时间翻倍 O(n!) 阶乘时间 —— 恐怖的增长速度
大 O 的直觉理解

假设 n = 1000:

• O(1) = 1 次操作
• O(log n) ≈ 10 次操作
• O(n) = 1000 次操作
• O(n log n) ≈ 10000 次操作
• O(n^2) = 1,000,000 次操作

差距一目了然!这就是为什么选对算法那么重要。

2.3 常见复杂度分析

O(1) —— 常数时间
# 无论列表多长,取第一个元素都是 O(1)
lst = [3, 1, 4, 1, 5, 9, 2, 6]
first = lst[0]  # O(1)

# 字典查找也是 O(1)
d = {"name": "Alice", "age": 25}
print(d["name"])  # O(1)
O(n) —— 线性时间
# 遍历列表 O(n)
lst = [3, 1, 4, 1, 5, 9, 2, 6]
total = 0
for x in lst:      # O(n)
    total += x
O(n^2) —— 平方时间
# 双重循环 O(n^2)
lst = [3, 1, 4, 1, 5, 9, 2, 6]
n = len(lst)
for i in range(n):
    for j in range(n):    # n * n = n^2
        pass
O(log n) —— 对数时间
# 二分查找:每次排除一半数据
def binary_search(lst, target):
    left, right = 0, len(lst) - 1
    while left <= right:
        mid = (left + right) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 1000 个数据最多查 10 次 (log2(1000) ≈ 10)
# 1000000 个数据最多查 20 次

2.4 空间复杂度

空间复杂度含义例子
O(1)只用固定几个变量交换两个变量
O(n)需要一个和输入等大的数组复制一个列表
O(log n)递归调用栈的深度二分查找的递归版
三种情况 • 最好情况:运气最好的时候
• 最坏情况:运气最差的时候——我们通常关注这个
• 平均情况:期望的平均表现

2.5 本章小结

本章要点回顾 • 时间复杂度用大 O 表示法,描述算法随数据量增长的趋势
• 常见复杂度:O(1) < O(log n) < O(n) < O(n log n) < O(n^2)
• 空间复杂度衡量额外内存使用
• 通常关注最坏情况的时间复杂度

第三章:数组——最基础的数据结构

3.1 什么是数组?

数组是一段连续的内存空间,里面存放相同类型的数据。

类比:数组 = 电影院的一排座位

电影院一排有 10 个座位,编号 0 到 9:

• 每个座位放一个人(元素)
• 座位是连续的(内存连续)
• 你知道编号就能直接找到对应座位(随机访问 O(1))
• 中间插入一个人?后面所有人都要往后挪(插入 O(n))

数组的内存布局: 地址: 1000 1004 1008 1012 1016 +-----+-----+-----+-----+-----+ | 3 | 1 | 4 | 1 | 5 | +-----+-----+-----+-----+-----+ 下标: 0 1 2 3 4 访问 arr[3]:地址 = 1000 + 3 * 4 = 1012 → O(1)

3.2 数组的基本操作与复杂度

操作时间复杂度说明
访问(按索引)O(1)直接计算地址
查找(按值)O(n)最坏遍历整个数组
尾部插入O(1)*直接放到末尾
中间插入O(n)后面的元素都要后移
删除O(n)后面的元素都要前移

3.3 Python 中的数组:list

数组基本操作
# 创建数组
arr = [3, 1, 4, 1, 5, 9, 2, 6]

# 访问 O(1)
print(arr[0])   # 3
print(arr[3])   # 1

# 查找 O(n)
idx = arr.index(5)  # 找到 5 的下标

# 尾部插入 O(1)
arr.append(7)

# 中间插入 O(n)
arr.insert(2, 99)   # 在下标 2 处插入

# 删除 O(n)
arr.remove(99)      # 删除第一个值为 99 的元素
del arr[0]          # 删除下标 0 的元素

# 遍历 O(n)
for x in arr:
    print(x, end=" ")

3.4 动态数组的原理

动态数组扩容过程: 初始:容量=4, 长度=0 [_, _, _, _] 插入 4 个元素后满了: [3, 1, 4, 1] 再插入一个 → 触发扩容(容量翻倍) 申请新空间(容量=8),复制旧数据 [3, 1, 4, 1, 5, _, _, _] 扩容代价 O(n),但均摊下来每次插入还是 O(1)
为什么容量翻倍而不是加 1? 如果每次只加 1,每次插入都要扩容,总时间 O(n^2)。翻倍扩容:n 次插入最多触发 log n 次扩容,均摊 O(1)。这是空间换时间的经典策略。

3.5 经典题目:两数之和

暴力解法 O(n^2) vs 哈希优化 O(n)
# 暴力解法 O(n^2)
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

# 哈希优化 O(n)
def two_sum_hash(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

print(two_sum_hash([2, 7, 11, 15], 9))  # [0, 1]

3.6 本章小结

本章要点回顾 • 数组是连续内存,支持 O(1) 随机访问
• 插入/删除需要移动元素,O(n)
• Python list 是动态数组,自动扩容(容量翻倍)
• 数组适合频繁读取、少修改的场景

第四章:链表——灵活的链条

4.1 什么是链表?

链表是一种不需要连续内存的数据结构。每个节点包含数据和指向下一个节点的指针。

类比:链表 = 寻宝游戏

想象一个寻宝游戏:第一个线索告诉你"去公园长椅下面找",长椅下面有纸条"去图书馆第三排书架"……每条线索都知道下一条在哪里,串成一整条链。你必须从头开始,一个一个跟下去。

单链表结构: head v +---+--> +---+--> +---+--> +---+--> None | 3 | | 1 | | 4 | | 1 | +---+ +---+ +---+ +---+ 每个节点 = 数据 + 指向下一个节点的指针

4.2 链表 vs 数组

对比数组链表
内存连续分散
随机访问O(1)O(n)
头部插入O(n)O(1)
尾部插入O(1)O(n) 或 O(1)
删除O(n)O(1)*
缓存友好好差

4.3 实现单链表

Python 实现单链表
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, val):
        """头部插入 O(1)"""
        self.head = ListNode(val, self.head)

    def append(self, val):
        """尾部插入 O(n)"""
        node = ListNode(val)
        if not self.head:
            self.head = node
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = node

    def delete(self, val):
        """删除第一个值为 val 的节点"""
        dummy = ListNode(0, self.head)
        prev, cur = dummy, self.head
        while cur:
            if cur.val == val:
                prev.next = cur.next
                break
            prev, cur = cur, cur.next
        self.head = dummy.next

    def display(self):
        parts = []
        cur = self.head
        while cur:
            parts.append(str(cur.val))
            cur = cur.next
        print(" -> ".join(parts) + " -> None")

ll = LinkedList()
ll.append(3); ll.append(1); ll.append(4)
ll.display()  # 3 -> 1 -> 4 -> None
ll.prepend(0)
ll.display()  # 0 -> 3 -> 1 -> 4 -> None

4.4 经典题目

反转链表(面试高频)
def reverse_list(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev
检测环(快慢指针)
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

4.5 本章小结

本章要点回顾 • 链表是非连续存储,通过指针串联
• 插入/删除 O(1)(已知位置时),查找 O(n)
• 哨兵节点(dummy node)简化边界处理
• 快慢指针是链表题的经典技巧

第五章:栈——后进先出

5.1 什么是栈?

栈是一种后进先出(LIFO)的数据结构。只能从一端(栈顶)进行插入和删除。

类比:栈 = 一摞盘子

食堂里一摞盘子:放盘子只能放在最上面(push),取盘子只能从最上面拿(pop)。最后放上去的,最先被取走——后进先出。

5.2 用 Python 实现栈

# Python 的 list 天然支持栈操作
stack = []
stack.append(1)   # 入栈 O(1)
stack.append(2)
stack.append(3)
print(stack.pop())  # 出栈 → 3(后进先出)
print(stack[-1])    # 查看栈顶 → 2

5.3 经典应用:括号匹配

def is_valid(s):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for c in s:
        if c in "([{":
            stack.append(c)
        elif c in ")]}":
            if not stack or stack[-1] != pairs[c]:
                return False
            stack.pop()
    return len(stack) == 0

print(is_valid("({[]})"))  # True
print(is_valid("([)]"))    # False

5.4 经典应用:用栈实现计算器

def eval_rpn(tokens):
    """逆波兰表达式求值(后缀表达式)"""
    stack = []
    for t in tokens:
        if t in "+-*/":
            b, a = stack.pop(), stack.pop()
            if t == "+": stack.append(a + b)
            elif t == "-": stack.append(a - b)
            elif t == "*": stack.append(a * b)
            else: stack.append(int(a / b))
        else:
            stack.append(int(t))
    return stack[0]

# "2 1 + 3 *" = (2+1) * 3 = 9
print(eval_rpn(["2", "1", "+", "3", "*"]))  # 9

5.5 本章小结

本章要点回顾 • 栈 = 后进先出(LIFO),只能操作栈顶
• push/pop/peek 都是 O(1)
• 经典应用:括号匹配、表达式求值、DFS、撤销操作

第六章:队列——先来先排队

6.1 什么是队列?

队列是一种先进先出(FIFO)的数据结构。从队尾入队,从队头出队。

类比:队列 = 排队买奶茶

新来的人排到队尾(enqueue),队头的人先买到离开(dequeue)。先来的先走——先进先出。

6.2 用 Python 实现队列

from collections import deque

queue = deque()
queue.append("Alice")    # 入队 O(1)
queue.append("Bob")
queue.append("Charlie")
print(queue.popleft())   # 出队 O(1) → Alice
print(queue.popleft())   # → Bob
为什么用 deque 而不是 list? Python 的 list.pop(0) 是 O(n)(所有元素前移)。deque.popleft() 才是 O(1)。队列用 deque,不要用 list!

6.3 循环队列

循环队列用数组实现,让首尾相连,充分利用空间:

class CircularQueue:
    """用数组实现的循环队列"""
    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.capacity = capacity
        self.front = 0
        self.rear = 0
        self.count = 0

    def enqueue(self, item):
        if self.count == self.capacity:
            raise Exception("队列已满")
        self.queue[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity  # 循环
        self.count += 1

    def dequeue(self):
        if self.count == 0:
            raise Exception("队列为空")
        item = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity  # 循环
        self.count -= 1
        return item

cq = CircularQueue(5)
cq.enqueue(1); cq.enqueue(2); cq.enqueue(3)
print(cq.dequeue())  # 1
print(cq.dequeue())  # 2

6.4 优先队列

优先队列(用堆实现)
import heapq

pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 4)
print(heapq.heappop(pq))  # 1(最小的先出)

6.5 本章小结

本章要点回顾 • 队列 = 先进先出(FIFO)
• Python 用 deque 实现 O(1) 入出队
• 循环队列用数组实现,首尾相连
• 优先队列按优先级出队,用堆实现

第七章:哈希表——闪电般的查找

7.1 什么是哈希表?

哈希表通过一个哈希函数把键映射到数组下标,实现 O(1) 的查找、插入和删除。

类比:哈希表 = 图书馆索引系统

图书馆有 100 万个座位,找"张三":
• 没有索引:从第 1 个开始一个一个找 → O(n)
• 有索引:算一下姓氏笔画 → 直接走到第 38 号书架 → O(1)

7.2 哈希冲突

两个不同的键可能映射到同一个位置——这叫哈希冲突。

方法原理优点缺点
链地址法冲突位置挂链表简单,负载因子可 > 1链表长了变慢
开放寻址法冲突了找下一个空位缓存友好负载因子不能太高

7.3 哈希函数的实现

手写一个简单的哈希表(链地址法)
class SimpleHashTable:
    """用链地址法解决冲突的哈希表"""
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]

    def _hash(self, key):
        """哈希函数:把 key 映射到桶下标"""
        return hash(key) % self.capacity

    def put(self, key, value):
        idx = self._hash(key)
        bucket = self.buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # 更新
                return
        bucket.append((key, value))  # 新增
        self.size += 1
        # 负载因子超过阈值时扩容
        if self.size > self.capacity * 0.75:
            self._resize()

    def get(self, key):
        idx = self._hash(key)
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        raise KeyError(key)

    def delete(self, key):
        idx = self._hash(key)
        bucket = self.buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return
        raise KeyError(key)

    def _resize(self):
        """扩容:容量翻倍,重新哈希所有元素"""
        old_buckets = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)

# 使用示例
ht = SimpleHashTable()
ht.put("apple", 1); ht.put("banana", 2); ht.put("cherry", 3)
print(ht.get("apple"))   # 1
ht.delete("banana")
print(ht.size)           # 2

7.4 开放寻址法实现

线性探测法(Linear Probing)
class OpenAddressHashTable:
    """开放寻址法(线性探测)解决冲突"""
    EMPTY = object()     # 空标记
    DELETED = object()   # 已删除标记

    def __init__(self, capacity=16):
        self.capacity = capacity
        self.keys = [self.EMPTY] * capacity
        self.values = [self.EMPTY] * capacity
        self.size = 0

    def _hash(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        if self.size > self.capacity * 0.5:  # 负载因子不能太高
            self._resize()
        idx = self._hash(key)
        while self.keys[idx] is not self.EMPTY:
            if self.keys[idx] == key:
                self.values[idx] = value  # 更新
                return
            idx = (idx + 1) % self.capacity  # 线性探测:找下一个
        self.keys[idx] = key
        self.values[idx] = value
        self.size += 1

    def get(self, key):
        idx = self._hash(key)
        while self.keys[idx] is not self.EMPTY:
            if self.keys[idx] == key:
                return self.values[idx]
            idx = (idx + 1) % self.capacity
        raise KeyError(key)

    def _resize(self):
        old_keys, old_values = self.keys, self.values
        self.capacity *= 2
        self.keys = [self.EMPTY] * self.capacity
        self.values = [self.EMPTY] * self.capacity
        self.size = 0
        for k, v in zip(old_keys, old_values):
            if k is not self.EMPTY:
                self.put(k, v)

7.5 Python 中的哈希表

# dict 和 set 都是哈希表
d = {"apple": 1, "banana": 2}
print(d["apple"])     # O(1) 查找
d["cherry"] = 3       # O(1) 插入

s = {1, 2, 3}
s.add(4)              # O(1)
print(3 in s)         # O(1) 查找

# 注意:只有可哈希的类型才能做键
# 可哈希:int, str, tuple
# 不可哈希:list, dict, set

# 自定义对象做键:需要实现 __hash__ 和 __eq__
class Point:
    def __init__(self, x, y):
        self.x = x; self.y = y
    def __hash__(self):
        return hash((self.x, self.y))
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

d = {Point(1, 2): "A", Point(3, 4): "B"}
print(d[Point(1, 2)])  # "A"

7.6 经典题:字母异位词分组

LeetCode 49 - 将字母异位词分在同一组
from collections import defaultdict

def group_anagrams(strs):
    """字母异位词分组"""
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))  # 排序后作为 key
        groups[key].append(s)
    return list(groups.values())

print(group_anagrams(["eat","tea","tan","ate","nat","bat"]))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]

# 优化:用字母计数作为 key,避免排序 O(m log m)
def group_anagrams_v2(strs):
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        groups[tuple(count)].append(s)
    return list(groups.values())

7.7 经典题:最长连续序列

LeetCode 128 - O(n) 解法
def longest_consecutive(nums):
    """找出最长连续序列的长度"""
    num_set = set(nums)
    best = 0
    for num in num_set:
        # 只从序列起点开始计数
        if num - 1 not in num_set:
            length = 1
            while num + length in num_set:
                length += 1
            best = max(best, length)
    return best

print(longest_consecutive([100, 4, 200, 1, 3, 2]))  # 4 (1,2,3,4)

7.8 本章小结

本章要点回顾 • 哈希表通过哈希函数实现 O(1) 查找/插入/删除
• 哈希冲突用链地址法或开放寻址法解决
• 负载因子过高时需要扩容(重新哈希)
• Python 的 dict 和 set 都是哈希表
• 自定义对象做键需要实现 __hash__ 和 __eq__
• 哈希表是用空间换时间的典范

第八章:树与二叉树

8.1 什么是树?

树是一种层次结构的数据结构。就像一棵倒着的树,根在上面,叶子在下面。

类比:树 = 公司组织架构

CEO 是根节点,各部门总监是子节点,普通员工是叶子节点。每个人只有一个直接上级,但可以有多个下属。

二叉树示例: 1 根节点:1 / \ 叶子节点:4, 5, 3 2 3 深度:0(根) → 1 → 2 / \ 4 5 前序遍历(根左右):1, 2, 4, 5, 3 中序遍历(左根右):4, 2, 5, 1, 3 后序遍历(左右根):4, 5, 2, 3, 1 层序遍历(逐层) :1, 2, 3, 4, 5

8.2 二叉树的遍历

递归实现三种遍历
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(root):
    """前序:根->左->右"""
    if not root: return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):
    """中序:左->根->右"""
    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]

from collections import deque
def level_order(root):
    """层序遍历(BFS)"""
    if not root: return []
    result, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return result

8.3 递归思维

树的递归定义 一棵二叉树 = 根节点 + 左子树 + 右子树。左子树和右子树本身也是二叉树——这就是递归!
处理树的问题 99% 用递归:终止条件 → 处理当前 → 递归子树。
求树的高度
def max_depth(root):
    if not root: return 0
    return max(max_depth(root.left), max_depth(root.right)) + 1

8.4 本章小结

本章要点回顾 • 树是层次结构,二叉树每个节点最多两个子节点
• 四种遍历:前序、中序、后序、层序
• 树的问题几乎都用递归解决

第九章:二叉搜索树(BST)

9.1 BST 的性质

二叉搜索树的核心性质:左子树所有节点 < 根 < 右子树所有节点。

类比:BST = 猜数字游戏

在 1~100 之间猜数字:猜 50,说"大了"→ 只需在 1~49 中继续猜。每次排除一半——这就是 BST 查找的思路!

BST 示例: 8 / \ 3 10 / \ \ 1 6 14 中序遍历(有序):1, 3, 6, 8, 10, 14

9.2 BST 的操作

def search_bst(root, target):
    """查找 O(log n) 平均"""
    if not root: return None
    if target == root.val: return root
    if target < root.val: return search_bst(root.left, target)
    return search_bst(root.right, target)

def insert_bst(root, val):
    """插入 O(log n) 平均"""
    if not root: return TreeNode(val)
    if val < root.val: root.left = insert_bst(root.left, val)
    elif val > root.val: root.right = insert_bst(root.right, val)
    return root

def delete_bst(root, val):
    """删除 BST 中值为 val 的节点(三种情况)"""
    if not root: return None
    if val < root.val:
        root.left = delete_bst(root.left, val)
    elif val > root.val:
        root.right = delete_bst(root.right, val)
    else:
        # 找到目标节点,分三种情况
        # 情况1:叶子节点 → 直接删除
        if not root.left and not root.right:
            return None
        # 情况2:只有一个子节点 → 用子节点替换
        if not root.left: return root.right
        if not root.right: return root.left
        # 情况3:有两个子节点 → 找右子树最小值替换
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val = successor.val
        root.right = delete_bst(root.right, successor.val)
    return root

# 演示
root = None
for v in [8, 3, 10, 1, 6, 14]:
    root = insert_bst(root, v)
root = delete_bst(root, 3)  # 删除节点 3
BST 的致命缺陷:可能退化成链表 如果按顺序插入 1, 2, 3, 4, 5,BST 变成一条链,所有操作都变成 O(n)。解决方案:平衡二叉树。

9.3 本章小结

本章要点回顾 • BST 性质:左 < 根 < 右,中序遍历有序
• 查找/插入/删除平均 O(log n)
• 删除三种情况:叶子直接删、单子替换、双子找后继
• 缺点:可能退化成链表 O(n),需要平衡机制

第十章:平衡树

10.1 为什么需要平衡?

BST 可能退化成链表。平衡树通过自动调整,保证树的高度始终是 O(log n)。

10.2 AVL 树 vs 红黑树

对比AVL 树红黑树
平衡标准严格(高度差 ≤ 1)宽松(最长路径 ≤ 2×最短)
查找更快(树更矮)稍慢
插入/删除旋转次数多旋转次数少
适用场景查找密集插入删除频繁
实际使用数据库索引Java TreeMap、Linux 内核

10.3 AVL 树的旋转操作

AVL 树通过旋转来维持平衡。当插入或删除导致某节点的左右子树高度差 > 1 时,需要旋转。

四种旋转情况: 1. LL 型(左左)→ 右旋 z y / \ / \ y T4 → x z / \ / \ / \ x T3 T1 T2 T3 T4 / \ T1 T2 2. RR 型(右右)→ 左旋 z y / \ / \ T1 y → z x / \ / \ / \ T2 x T1 T2 T3 T4 / \ T3 T4 3. LR 型(左右)→ 先左旋再右旋 4. RL 型(右左)→ 先右旋再左旋
AVL 树完整实现(Python)
class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1  # 节点高度

class AVLTree:
    def _height(self, node):
        return node.height if node else 0

    def _balance_factor(self, node):
        """平衡因子 = 左子树高度 - 右子树高度"""
        return self._height(node.left) - self._height(node.right)

    def _update_height(self, node):
        node.height = 1 + max(self._height(node.left),
                              self._height(node.right))

    def _rotate_right(self, z):
        """右旋"""
        y = z.left
        T3 = y.right
        y.right = z
        z.left = T3
        self._update_height(z)
        self._update_height(y)
        return y

    def _rotate_left(self, z):
        """左旋"""
        y = z.right
        T2 = y.left
        y.left = z
        z.right = T2
        self._update_height(z)
        self._update_height(y)
        return y

    def _rebalance(self, node):
        """检查并修复平衡"""
        self._update_height(node)
        bf = self._balance_factor(node)

        # LL 型:左子树太高,右旋
        if bf > 1 and self._balance_factor(node.left) >= 0:
            return self._rotate_right(node)
        # RR 型:右子树太高,左旋
        if bf < -1 and self._balance_factor(node.right) <= 0:
            return self._rotate_left(node)
        # LR 型:先左旋左子树,再右旋
        if bf > 1 and self._balance_factor(node.left) < 0:
            node.left = self._rotate_left(node.left)
            return self._rotate_right(node)
        # RL 型:先右旋右子树,再左旋
        if bf < -1 and self._balance_factor(node.right) > 0:
            node.right = self._rotate_right(node.right)
            return self._rotate_left(node)
        return node

    def insert(self, root, val):
        """插入并自动平衡"""
        if not root: return AVLNode(val)
        if val < root.val:
            root.left = self.insert(root.left, val)
        elif val > root.val:
            root.right = self.insert(root.right, val)
        else:
            return root  # 重复值不插入
        return self._rebalance(root)

    def delete(self, root, val):
        """删除并自动平衡"""
        if not root: return None
        if val < root.val:
            root.left = self.delete(root.left, val)
        elif val > root.val:
            root.right = self.delete(root.right, val)
        else:
            if not root.left: return root.right
            if not root.right: return root.left
            # 找后继
            succ = root.right
            while succ.left: succ = succ.left
            root.val = succ.val
            root.right = self.delete(root.right, succ.val)
        return self._rebalance(root)

# 演示:按顺序插入不会退化
avl = AVLTree()
root = None
for v in [1, 2, 3, 4, 5, 6, 7]:  # 顺序插入
    root = avl.insert(root, v)
# 树仍然平衡,高度 O(log n),不会变成链表!

def inorder(node):
    if not node: return []
    return inorder(node.left) + [node.val] + inorder(node.right)

print(inorder(root))  # [1, 2, 3, 4, 5, 6, 7](有序)

10.4 红黑树

红黑树是一种自平衡二叉搜索树,通过颜色标记和旋转规则来维持近似平衡。

红黑树的五条规则: 1. 每个节点要么是红色,要么是黑色 2. 根节点是黑色 3. 每个叶子节点(NIL)是黑色 4. 红色节点的两个子节点必须是黑色(不能有两个连续的红节点) 5. 从任一节点到其所有叶子的路径上,黑色节点数量相同 → 保证最长路径 ≤ 2 × 最短路径 → 树高 O(log n)
红黑树 vs AVL 树:实际选择 • 查找密集:选 AVL(更矮,查找更快)
• 插入删除频繁:选红黑树(旋转次数更少,最多 2-3 次)
• 实际工程:Java 的 TreeMap/TreeSet、C++ 的 std::map、Linux 内核调度器都用红黑树

10.5 B 树和 B+ 树

为什么数据库用 B+ 树? 磁盘 IO 是瓶颈。B+ 树每个节点存几百个键,3 层就能索引几亿条数据,只需 3 次 IO。层数越少 → IO 越少 → 越快。MySQL InnoDB 就用 B+ 树。
B 树 vs B+ 树: B 树: • 每个节点都存数据 • 关键字不重复出现 • 查找可能在任意层结束 B+ 树(数据库常用): • 只有叶子节点存数据 • 叶子节点用链表串联 → 范围查询高效 • 非叶子节点只存索引 → 每个节点能存更多键 B+ 树的优势: 1. 范围查询:叶子节点串联,遍历链表即可 2. 更矮胖:非叶子节点不存数据,每节点容纳更多键 3. 查询稳定:每次都要走到叶子,时间一致
B 树插入演示(阶数 M=3,每个节点最多 2 个键)
# B 树插入过程演示(简化版,M=3)
# 插入序列:10, 20, 5, 6, 12, 30, 7, 17

# 步骤 1: [10]
# 步骤 2: [10, 20]
# 步骤 3: 插入 5 → 分裂 →    [10]
#                            /    \
#                          [5]   [20]
# 步骤 4: 插入 6 →          [10]
#                          /    \
#                       [5,6]  [20]
# 步骤 5: 插入 12 →        [10]
#                          /    \
#                      [5,6]  [12,20]
# 步骤 6: 插入 30 →        [10]
#                          /    \
#                      [5,6]  [12,20,30] → 满了!
# 分裂 →        [10, 20]
#              /   |    \
#           [5,6] [12]  [30]

# 核心思想:节点满了就分裂,保证所有叶子在同一层

10.6 本章小结

本章要点回顾 • AVL 树通过旋转维持严格平衡(高度差 ≤ 1),四种旋转:LL/RR/LR/RL
• 红黑树用颜色规则实现近似平衡,旋转次数更少
• AVL 适合查找密集,红黑树适合插入删除频繁
• B+ 树叶子串联,范围查询高效,是数据库索引的标准选择
• 内存中用红黑树/AVL,磁盘上用 B+ 树

第十一章:堆——优先级的世界

11.1 什么是堆?

堆是一种特殊的完全二叉树:最大堆中父节点 ≥ 子节点,最小堆中父节点 ≤ 子节点。

类比:堆 = 公司职级

最大堆像公司:总经理 > 部门经理 > 普通员工。任何时候你都能快速找到"最大的那个"(堆顶)。

最大堆示例(完全二叉树 + 父 >= 子): 9 / \ 7 8 / \ / \ 3 5 6 4 堆顶 = 最大值 = 9 用数组表示:[9, 7, 8, 3, 5, 6, 4] 父节点下标 i → 左子 2i+1,右子 2i+2

11.2 堆的核心操作

import heapq

# Python 的 heapq 是最小堆
heap = []
heapq.heappush(heap, 3)   # 插入 O(log n)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
print(heapq.heappop(heap)) # 弹出最小值 O(log n) → 1

# 从列表建堆 O(n)
nums = [5, 3, 8, 1, 2]
heapq.heapify(nums)
print(nums)  # [1, 2, 8, 3, 5](堆的数组表示)

# 最大堆技巧:取负数
max_heap = []
for x in [3, 1, 4]:
    heapq.heappush(max_heap, -x)
print(-heapq.heappop(max_heap))  # 4

11.3 手写堆(理解原理)

class MinHeap:
    """手写最小堆(理解 heapq 底层原理)"""
    def __init__(self):
        self.heap = []

    def _sift_up(self, i):
        """上浮:插入元素后,向上调整到正确位置"""
        while i > 0:
            parent = (i - 1) // 2
            if self.heap[i] < self.heap[parent]:
                self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
                i = parent
            else:
                break

    def _sift_down(self, i):
        """下沉:删除堆顶后,向下调整到正确位置"""
        n = len(self.heap)
        while True:
            smallest = i
            left = 2 * i + 1
            right = 2 * i + 2
            if left < n and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < n and self.heap[right] < self.heap[smallest]:
                smallest = right
            if smallest != i:
                self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
                i = smallest
            else:
                break

    def push(self, val):
        """插入 O(log n)"""
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)

    def pop(self):
        """弹出最小值 O(log n)"""
        top = self.heap[0]
        last = self.heap.pop()
        if self.heap:
            self.heap[0] = last
            self._sift_down(0)
        return top

    def peek(self):
        """查看堆顶 O(1)"""
        return self.heap[0]

h = MinHeap()
for x in [5, 3, 8, 1, 2]:
    h.push(x)
print(h.pop())  # 1
print(h.pop())  # 2

11.4 堆排序

def heap_sort(arr):
    """堆排序 O(n log n)"""
    heapq.heapify(arr)           # 建堆 O(n)
    result = []
    while arr:
        result.append(heapq.heappop(arr))  # 逐个弹出 O(log n)
    return result

print(heap_sort([5, 3, 8, 1, 2]))  # [1, 2, 3, 5, 8]

11.5 经典应用:Top-K 问题

import heapq

def top_k(nums, k):
    """找出最大的 K 个数 O(n log k)"""
    return heapq.nlargest(k, nums)

print(top_k([3, 1, 4, 1, 5, 9, 2, 6], 3))  # [9, 6, 5]

11.6 本章小结

本章要点回顾 • 堆是完全二叉树,堆顶是最大/最小值
• 核心操作:sift_up(上浮)和 sift_down(下沉)
• 插入/删除都是 O(log n)
• Python 用 heapq 模块(最小堆)
• 经典应用:Top-K、优先队列、堆排序

第十二章:图——万物皆相连

12.1 什么是图?

图由顶点(节点)和边组成,用来表示"多对多"的关系。

类比:图 = 社交网络

微信好友关系就是一张图:每个人是节点,好友关系是边。你和朋友之间可能有共同好友,形成复杂的网络。

图的分类: 无向图(好友关系): 有向图(关注关系): 加权图(路线距离): A --- B A → B A --5-- B | / | ↑ ↓ | | | / | D ← C 3 2 | / | | | C --- D D --1-- C

12.2 图的存储方式

邻接矩阵 vs 邻接表
# 邻接矩阵(适合稠密图)
# graph[i][j] = 1 表示 i 和 j 之间有边
graph_matrix = [
    [0, 1, 1, 0],  # 节点 0 连接 1, 2
    [1, 0, 1, 1],  # 节点 1 连接 0, 2, 3
    [1, 1, 0, 1],  # 节点 2 连接 0, 1, 3
    [0, 1, 1, 0],  # 节点 3 连接 1, 2
]

# 邻接表(适合稀疏图,更常用)
from collections import defaultdict
graph = defaultdict(list)
edges = [(0,1), (0,2), (1,2), (1,3), (2,3)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # 无向图要加反向边

# graph = {0: [1,2], 1: [0,2,3], 2: [0,1,3], 3: [1,2]}
对比邻接矩阵邻接表
空间O(n^2)O(n + m)
判断是否有边O(1)O(degree)
遍历邻居O(n)O(degree)
适用稠密图稀疏图(更常用)

12.3 DFS 和 BFS

from collections import deque

def dfs(graph, start, visited=None):
    """深度优先搜索"""
    if visited is None: visited = set()
    visited.add(start)
    print(start, end=" ")
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

def bfs(graph, start):
    """广度优先搜索"""
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node, end=" ")
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

12.4 本章小结

本章要点回顾 • 图由顶点和边组成,表示多对多关系
• 存储方式:邻接矩阵(稠密图)vs 邻接表(稀疏图)
• DFS 用栈/递归,BFS 用队列
• DFS 适合路径搜索,BFS 适合最短路径(无权图)

第十三章:图的经典算法

13.1 最短路径:Dijkstra 算法

Dijkstra 算法求单源最短路径——从一个起点到其他所有点的最短距离。要求边权非负。

Dijkstra = 导航软件

导航软件找最短路线的原理:从你的位置出发,每次都走当前"最近的未访问路口",逐步扩展,直到覆盖所有路口。

import heapq

def dijkstra(graph, start):
    """Dijkstra 最短路径 O((V+E) log V)"""
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]  # (距离, 节点)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in graph[u]:  # (邻居, 权重)
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

# 带权图(邻接表)
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 4), ('B', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)]
}
print(dijkstra(graph, 'A'))  # {'A':0, 'B':1, 'C':3, 'D':4}

13.2 最小生成树:Kruskal 算法

最小生成树:用最少的边权总和连接所有节点。

def kruskal(n, edges):
    """Kruskal 最小生成树"""
    edges.sort(key=lambda x: x[2])  # 按权重排序
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    mst_weight = 0
    mst_edges = []
    for u, v, w in edges:
        pu, pv = find(u), find(v)
        if pu != pv:
            parent[pu] = pv
            mst_weight += w
            mst_edges.append((u, v, w))
    return mst_weight, mst_edges

13.3 最小生成树:Prim 算法

Prim 算法从一个起点出发,每次选最小的边扩展到新节点,适合稠密图。

import heapq

def prim(graph, n):
    """Prim 最小生成树(邻接表 + 优先队列)"""
    visited = set()
    min_heap = [(0, 0)]  # (权重, 节点)
    total_weight = 0

    while len(visited) < n and min_heap:
        w, u = heapq.heappop(min_heap)
        if u in visited:
            continue
        visited.add(u)
        total_weight += w
        for v, weight in graph[u]:
            if v not in visited:
                heapq.heappush(min_heap, (weight, v))

    return total_weight if len(visited) == n else -1

# 示例:无向带权图
graph = {
    0: [(1, 2), (3, 6)],
    1: [(0, 2), (2, 3), (3, 8), (4, 5)],
    2: [(1, 3), (4, 7)],
    3: [(0, 6), (1, 8)],
    4: [(1, 5), (2, 7)]
}
print(prim(graph, 5))  # 最小生成树总权重 = 16

13.4 最短路径:Bellman-Ford 算法

Dijkstra 不能处理负权边。Bellman-Ford 可以,还能检测负权环。

def bellman_ford(n, edges, start):
    """Bellman-Ford 最短路径(支持负权边)"""
    dist = [float('inf')] * n
    dist[start] = 0

    # 松弛 V-1 次
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # 第 V 次松弛:如果还能更新,说明有负权环
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None  # 存在负权环

    return dist

# 示例:含负权边
edges = [(0, 1, 4), (0, 2, 5), (1, 2, -3), (2, 3, 2)]
print(bellman_ford(4, edges, 0))  # [0, 4, 1, 3]
Dijkstra vs Bellman-Ford • Dijkstra:O((V+E) log V),不能处理负权边,更快
• Bellman-Ford:O(V×E),支持负权边,能检测负权环
• 实际选择:无负权边用 Dijkstra,有负权边用 Bellman-Ford

13.5 全源最短路径:Floyd-Warshall 算法

Floyd 算法求任意两点之间的最短距离,代码极其简洁。

def floyd_warshall(n, graph):
    """Floyd-Warshall 全源最短路径 O(V^3)"""
    # 初始化距离矩阵
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in graph:
        dist[u][v] = w

    # 核心:三重循环,枚举中间点
    for k in range(n):       # 中间点
        for i in range(n):   # 起点
            for j in range(n):  # 终点
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

# 示例:4 个节点的有向图
edges = [(0, 1, 3), (0, 2, 8), (1, 2, 2), (2, 3, 1), (3, 0, 5)]
dist = floyd_warshall(4, edges)
for row in dist:
    print([x if x != float('inf') else '∞' for x in row])
# [0, 3, 5, 6]
# [7, 0, 2, 3]
# [6, 9, 0, 1]
# [5, 8, 10, 0]

13.6 拓扑排序

拓扑排序用于有向无环图(DAG)——把节点排成一个线性序列,使得所有边从前指向后。

拓扑排序 = 选课顺序

大学里有些课有先修要求:学数据结构之前要学程序设计,学操作系统之前要学数据结构。拓扑排序就是找到一个合法的选课顺序。

from collections import deque, defaultdict

def topological_sort(num_courses, prerequisites):
    """拓扑排序(BFS / Kahn 算法)"""
    graph = defaultdict(list)
    in_degree = [0] * num_courses
    for dest, src in prerequisites:
        graph[src].append(dest)
        in_degree[dest] += 1

    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == num_courses else []

# 课程 0->1->2 的依赖关系
print(topological_sort(3, [[1,0], [2,1]]))  # [0, 1, 2]

13.7 本章小结

本章要点回顾 • Dijkstra:单源最短路径(非负权),O((V+E) log V)
• Bellman-Ford:单源最短路径(支持负权),O(V×E),能检测负权环
• Floyd-Warshall:全源最短路径,O(V^3),代码简洁
• Kruskal:最小生成树(边贪心,用并查集)
• Prim:最小生成树(点贪心,用优先队列)
• 拓扑排序:DAG 的线性排序,用于任务调度

第十四章:排序算法大比拼

14.1 排序算法总览

算法时间(平均)时间(最坏)空间稳定性
冒泡排序O(n^2)O(n^2)O(1)稳定
选择排序O(n^2)O(n^2)O(1)不稳定
插入排序O(n^2)O(n^2)O(1)稳定
归并排序O(n log n)O(n log n)O(n)稳定
快速排序O(n log n)O(n^2)O(log n)不稳定
堆排序O(n log n)O(n log n)O(1)不稳定
计数排序O(n+k)O(n+k)O(k)稳定

14.2 冒泡排序

def bubble_sort(arr):
    """冒泡排序 O(n^2) —— 每次把最大的"冒泡"到末尾"""
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped: break  # 优化:没有交换说明已有序
    return arr

14.3 选择排序

def selection_sort(arr):
    """选择排序 O(n^2) —— 每次选最小的放到前面"""
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

print(selection_sort([5, 3, 8, 1, 2]))  # [1, 2, 3, 5, 8]

14.4 插入排序

def insertion_sort(arr):
    """插入排序 O(n^2) —— 像打扑克牌一样,把新牌插入已排序的手牌"""
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]  # 后移
            j -= 1
        arr[j+1] = key  # 插入到正确位置
    return arr

# 特点:对近乎有序的数组接近 O(n)!
print(insertion_sort([1, 2, 4, 3, 5]))  # 几乎有序,很快
插入排序的特殊优势 虽然平均 O(n^2),但对近乎有序的数据接近 O(n)。Python 的 Timsort 在小数组(≤64)时就用插入排序!归并排序在合并时也常配合插入排序使用。

14.5 快速排序(最常用)

# 版本1:简洁写法(好理解,但需要额外空间)
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# 版本2:原地快排(面试常考,O(log n) 栈空间)
def quick_sort_inplace(arr, low=0, high=None):
    """原地快速排序,不需要额外数组"""
    if high is None: high = len(arr) - 1
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort_inplace(arr, low, pivot_idx - 1)
        quick_sort_inplace(arr, pivot_idx + 1, high)

def partition(arr, low, high):
    """分区:选最后一个做 pivot,小的放左边,大的放右边"""
    pivot = arr[high]
    i = low - 1  # i 指向"小于区"的最后一个
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

arr = [5, 3, 8, 1, 2, 9, 4]
quick_sort_inplace(arr)
print(arr)  # [1, 2, 3, 4, 5, 8, 9]
快排优化技巧 • 三数取中:选首、中、尾的中位数做 pivot,避免最坏 O(n^2)
• 小数组切换:元素少于 16 个时改用插入排序
• 三路快排:处理大量重复元素时,分为 </=/> 三部分

14.6 归并排序

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

14.7 本章小结

本章要点回顾 • 冒泡/选择/插入:O(n^2),适合小数据量
• 插入排序对近乎有序数据接近 O(n),是 Timsort 的基础
• 快排平均最快 O(n log n),最坏 O(n^2)(三数取中可优化)
• 归并排序稳定 O(n log n),但需要额外空间
• 堆排序 O(n log n),原地但不稳定
• Python 的 sort() 用 Timsort(归并+插入的混合)

第十五章:查找算法

15.1 顺序查找

def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target: return i
    return -1  # O(n)

15.2 二分查找

前提:数组必须有序 二分查找每次排除一半,O(log n)。100 万个数据最多查 20 次。
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: left = mid + 1
        else: right = mid - 1
    return -1

# 变体:查找第一个 >= target 的位置
def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target: left = mid + 1
        else: right = mid
    return left

15.3 二分查找变体

def upper_bound(arr, target):
    """查找第一个 > target 的位置"""
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

def search_rotated(nums, target):
    """LeetCode 33:在旋转有序数组中查找"""
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target: return mid
        # 判断哪半边有序
        if nums[left] <= nums[mid]:  # 左半边有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # 右半边有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

print(search_rotated([4,5,6,7,0,1,2], 0))  # 4

def find_peak(nums):
    """LeetCode 162:查找峰值(局部最大值)"""
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < nums[mid + 1]:
            left = mid + 1  # 峰值在右边
        else:
            right = mid     # 峰值在左边或就是 mid
    return left
二分查找的本质 二分不只是"有序数组找值"。只要能定义一个单调的判断条件,就能用二分。例如:求最小满足条件的值、求最大满足条件的值、在旋转数组中查找……核心思想:每次排除一半。

15.4 查找方式对比

方法时间要求适用场景
顺序查找O(n)无无序小数组
二分查找O(log n)有序数组有序大数组
哈希查找O(1)哈希表频繁查找
树查找O(log n)BST/平衡树动态数据

15.5 本章小结

本章要点回顾 • 顺序查找 O(n),简单但慢
• 二分查找 O(log n),要求有序(或单调条件)
• 二分变体:lower_bound、upper_bound、旋转数组查找、峰值查找
• 哈希查找 O(1),最快但无序
• 根据场景选择合适的查找方式

第十六章:分治算法

16.1 什么是分治?

分治(Divide and Conquer)的核心思想:把大问题拆成小问题,分别解决,再合并结果。

类比:分治 = 分蛋糕

一个大蛋糕不好切?先切成两半,每半再切成两半……直到切成小块。每小块很容易处理。最后把结果拼起来。

分治三步: 1. 分(Divide):把问题拆成若干子问题 2. 治(Conquer):递归解决子问题 3. 合(Combine):合并子问题的解

16.2 经典分治:归并排序

def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])     # 分
    right = merge_sort(arr[mid:])    # 分
    return merge(left, right)        # 合

16.3 经典分治:快速幂

def power(base, exp):
    """快速求 base^exp O(log exp)"""
    if exp == 0: return 1
    if exp % 2 == 0:
        half = power(base, exp // 2)
        return half * half            # 分治
    else:
        return base * power(base, exp - 1)

print(power(2, 10))  # 1024

16.4 经典分治:最大子数组和

def max_subarray_divide(nums):
    """LeetCode 53:分治法求最大子数组和 O(n log n)"""
    def helper(l, r):
        if l == r: return nums[l]
        mid = (l + r) // 2

        # 左半边最大
        left_max = helper(l, mid)
        # 右半边最大
        right_max = helper(mid + 1, r)

        # 跨越中点的最大
        left_sum = float('-inf')
        s = 0
        for i in range(mid, l - 1, -1):
            s += nums[i]
            left_sum = max(left_sum, s)

        right_sum = float('-inf')
        s = 0
        for i in range(mid + 1, r + 1):
            s += nums[i]
            right_sum = max(right_sum, s)

        cross_max = left_sum + right_sum
        return max(left_max, right_max, cross_max)

    return helper(0, len(nums) - 1)

print(max_subarray_divide([-2,1,-3,4,-1,2,1,-5,4]))  # 6

16.5 经典分治:最近点对

import math

def closest_pair(points):
    """平面上最近点对的距离 O(n log n)"""
    def dist(p1, p2):
        return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)

    def solve(px, py):
        if len(px) <= 3:
            return min(dist(px[i], px[j])
                       for i in range(len(px))
                       for j in range(i+1, len(px)))

        mid = len(px) // 2
        mid_x = px[mid][0]
        left_px, right_px = px[:mid], px[mid:]
        left_py = [p for p in py if p[0] <= mid_x]
        right_py = [p for p in py if p[0] > mid_x]

        d = min(solve(left_px, left_py), solve(right_px, right_py))

        # 检查跨越分界线的点对
        strip = [p for p in py if abs(p[0] - mid_x) < d]
        for i in range(len(strip)):
            for j in range(i+1, min(i+7, len(strip))):
                d = min(d, dist(strip[i], strip[j]))
        return d

    px = sorted(points, key=lambda p: p[0])
    py = sorted(points, key=lambda p: p[1])
    return solve(px, py)

print(closest_pair([(2,3), (12,30), (40,50), (5,1), (12,10), (3,4)]))
# ≈ 1.41 (点 (2,3) 和 (3,4))

16.6 本章小结

本章要点回顾 • 分治 = 分 + 治 + 合
• 归并排序、快速排序、快速幂都是分治
• 分治常与递归结合,时间复杂度通常是 O(n log n)

第十七章:贪心算法

17.1 什么是贪心?

贪心算法的核心:每一步都选当前看起来最优的,不考虑全局,最终得到全局最优解。

类比:贪心 = 吃自助餐

吃自助餐的贪心策略:每道菜都挑最好吃的先吃。虽然不一定能吃到"全局最优组合",但在很多场景下效果很好。

17.2 经典问题:活动选择

def activity_selection(activities):
    """选择最多的不重叠活动"""
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    count = 0
    last_end = 0
    for start, end in activities:
        if start >= last_end:  # 贪心:选最早结束的
            count += 1
            last_end = end
    return count

17.3 经典问题:分糖果

def find_content_children(children, cookies):
    """每个孩子分配一块饼干,求最多满足几个孩子"""
    children.sort()
    cookies.sort()
    child = cookie = 0
    while child < len(children) and cookie < len(cookies):
        if cookies[cookie] >= children[child]:
            child += 1  # 满足了这个孩子
        cookie += 1
    return child

17.4 经典问题:跳跃游戏

def can_jump(nums):
    """LeetCode 55:能否跳到最后一个位置"""
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:  # 当前位置跳不到
            return False
        max_reach = max(max_reach, i + nums[i])
    return True

print(can_jump([2, 3, 1, 1, 4]))  # True
print(can_jump([3, 2, 1, 0, 4]))  # False

def jump(nums):
    """LeetCode 45:跳到最后的最少步数"""
    steps = 0
    cur_end = 0      # 当前步能到达的最远
    farthest = 0     # 下一步能到达的最远
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:  # 到达当前步的边界
            steps += 1
            cur_end = farthest
    return steps

print(jump([2, 3, 1, 1, 4]))  # 2

17.5 经典问题:合并区间

def merge_intervals(intervals):
    """LeetCode 56:合并所有重叠区间"""
    intervals.sort(key=lambda x: x[0])  # 按起点排序
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:  # 重叠
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6], [8,10], [15,18]]

17.6 经典问题:用最少的箭引爆气球

def find_min_arrows(points):
    """LeetCode 452:按右端点贪心"""
    points.sort(key=lambda x: x[1])
    arrows = 1
    end = points[0][1]
    for s, e in points[1:]:
        if s > end:  # 新箭
            arrows += 1
            end = e
    return arrows

17.7 贪心的适用条件

贪心能用的前提 1. 贪心选择性质:局部最优能导致全局最优
2. 最优子结构:问题的最优解包含子问题的最优解

不是所有问题都能用贪心!如果局部最优不能保证全局最优,就需要动态规划。

17.8 本章小结

本章要点回顾 • 贪心:每步选当前最优,不回头
• 适用条件:贪心选择性质 + 最优子结构
• 区间问题:按右端点排序,贪心选最早结束的
• 跳跃游戏:维护当前能到达的最远距离
• 典型应用:活动选择、区间调度、哈夫曼编码、最小生成树

第十八章:回溯算法

18.1 什么是回溯?

回溯 = 试探 + 撤销。走一步试试,不行就退回来,换一条路继续试。

类比:回溯 = 走迷宫

走迷宫时:选一条路走到底。遇到死胡同?退回来,换一条路。直到找到出口或所有路都试完。

回溯模板: def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 # 把选择加入路径 backtrack(路径, 选择列表) 撤销选择 # 把选择从路径移除(回溯!)

18.2 经典问题:全排列

def permute(nums):
    """生成全排列"""
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i, num in enumerate(remaining):
            path.append(num)
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()  # 回溯:撤销选择

    backtrack([], nums)
    return result

print(permute([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

18.3 经典问题:N 皇后

def solve_n_queens(n):
    """N 皇后问题"""
    result = []
    def backtrack(row, cols, diag1, diag2, board):
        if row == n:
            result.append(["".join(r) for r in board])
            return
        for col in range(n):
            if col in cols or row-col in diag1 or row+col in diag2:
                continue  # 剪枝
            board[row][col] = 'Q'
            backtrack(row+1, cols|{col}, diag1|{row-col},
                     diag2|{row+col}, board)
            board[row][col] = '.'  # 回溯

    backtrack(0, set(), set(), set(),
              [['.']*n for _ in range(n)])
    return result

18.4 经典问题:子集

def subsets(nums):
    """LeetCode 78:生成所有子集"""
    result = []
    def backtrack(start, path):
        result.append(path[:])  # 每个路径都是一个子集
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

18.5 经典问题:组合总和

def combination_sum(candidates, target):
    """LeetCode 39:找出所有和为 target 的组合(可重复使用)"""
    result = []
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining: break  # 剪枝
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # i 不是 i+1,可重复
            path.pop()

    candidates.sort()
    backtrack(0, [], target)
    return result

print(combination_sum([2, 3, 6, 7], 7))
# [[2,2,3], [7]]

18.6 经典问题:括号生成

def generate_parenthesis(n):
    """LeetCode 22:生成所有有效括号组合"""
    result = []
    def backtrack(path, open_count, close_count):
        if len(path) == 2 * n:
            result.append(path)
            return
        if open_count < n:
            backtrack(path + '(', open_count + 1, close_count)
        if close_count < open_count:
            backtrack(path + ')', open_count, close_count + 1)

    backtrack('', 0, 0)
    return result

print(generate_parenthesis(3))
# ['((()))', '(()())', '(())()', '()(())', '()()()']

18.7 本章小结

本章要点回顾 • 回溯 = 试探 + 撤销,穷举所有可能
• 核心:做选择 → 递归 → 撤销选择
• 剪枝可以大幅减少搜索空间
• 三种模式:排列(顺序有关)、组合(顺序无关)、子集(所有子集)
• 典型应用:全排列、组合、子集、N 皇后、括号生成、数独

第十九章:动态规划——从零到精通

19.1 什么是动态规划?

动态规划(DP)的核心:把大问题拆成重叠子问题,记住子问题的解,避免重复计算。

类比:DP = 考试带笔记本

普通递归就像闭卷考试:同一道题反复做。DP 就像开卷考试:做过的题记在笔记本上,下次直接查答案。

对比贪心回溯动态规划
策略每步选最优穷举所有可能记住子问题解
是否回退不回退回退不回退
适用局部最优=全局最优需要穷举最优子结构+重叠子问题

19.2 斐波那契数列:DP 入门

# 普通递归 O(2^n) —— 大量重复计算
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# 动态规划 O(n) —— 记住已算过的
def fib_dp(n):
    if n <= 1: return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# 空间优化 O(1)
def fib_opt(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

19.3 背包问题(DP 经典)

def knapsack(weights, values, capacity):
    """0-1 背包问题"""
    n = len(weights)
    # dp[i][w] = 前 i 个物品、容量为 w 时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i-1][w]  # 不选第 i 个
            if w >= weights[i-1]:
                dp[i][w] = max(dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][capacity]

print(knapsack([2,3,4,5], [3,4,5,6], 8))  # 10

19.4 最长公共子序列(LCS)

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

print(lcs("abcde", "ace"))  # 3 ("ace")

19.5 经典问题:爬楼梯

def climb_stairs(n):
    """LeetCode 70:每次爬 1 或 2 阶,求方案数"""
    if n <= 2: return n
    a, b = 1, 2  # dp[1], dp[2]
    for _ in range(3, n + 1):
        a, b = b, a + b  # dp[i] = dp[i-1] + dp[i-2]
    return b

# 本质就是斐波那契数列!
print(climb_stairs(5))  # 8

19.6 经典问题:零钱兑换

def coin_change(coins, amount):
    """LeetCode 322:凑成 amount 最少需要多少硬币"""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 凑 0 元需要 0 个硬币
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 2, 5], 11))  # 3 (5+5+1)
print(coin_change([2], 3))         # -1

def coin_change_ways(coins, amount):
    """凑成 amount 有多少种方案"""
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]
    return dp[amount]

print(coin_change_ways([1, 2, 5], 5))  # 4

19.7 经典问题:最长递增子序列(LIS)

def lis_dp(nums):
    """LeetCode 300:O(n^2) DP 解法"""
    n = len(nums)
    dp = [1] * n  # dp[i] = 以 nums[i] 结尾的 LIS 长度
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

print(lis_dp([10, 9, 2, 5, 3, 7, 101, 18]))  # 4

def lis_binary(nums):
    """O(n log n) 二分查找优化"""
    from bisect import bisect_left
    tails = []  # tails[i] = 长度为 i+1 的递增子序列的最小末尾
    for num in nums:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

print(lis_binary([10, 9, 2, 5, 3, 7, 101, 18]))  # 4

19.8 经典问题:编辑距离

def min_distance(word1, word2):
    """LeetCode 72:最少操作将 word1 变成 word2"""
    m, n = len(word1), len(word2)
    dp = [[0] * (n+1) for _ in range(m+1)]

    # 边界:空串变成目标串需要的步数
    for i in range(m+1): dp[i][0] = i  # 全部删除
    for j in range(n+1): dp[0][j] = j  # 全部插入

    for i in range(1, m+1):
        for j in range(1, n+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # 字符相同,不需要操作
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],     # 删除
                    dp[i][j-1],     # 插入
                    dp[i-1][j-1]    # 替换
                )
    return dp[m][n]

print(min_distance("horse", "ros"))      # 3
print(min_distance("intention", "execution"))  # 5
编辑距离的应用 编辑距离是 NLP 和生物信息学的基础算法:拼写纠错(找最近的正确单词)、DNA 序列比对、diff 工具(Git diff 的核心思想)。

19.9 经典问题:最长回文子串

def longest_palindrome(s):
    """LeetCode 5:中心扩展法 O(n^2)"""
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1
        return s[l+1:r]

    best = ""
    for i in range(len(s)):
        odd = expand(i, i)      # 奇数长度回文
        even = expand(i, i+1)   # 偶数长度回文
        best = max(best, odd, even, key=len)
    return best

print(longest_palindrome("babad"))  # "bab" 或 "aba"

19.10 DP 解题四步法

1
定义状态——dp[i] 或 dp[i][j] 代表什么?
2
状态转移方程——dp[i] 怎么从 dp[i-1] 推导出来?
3
初始条件——dp[0] 等于什么?
4
遍历顺序——正序还是倒序?

19.11 本章小结

本章要点回顾 • DP = 记忆化搜索,避免重复计算
• 适用条件:最优子结构 + 重叠子问题
• 四步法:定义状态 → 转移方程 → 初始条件 → 遍历顺序
• 背包问题:选或不选,二维 DP
• LIS:O(n^2) DP 或 O(n log n) 二分优化
• 编辑距离:增删改三种操作取最小
• 零钱兑换:完全背包变体
• 经典问题:背包、LCS、编辑距离、爬楼梯、零钱兑换

第二十章:高级数据结构

20.1 字典树(Trie)

Trie 是一种专门处理字符串前缀的树结构,广泛用于搜索引擎自动补全、拼写检查。

Trie 结构(存储 "cat", "car", "dog"): root / | \ c d / \ a o / \ \ t r g 查找 "car":root -> c -> a -> r(存在!) 前缀 "ca" 匹配:cat, car
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True

    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children: return False
            node = node.children[c]
        return node.is_end

trie = Trie()
trie.insert("cat"); trie.insert("car")
print(trie.search("cat"))   # True
print(trie.search("ca"))    # False

20.2 并查集(Union-Find)

并查集用于处理连通性问题:判断两个元素是否属于同一集合,合并两个集合。

并查集 = 帮派系统

一群人各自为派:A 和 B 结盟 → 合并为一派。C 和 D 结盟 → 合并为一派。问"A 和 C 是一派吗?"→ 查找他们各自的"帮主"。

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        """查找根节点(带路径压缩)"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        """合并两个集合"""
        px, py = self.find(x), self.find(y)
        if px == py: return
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

    def connected(self, x, y):
        return self.find(x) == self.find(y)

uf = UnionFind(5)
uf.union(0, 1); uf.union(2, 3)
print(uf.connected(0, 1))  # True
print(uf.connected(0, 2))  # False

20.3 线段树

线段树用于区间查询和区间修改,支持 O(log n) 的区间求和、区间最大值等操作。

class SegmentTree:
    """线段树:区间求和"""
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self._build(data, 1, 0, self.n - 1)

    def _build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
            return
        mid = (start + end) // 2
        self._build(data, 2*node, start, mid)
        self._build(data, 2*node+1, mid+1, end)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

    def query(self, left, right):
        """查询区间 [left, right] 的和 O(log n)"""
        return self._query(1, 0, self.n-1, left, right)

    def _query(self, node, start, end, left, right):
        if right < start or end < left: return 0
        if left <= start and end <= right: return self.tree[node]
        mid = (start + end) // 2
        return (self._query(2*node, start, mid, left, right) +
                self._query(2*node+1, mid+1, end, left, right))

st = SegmentTree([1, 3, 5, 7, 9, 11])
print(st.query(1, 3))  # 3+5+7 = 15

20.4 布隆过滤器

布隆过滤器(Bloom Filter) 一种概率型数据结构,用于判断"某个元素是否在集合中"。可能误判存在(假阳性),但不会误判不存在。空间效率极高,广泛用于爬虫去重、缓存穿透防护。
布隆过滤器原理: 位数组: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 插入 "apple" → 用 3 个哈希函数分别算出位置 1, 4, 7 位数组: [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] 插入 "banana" → 位置 2, 5, 8 位数组: [0, 1, 1, 0, 1, 1, 0, 1, 1, 0] 查询 "apple" → 位置 1, 4, 7 全为 1 → 可能存在 查询 "cherry" → 位置 1, 5, 9 → 位置 9 为 0 → 一定不存在! 误判原因:多个元素可能把同一位设为 1
布隆过滤器实现(Python)
import mmh3  # 需要安装:pip install mmh3
from bitarray import bitarray  # 需要安装:pip install bitarray

class BloomFilter:
    def __init__(self, size, hash_count):
        self.size = size           # 位数组大小
        self.hash_count = hash_count  # 哈希函数个数
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)

    def add(self, item):
        """插入元素"""
        for i in range(self.hash_count):
            idx = mmh3.hash(item, i) % self.size
            self.bit_array[idx] = 1

    def contains(self, item):
        """查询元素是否存在"""
        for i in range(self.hash_count):
            idx = mmh3.hash(item, i) % self.size
            if not self.bit_array[idx]:
                return False  # 一定不存在
        return True  # 可能存在(有误判概率)

# 使用示例
bf = BloomFilter(size=1000, hash_count=3)
bf.add("apple"); bf.add("banana")
print(bf.contains("apple"))   # True
print(bf.contains("cherry"))  # 大概率 False

# 简化版(不用第三方库)
class SimpleBloomFilter:
    def __init__(self, size=1024, hash_count=3):
        self.size = size
        self.hash_count = hash_count
        self.bits = [0] * size

    def _hashes(self, item):
        """生成多个哈希值"""
        results = []
        for i in range(self.hash_count):
            h = hash(item + str(i)) % self.size
            results.append(h)
        return results

    def add(self, item):
        for h in self._hashes(item):
            self.bits[h] = 1

    def contains(self, item):
        return all(self.bits[h] for h in self._hashes(item))

20.5 跳表(Skip List)

跳表是 Redis 有序集合(ZSet)的底层数据结构。它通过多层索引来加速查找,实现简单,性能堪比平衡树。

跳表结构(多层索引): Level 3: 1 ────────────────→ 9 → None Level 2: 1 ────→ 4 ────────→ 9 → None Level 1: 1 → 3 → 4 → 5 → 7 → 9 → None 查找 7:Level 3: 1→9(太大)→ 回退到 1 Level 2: 1→4→9(太大)→ 回退到 4 Level 1: 4→5→7(找到了!) 只走了 7 步中的 6 步,比逐个遍历快!
跳表实现(Python,简化版)
import random

class SkipListNode:
    def __init__(self, val=-1, level=0):
        self.val = val
        self.next = [None] * (level + 1)  # 每层的下一个指针

class SkipList:
    def __init__(self, max_level=16, p=0.5):
        self.max_level = max_level
        self.p = p
        self.head = SkipListNode(-1, max_level)
        self.level = 0  # 当前最高层

    def _random_level(self):
        """随机决定节点层数"""
        lvl = 0
        while random.random() < self.p and lvl < self.max_level:
            lvl += 1
        return lvl

    def search(self, target):
        """查找 O(log n)"""
        cur = self.head
        for i in range(self.level, -1, -1):  # 从最高层开始
            while cur.next[i] and cur.next[i].val < target:
                cur = cur.next[i]
        cur = cur.next[0]
        return cur and cur.val == target

    def insert(self, val):
        """插入 O(log n)"""
        update = [self.head] * (self.max_level + 1)
        cur = self.head
        for i in range(self.level, -1, -1):
            while cur.next[i] and cur.next[i].val < val:
                cur = cur.next[i]
            update[i] = cur

        new_level = self._random_level()
        if new_level > self.level:
            self.level = new_level

        new_node = SkipListNode(val, new_level)
        for i in range(new_level + 1):
            new_node.next[i] = update[i].next[i]
            update[i].next[i] = new_node

sl = SkipList()
for v in [3, 6, 7, 9, 12, 19, 21]:
    sl.insert(v)
print(sl.search(7))   # True
print(sl.search(8))   # False
跳表 vs 红黑树 • 两者都是 O(log n) 查找/插入/删除
• 跳表实现更简单,区间查询更方便
• Redis 选择跳表:实现简单 + 支持范围查询 + 并发友好

20.6 树状数组(Binary Indexed Tree / Fenwick Tree)

树状数组用于单点修改 + 前缀和查询,比线段树更简洁,常数更小。

树状数组实现
class BIT:
    """树状数组:单点修改 + 前缀和查询,都是 O(log n)"""
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        """在位置 i 增加 delta"""
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)  # 关键操作:lowbit

    def query(self, i):
        """查询前缀和 [1, i]"""
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)  # 关键操作:lowbit
        return s

    def range_query(self, l, r):
        """查询区间和 [l, r]"""
        return self.query(r) - self.query(l - 1)

# 示例
bit = BIT(10)
for i, v in enumerate([1, 3, 5, 7, 9, 2, 4, 6, 8, 10], 1):
    bit.update(i, v)
print(bit.query(5))       # 1+3+5+7+9 = 25
print(bit.range_query(3, 7))  # 5+7+9+2+4 = 27
树状数组的 lowbit 操作: lowbit(x) = x & (-x) 取最低位的 1 例:lowbit(6) = 6 & (-6) = 0110 & 1010 = 0010 = 2 树状数组的树形结构(以 n=8 为例): tree[8] = sum[1..8] / \ tree[4] tree[6] = sum[1..4], sum[5..6] / \ | t[2] t[3] t[5] t[7] = 各自管理的区间 update(i): 沿 i += lowbit(i) 向上更新所有父节点 query(i): 沿 i -= lowbit(i) 向下累加所有前缀

20.7 本章小结

本章要点回顾 • Trie:字符串前缀匹配,O(m) 查找(m 为字符串长度)
• 并查集:连通性判断,路径压缩 + 按秩合并 → 接近 O(1)
• 线段树:区间查询/修改 O(log n),支持懒传播
• 布隆过滤器:概率型存在性判断,极省内存,可能误判存在
• 跳表:多层索引加速查找 O(log n),Redis ZSet 的底层
• 树状数组:单点修改 + 前缀和查询 O(log n),比线段树更简洁

第二十一章:经典面试题与实战

21.1 LRU 缓存

LRU(Least Recently Used)缓存淘汰最久没使用的数据。面试高频题!

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache: return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

cache = LRUCache(2)
cache.put(1, 1); cache.put(2, 2)
print(cache.get(1))     # 1
cache.put(3, 3)          # 淘汰 key=2
print(cache.get(2))     # -1

21.2 用栈实现队列

class MyQueue:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def push(self, x):
        self.stack_in.append(x)

    def pop(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        return self.stack_out.pop()

21.3 二叉树的最近公共祖先(LCA)

def lowest_common_ancestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right: return root
    return left or right

21.4 滑动窗口最大值

from collections import deque

def max_sliding_window(nums, k):
    """滑动窗口最大值(单调队列)"""
    result = []
    dq = deque()  # 存下标,保持队列单调递减
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] <= num:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]

21.5 解题模式一:双指针

双指针适用场景 有序数组求和、去重、分区、回文判断。核心思想:两个指针从两端或同端出发,根据条件移动,将 O(n^2) 降为 O(n)。
def two_sum_sorted(nums, target):
    """LeetCode 167:有序数组两数之和"""
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target: return [left + 1, right + 1]
        elif s < target: left += 1
        else: right -= 1

def three_sum(nums):
    """LeetCode 15:三数之和(排序 + 双指针)"""
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]: continue  # 跳过重复
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]: left += 1
                while left < right and nums[right] == nums[right-1]: right -= 1
                left += 1; right -= 1
            elif s < 0: left += 1
            else: right -= 1
    return result

print(three_sum([-1, 0, 1, 2, -1, -4]))  # [[-1,-1,2], [-1,0,1]]

21.6 解题模式二:滑动窗口

滑动窗口适用场景 子串/子数组问题(最长/最短/包含/不重复)。核心:维护一个窗口 [left, right],right 扩展,left 收缩。
def length_of_longest_substring(s):
    """LeetCode 3:最长无重复子串"""
    seen = {}
    left = 0
    best = 0
    for right, c in enumerate(s):
        if c in seen and seen[c] >= left:
            left = seen[c] + 1  # 收缩左边界
        seen[c] = right
        best = max(best, right - left + 1)
    return best

print(length_of_longest_substring("abcabcbb"))  # 3

def min_window(s, t):
    """LeetCode 76:最小覆盖子串"""
    from collections import Counter
    need = Counter(t)
    missing = len(t)  # 还需要匹配的字符数
    left = 0
    start, end = 0, float('inf')

    for right, c in enumerate(s):
        if need[c] > 0:
            missing -= 1
        need[c] -= 1

        while missing == 0:  # 窗口已包含所有字符
            if right - left < end - start:
                start, end = left, right
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1

    return s[start:end+1] if end != float('inf') else ""

print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"

21.7 解题模式三:单调栈

单调栈适用场景 "下一个更大/更小元素"类问题。核心:栈中元素保持单调,遇到破坏单调的元素时弹出处理。
def next_greater_element(nums):
    """LeetCode 496:下一个更大元素"""
    n = len(nums)
    result = [-1] * n
    stack = []  # 存下标,栈中元素对应值单调递减
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    return result

print(next_greater_element([2, 1, 2, 4, 3]))  # [4, 2, 4, -1, -1]

def daily_temperatures(temps):
    """LeetCode 739:每天要等几天才升温"""
    n = len(temps)
    result = [0] * n
    stack = []
    for i in range(n):
        while stack and temps[stack[-1]] < temps[i]:
            j = stack.pop()
            result[j] = i - j
        stack.append(i)
    return result

print(daily_temperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]

21.8 解题模式四:BFS 层序遍历

from collections import deque

def level_order(root):
    """LeetCode 102:二叉树层序遍历"""
    if not root: return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

def oranges_rotting(grid):
    """LeetCode 994:腐烂的橘子(多源 BFS)"""
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2: queue.append((r, c, 0))
            elif grid[r][c] == 1: fresh += 1

    minutes = 0
    while queue:
        r, c, minutes = queue.popleft()
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                queue.append((nr, nc, minutes + 1))

    return minutes if fresh == 0 else -1

21.9 更多经典题目清单

题目数据结构/模式难度
有效的括号栈简单
合并两个有序链表链表简单
二叉树的最大深度树 + 递归简单
反转链表链表简单
两数之和哈希表简单
三数之和排序 + 双指针中等
岛屿数量DFS/BFS中等
课程表拓扑排序中等
最长递增子序列DP / 二分中等
接雨水双指针 / 栈困难
最小覆盖子串滑动窗口困难
编辑距离DP中等
最长无重复子串滑动窗口中等
下一个更大元素单调栈中等
腐烂的橘子多源 BFS中等
单词接龙BFS困难
最大子数组和Kadane / DP中等
合并 K 个有序链表分治 / 堆困难

21.10 本章小结

本章要点回顾 • LRU 缓存 = 哈希表 + 双向链表
• 双指针:有序数组求和、三数之和 → O(n^2) 降为 O(n)
• 滑动窗口:子串/子数组问题 → 维护 [left, right] 窗口
• 单调栈:下一个更大/更小元素 → 栈中保持单调
• BFS 层序遍历:最短路径、逐层处理
• 单调队列解决滑动窗口最值
• LCA 是树的经典问题
• 多刷题、多总结,面试就不慌

附录:速查手册

A. 各数据结构时间复杂度对比

数据结构访问查找插入删除
数组O(1)O(n)O(n)O(n)
链表O(n)O(n)O(1)O(1)
栈O(n)O(n)O(1)O(1)
队列O(n)O(n)O(1)O(1)
哈希表-O(1)O(1)O(1)
BSTO(log n)O(log n)O(log n)O(log n)
堆O(1)(堆顶)O(n)O(log n)O(log n)

B. 排序算法速查

算法平均最坏空间稳定
冒泡O(n^2)O(n^2)O(1)Yes
插入O(n^2)O(n^2)O(1)Yes
归并O(n log n)O(n log n)O(n)Yes
快排O(n log n)O(n^2)O(log n)No
堆排O(n log n)O(n log n)O(1)No

C. Python 内置数据结构速查

Python 常用数据结构
# list —— 动态数组
lst = [1, 2, 3]
lst.append(4)     # O(1)
lst.pop()          # O(1)
lst[0]             # O(1) 访问

# deque —— 双端队列
from collections import deque
dq = deque([1, 2, 3])
dq.append(4)       # 右端入 O(1)
dq.popleft()       # 左端出 O(1)

# dict —— 哈希表
d = {"a": 1}
d["a"]             # O(1) 查找
d["b"] = 2         # O(1) 插入

# set —— 集合(哈希表)
s = {1, 2, 3}
s.add(4)           # O(1)
3 in s             # O(1) 查找

# heapq —— 最小堆
import heapq
heap = [3, 1, 2]
heapq.heapify(heap)    # O(n)
heapq.heappush(heap, 0)  # O(log n)
heapq.heappop(heap)      # O(log n)

# defaultdict —— 带默认值的字典
from collections import defaultdict
dd = defaultdict(int)
dd["key"] += 1     # 自动初始化为 0

D. 图算法速查

算法用途时间复杂度条件
DFS遍历、路径搜索、连通分量O(V+E)通用
BFS最短路径(无权)、层序遍历O(V+E)通用
Dijkstra单源最短路径O((V+E)logV)非负权
Bellman-Ford单源最短路径O(V×E)支持负权
Floyd-Warshall全源最短路径O(V³)通用
Prim最小生成树O((V+E)logV)稠密图优
Kruskal最小生成树O(E log E)稀疏图优
拓扑排序DAG 线性排序O(V+E)必须 DAG
并查集连通性判断≈O(1)合并/查询

E. 算法选择决策树

遇到问题,怎么选算法? 1. 涉及"字符串"? ├─ 前缀匹配 → Trie ├─ 子串/子数组 → 滑动窗口 └─ 编辑距离 → DP 2. 涉及"数组/序列"? ├─ 有序 → 二分查找 ├─ 求和/配对 → 双指针 或 哈希表 ├─ 最大/最小连续子数组 → Kadane(DP) └─ 排序 → 快排/归并 3. 涉及"树"? ├─ 遍历 → 前序/中序/后序/层序 ├─ 最短路径 → BFS ├─ 最优解 → DP 或 递归 └─ 区间查询 → 线段树/树状数组 4. 涉及"图"? ├─ 连通性 → DFS/BFS/并查集 ├─ 最短路径 → Dijkstra/Bellman-Ford/Floyd ├─ 最小生成树 → Prim/Kruskal └─ 依赖关系 → 拓扑排序 5. 涉及"最优化"? ├─ 局部最优=全局最优 → 贪心 ├─ 有重叠子问题 → 动态规划 ├─ 需要穷举 → 回溯 └─ 可以拆成子问题 → 分治 6. 涉及"查找/缓存"? ├─ O(1) 查找 → 哈希表 ├─ 有序查找 → BST/二分 ├─ Top-K → 堆 └─ 缓存淘汰 → LRU(哈希+双向链表)

F. 推荐学习资源

推荐资源 • LeetCode:刷题必备,从 Easy 开始
• 《算法导论》:经典教材,深入理论
• 《大话数据结构》:通俗易懂,适合入门
• Visualgo.net:算法可视化网站
• Hello 算法:hello-algo.com,图解数据结构