总结与进阶

第 17 章 · 数据结构与算法

一、全书知识地图

按模块可概括为：基础结构（数组、链表、栈、队列、哈希表）→ 树与图（二叉树、BST/AVL/红黑、堆、图与 DFS/BFS、最短路与 MST）→ 排序与查找（比较排序、二分及其变体）→ 算法思想（递归与分治、动态规划、贪心）。复杂度（大 O）贯穿始终，是衡量「选哪种结构、哪种算法」的标尺。

二、核心思想小结

复杂度：用大 O 描述时间、空间随规模增长的趋势；选数据结构与算法时先看「需要什么操作、允许什么复杂度」。数据结构选型：查多用哈希、有序用 BST/堆、邻接关系用图、层次用树。递归与分治：基线条件 + 递归关系；分治分解→解决→合并，子问题不重叠时高效。动态规划：重叠子问题用记忆化或递推避免重复计算；状态、转移、边界、顺序四要素。贪心：每步局部最优、不回溯；需贪心选择性质与最优子结构。排序、二分、DFS/BFS、最短路与 MST 是常考常用的工具。

三、后续学习方向

刷题巩固：LeetCode、牛客、Codeforces 等按「数组/链表/树/图/DP/贪心」标签刷题，先做简单与中等，再挑困难。进阶主题：字符串（KMP、字典树、AC 自动机）、高级数据结构（线段树、树状数组、并查集进阶）、网络流、计算几何等，可按兴趣与方向选读。书籍与课程：《算法导论》《算法》（Sedgewick）、慕课/ B 站上的数据结构与算法课程，可与本课互为补充。面试准备：本课覆盖的栈、队列、哈希、树、图、排序、二分、DP、贪心都是高频考点，建议每章配合 3～5 道经典题反复练。

四、综合练习

下面三道题综合运用多章知识，均给出 Python3 实现（类型标注与注释）。

from typing import List


def two_sum(nums: List[int], target: int) -> List[int]:
    """一次遍历：用字典记录「值→下标」，对当前 x 查 target-x 是否已出现。"""
    seen: dict = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

from typing import List, Optional
from collections import deque


class TreeNode:
    def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None) -> None:
        self.val = val
        self.left = left
        self.right = right


def level_order(root: Optional[TreeNode]) -> List[List[int]]:
    """队列 BFS：按层扩展，每层记录当前层节点数，出队对应个数并收集值。"""
    if not root:
        return []
    q: deque = deque([root])
    result: List[List[int]] = []
    while q:
        level: List[int] = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(level)
    return result

from typing import List


def max_profit(prices: List[int]) -> int:
    """贪心：维护「至今最低价」min_price，每天用 当天价-min_price 更新最大利润。"""
    if not prices:
        return 0
    min_price = prices[0]
    best = 0
    for p in prices[1:]:
        best = max(best, p - min_price)
        min_price = min(min_price, p)
    return best

def is_valid(s: str) -> bool:
    """栈：左括号入栈，右括号与栈顶匹配则弹栈，否则无效；最后栈空才有效。"""
    stack: list = []
    pair = {')': '(', ']': '[', '}': '{'}
    for c in s:
        if c in '([{':
            stack.append(c)
        else:
            if not stack or stack[-1] != pair[c]:
                return False
            stack.pop()
    return len(stack) == 0