| 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
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.
