Hello 算法
Java 语言版
靳宇栋(Krahets)
Release 1.0.0b4
2023‑07‑26
序
两年前,我在力扣上分享了《剑指 Oer》系列题解,受到了许多朋友的喜爱与支持。在此期间,我回答了众
多读者的评论问题,其中最常见的一个问题是“如何入门学习算法”。我逐渐也对这个问题产生了浓厚的兴
趣。
两眼一抹黑地刷题似乎是最受欢迎的方法,简单直接且有效。然而,刷题就如同玩“扫雷”游戏,自学能力
强的同学能够顺利地将地雷逐个排掉,而基础不足的同学很可能被炸的满头是包,并在挫折中步步退缩。通
读教材书籍也是一种常见做法,但对于面向求职的同学来说,毕业季、投递简历、准备笔试面试已经占据了
大部分精力,厚重的书籍往往变成了一项艰巨的挑战。
如果你也面临类似的困扰,那么很幸运这本书找到了你。本书是我对此问题的给出的答案,虽然不一定正确,
但至少是一次积极的尝试。这本书虽然不足以让你直接拿到 Oer ,但会引导你探索数据结构与算法的“知
识地图”,带你了解不同“地雷”的形状大小和分布位置,让你掌握各种“排雷方法”。有了这些本领,相信
你可以更加自如地应对刷题和阅读文献,逐步构建起完整的知识体系。
本书中的代码附有可一键运行的源文件,托管于 github.com/krahets/hello‑algo 仓库。动画在 PDF 内的
展示效果受限,可访问 hello‑algo.com 网页版以获得更优的阅读体验。
致谢
本书在开源社区众多贡献者的共同努力下不断成长。感谢每一位投入 时 间 与 精 力 的 撰 稿 人, 他 们
是(按照 GitHub 自动生成的顺序):krahets, sjinzh, justin‑tse, Reanon, nuomi1, Gonglja, S‑N‑O‑
R‑L‑A‑X, danielsss, hpstory, RiverTwilight, msk397, gyt95, zhuoqinyue, FangYuan33, mingXta,
gvenusleo, Xia‑Sang, night‑cruise, guowei‑gong, GN‑Yu, xBLACKICEx, JoseHung, IsChristina,
pengchzn, qualier1024, Guanngxu, Cathay‑Chen, what‑is‑me, L‑Super, Slone123c, mgisr,
WSL0809, longsizhuo, JeersonHuang, longranger2, xiongsp, hongyun‑robot, Wonderdch, a16su,
NI‑SW, xjr7670, MolDuM, XC‑Zero, DullSword, iron‑irax, yuan0221, wangwang105, ZongYangL,
shanghai‑Jerry, curly210102, Suremotoo, linzeyan, yi427, boloboloda, huawuque404, 4yDX3906,
ZJKung, xb534, siqyka, ZnYang2018, beintentional, luluxia, GaochaoZhu, weibk, dshlstarr,
ShiMaRing, fbigm, dyizheng, iStig, YuelinXin, szu17dmy, hezhizhen, fanchenggang, Keynman,
youshaoXG, lipusheng, Javesun99, tao363, czruby, gltianwen, liuxjerry, yabo083.
本书的代码审阅工作由 Gonglja, gvenusleo, hpstory, justin‐tse, krahets, nuomi1, Reanon, sjinzh 完
成(按照首字母顺序排列)。感谢他们付出的时间与精力,正是他们确保了各语言代码的规范与统一。
推荐语
“一本通俗易懂的数据结构与算法入门书,引导读者手脑并用地学习,强烈推荐算法初学者阅读。”
——邓俊辉,清华大学计算机系教授
“如果我当年学数据结构与算法的时候有《Hello 算法》,学起来应该会简单 10 倍!”
——李沐,亚马逊资深首席科学家
i
目 录
0. 前言 1
0.1. 关于本书 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
0.2. 如何使用本书 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
0.3. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1. 初识算法 7
1.1. 算法无处不在 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2. 算法是什么 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2. 复杂度 13
2.1. 算法效率评估 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2. 时间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3. 空间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3. 数据结构 37
3.1. 数据结构分类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2. 基本数据类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3. 数字编码 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4. 字符编码 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.5. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4. 数组与链表 50
4.1. 数组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2. 链表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3. 列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.4. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5. 栈与队列 68
5.1. 栈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.2. 队列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.3. 双向队列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.4. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6. 散列表 91
6.1. 哈希表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2. 哈希冲突 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.3. 哈希算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.4. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7. 树 112
7.1. 二叉树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
7.2. 二叉树遍历 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
7.3. 二叉树数组表示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
7.4. 二叉搜索树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.5. AVL 树 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.6. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
8. 堆 147
8.1. 堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
目 录 hello‑algo.com ii
8.2. 建堆操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
8.3. Top‑K 问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
8.4. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
9. 图 161
9.1. 图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
9.2. 图基础操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
9.3. 图的遍历 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
9.4. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
10. 搜索 180
10.1. 二分查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
10.2. 二分查找边界 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
10.3. 哈希优化策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
10.4. 重识搜索算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
10.5. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
11. 排序 193
11.1. 排序算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
11.2. 选择排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
11.3. 冒泡排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
11.4. 插入排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
11.5. 快速排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
11.6. 归并排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
11.7. 堆排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
11.8. 桶排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
11.9. 计数排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
11.10. 基数排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
11.11. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
12. 分治 228
12.1. 分治算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
12.2. 分治搜索策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
12.3. 构建二叉树问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
12.4. 汉诺塔问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
12.5. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
13. 回溯 244
13.1. 回溯算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
13.2. 全排列问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
13.3. 子集和问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
13.4. N 皇后问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
13.5. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
14. 动态规划 270
14.1. 初探动态规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
14.2. 动态规划问题特性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
14.3. 动态规划解题思路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
14.4. 0‑1 背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
14.5. 完全背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
14.6. 编辑距离问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
14.7. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
15. 贪心 316
15.1. 贪心算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
15.2. 分数背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320