dsa-hello-algo

name	dsa-hello-algo
description	Knowledge base from "Hello 算法" (Python 版) by 靳宇栋 (@krahets), Release 1.3.0. Use when learning or applying data structures and algorithms in Python - covers complexity analysis, arrays, linked lists, stacks, queues, hash maps, trees, heaps, graphs, search, sorting, divide-and-conquer, backtracking, dynamic programming, and greedy algorithms.

Hello 算法 (Python 版)

Author: 靳宇栋 (@krahets) | Pages: ~348 | Chapters: 17 (0-16) | Generated: 2026-07-08

How to Use This Skill

• Without arguments - load core frameworks for reference
• With a topic - ask about 链表, 动态规划, 红黑树, or another indexed topic; I find and read the relevant chapter
• With chapter - ask for ch07; I load that specific chapter
• Browse - ask "what chapters do you have?" to see the full index

When you ask about a topic not covered in Core Frameworks below, I will read the relevant chapter file before answering.

---

Core Frameworks & Mental Models

1. 渐近复杂度分析 (大O记号) — 评估算法效率的标尺

Use on every algorithm design. 推算两步法：① 用三技巧（忽略常数/省略系数/嵌套相乘）统计操作数量；② 取最高阶项得渐近上界。Prefer 最差时间复杂度 O() 作"效率安全值"。常见排序：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)。口诀："系数无法撼动阶数"。

2. 时间-空间权衡 (Trade-off)

多数场景"以空间换时间"（数据库索引、哈希表）；内存宝贵时"以时间换空间"（嵌入式用数组顺序查找替哈希表）。哈希表是典型：用未使用内存换 O(1) 查询。递归深度 n 累积 O(n) 栈帧空间——Python/Java/C++ 等多数语言不支持自动尾递归优化。

3. 物理-逻辑双维度选数据结构

先看逻辑需求（线性 vs 树形 vs 网状），再看物理约束（连续 vs 分散）。

• 数组 (连续): O(1) 访问、O(n) 增删；缓存命中率高（缓存行/预取/空间局部性）。索引从 0 起因地址偏移量为 0。
• 链表 (分散): O(1) 增删（改两个引用）、O(n) 访问；适合频繁中间增删且长度难预估。
• 动态数组 (列表): 初始容量 + 数量记录 + 倍数扩容，兼顾两者；扩容时单次 O(n)。

4. 哈希查询框架 index = hash(key) % capacity

Use 需按 key 高效查询。冲突不可避免（输入空间≫输出空间）。三种解决：① 链式地址（桶内链表，过长转 AVL/红黑树）；② 开放寻址（线性/平方/多次哈希探测，不能直接删除，必须用 TOMBSTONE 懒删除）；③ 扩容（负载因子阈值如 0.75）。Prefer 大质数取模以减少聚集。Only 不可变对象才能作 key。

5. 二叉树遍历：BFS + DFS 三序

• BFS (层序): 队列实现，逐层推进；求最短路径（无权图）、层次遍历。
• DFS: 递归实现；前序（根→左→右）、中序（左→根→右，BST 升序）、后序（左→右→根）。 完全二叉树用数组表示：节点 i 左子 2i+1、右子 2i+2、父 (i-1)//2。

6. AVL 旋转：自底向上恢复平衡

插入/删除后 |平衡因子|>1 时旋转。四种情况：左偏+左子≥0 → 右旋；左偏+左子<0 → 先左后右；右偏+右子≤0 → 左旋；右偏+右子>0 → 先右后左。旋转后必更新 node 和 child 高度；空节点高度 -1，叶节点 0。BST 删除度为 2 节点须用中序后继替换。

7. 堆化与 Top-k

堆=完全二叉树+数组存储。入堆 sift_up（与父比）、出堆 sift_down（与较大子比），均 O(log n)。高效建堆：倒序遍历非叶节点 sift_down，O(n) 而非 O(n log n)。出堆必须先交换堆顶堆底再删尾，避免索引全变。Top-k 用小顶堆维护 k 大小，O(n log k)；不要用大顶堆维护 n 大小，也不要全排序。

8. 二分查找 (双闭区间 [0, n-1])

Use 仅当有序数组且查询频繁。i=0, j=n-1; while i<=j: m=(i+j)//2。变种：插入点（找到 target 时 j=m-1，使 i 收敛至最左 target）；右边界 = 查找最左 target+1 后 j=i-1。大数越界用 m = i + (j-i)//2。避坑：链表不可二分；小数据量线性查找更快；高频增删场景维护有序数组插入 O(n) 太贵。

9. 排序算法特性权衡五边形

运行快、原地、稳定、自适应、通用——不可兼得，按需取舍。

• 快排 O(n log n)：通用首选，缓存友好常数小；三数取中+短子数组优先递归降栈深。固定选最左端基准会退化 O(n²)。
• 归并 O(n log n)：稳定，链表排序可 O(1) 额外空间，外部排序。
• 堆排 O(n log n)：原地但非稳定，跳跃访问缓存不友好。
• 插入排序 O(n²)：小数据量常快于 O(n log n)，Java 内置排序对短数组用它。
• 非比较排序（桶/计数/基数）可达 O(n) 但条件严：均匀分布/非负小范围整数/固定位数。
• 多级排序必须用稳定排序，否则前序成果丢失。

10. 分治三判断依据 + 分治 = 分 + 治

判断适合分治：① 可分解为更小类似子问题；② 子问题独立互不依赖；③ 子问题解可合并。二分查找是分治特例（无须合并）。汉诺塔 f(n)=2·f(n-1)+f(1)，O(2ⁿ)。子问题重叠时改用 DP——分治与 DP 的核心区别。

11. 回溯算法框架：尝试 → 剪枝 → 递归 → 回退

def backtrack(state, choices, res):
    if is_solution(state): record(state, res); return
    for choice in choices:
        if is_valid(state, choice):
            make_choice(state, choice)
            backtrack(state, choices, res)
            undo_choice(state, choice)   # 必须与 make_choice 配对

回溯本质 = 穷举 + 剪枝。三种剪枝：① selected 数组（全局唯一，防元素重复选）；② duplicated 集合（每轮新建，防相等元素本轮被多次选）；③ 越界/约束剪枝（排序后 target-choice<0 时 break）。子集和：先排序 + start 变量保索引单调。n 皇后逐行放置 + cols/diags1/diags2 处理列与对角线。组合优化问题（0-1 背包、TSP）回溯不是最优，应优先 DP 或启发式。

12. 动态规划：四步法 + 三方法递进

判断三大特性：① 重叠子问题；② 最优子结构；③ 无后效性（未来只与当前状态有关）。 四步：① 定义状态得 dp 表；② 推状态转移方程；③ 确定边界与转移顺序；④ 实现。 三方法演进：暴力搜索 O(2ⁿ) → 记忆化搜索 O(n)（mem 数组从顶至底）→ 动态规划 O(n)（dp 表从底至顶）。 空间优化看依赖方向：依赖正上方+左上方 → 倒序（0-1 背包）；依赖正上方+正左方 → 正序（完全背包）；依赖左+上+左上 → 用 leftup 变量暂存（编辑距离）。无后效性破坏时扩展状态维度（带约束爬楼梯 [i] → [i,j]）。零钱兑换用 amt+1 表示无效解避免溢出。

13. 贪心：两大特性 + 三步法

判断：① 贪心选择性质（局部最优→全局最优）；② 最优子结构（与 DP 共享）。三步：问题分析 → 确定贪心策略 → 正确性证明（反证法或数学归纳法）。 典型：分数背包按单位价值降序；最大容量双指针移动短板 O(n)；最大切分乘积因子 3，余数 1 时 1×3 替换为 2×2。 避坑：零钱兑换仅特定硬币组合（如 [1,5,10,20,50,100]）保证最优，[1,20,50] 等组合贪心失败；0-1 背包必须用 DP，分数背包才可贪心。贪心通常比 DP 低一个数量级。

14. 图遍历：BFS 用队列、DFS 用递归

必须用 visited 集合防环路——图与树遍历的关键区别。链表 ⊂ 树 ⊂ 图（自由度递增）。邻接矩阵 O(n²) 空间换 O(1) 查边；邻接表 O(n+m) 空间，链表过长转红黑树/哈希表。树的前/中/后序遍历都是 DFS 特例。

---

Chapter Index

#	Title	Key Frameworks
ch00	前言	内容三部分结构, 算法学习三阶段, 三位一体学习法
ch01	初识算法	算法定义三特性, 数据结构设计三目标, 拼装积木类比
ch02	复杂度分析	渐近复杂度分析, 大O记号, 推算两步法, 计数简化三技巧, 时间-空间权衡
ch03	数据结构	逻辑结构分类, 物理结构分类, 组织方式+内容类型, 补码, UTF-8
ch04	数组与链表	数组操作复杂度, 链表节点操作, 动态数组扩容, 缓存效率评估
ch05	栈与队列	栈实现选择, 环形数组队列, 双向队列扩展, 撤销/反撤销双栈
ch06	哈希表	哈希查询框架, 冲突处理选择, 链式地址/开放寻址, 懒删除
ch07	树	二叉树遍历(BFS/DFS), BST 操作, AVL 旋转, 数组表示二叉树
ch08	堆	堆化(sift_up/sift_down), 建堆框架, Top-k 框架
ch09	图	邻接矩阵, 邻接表, BFS, DFS, visited 防环
ch10	搜索	二分查找(双闭), 插入点, 左/右边界, 哈希优化策略
ch11	排序	选择/冒泡/插入/快排/归并/堆排/桶/计数/基数排序, 特性权衡五边形
ch12	分治	分治三判断依据, 分治搜索策略, 汉诺塔分解
ch13	回溯	回溯算法框架, 剪枝三类型, n 皇后, 子集和
ch14	动态规划	DP 三大特性, 解题四步法, 三方法递进, 背包/编辑距离
ch15	贪心	贪心两大特性, 解题三步法, 分数背包, 最大容量, 切分乘积
ch16	附录	环境安装两步法, 开源贡献三路径, 中英繁术语对照

Topic Index

• AVL 树 -> ch06, ch07
• BFS (广度优先搜索) -> ch07, ch09, ch14
• Big-O 记号 -> ch02
• DFS (深度优先搜索) -> ch07, ch09, ch13
• DP (动态规划) -> ch14
• Dijkstra 算法 -> ch15
• MD5 / SHA 哈希算法 -> ch06
• Top-k 问题 -> ch08
• UTF-8 编码 -> ch03
• 二分查找 -> ch10, ch12
• 二叉搜索树 (BST) -> ch07
• 二叉树 -> ch07
• 分治 -> ch12
• 双指针 -> ch15
• 平衡因子 -> ch07
• 归并排序 -> ch11
• 计数排序 -> ch11
• 记忆化搜索 -> ch14
• 堆 -> ch08
• 堆排序 -> ch11
• 堆化 (heapify) -> ch08
• 图 -> ch09
• 大顶堆 / 小顶堆 -> ch08
• 插入排序 -> ch11
• 指数阶 O(2ⁿ) -> ch02
• 排序稳定性 -> ch11
• 插入点查找 -> ch10
• 撤销/反撤销 (undo/redo) -> ch05
• 字典序/前缀和 -> ch10
• 动态数组 (列表) -> ch04
• 哈希冲突 -> ch06
• 哈希表 -> ch06
• 回溯 -> ch13
• 图遍历 -> ch09
• 基数排序 -> ch11
• 复杂度分析 -> ch02
• 子集和问题 -> ch13
• 完全二叉树 -> ch07, ch08
• 尾递归 -> ch02
• 快速排序 -> ch11
• 时间-空间权衡 -> ch02
• 背包问题 (0-1/完全) -> ch14
• 贪心 -> ch15
• 链表 -> ch04
• 队列 -> ch05
• 邻接矩阵 / 邻接表 -> ch09
• 递归 -> ch02
• 编辑距离 -> ch14
• 数组 -> ch04
• 树 -> ch07
• 栈 -> ch05
• 栈帧空间 -> ch02
• 桶排序 -> ch11
• 汉诺塔 -> ch12
• 环形数组 -> ch05
• 算法学习三阶段 -> ch00
• 补码 -> ch03
• 过度拟合 / 雪崩效应 -> ch06
• n 皇后问题 -> ch13
• 剪枝 -> ch13

Supporting Files

• glossary.md - 所有关键术语及定义
• patterns.md - 所有算法模式与技术
• cheatsheet.md - 决策规则与快速参考表

---

Scope & Limits

This skill covers the book "Hello 算法" (Python 版) content only. All code examples are in Python. For C++ implementations, see the companion skills dsa-yin (殷人昆) and dsa-deng (邓俊辉). For topics beyond this book, check related skills or ask the agent directly.