Hello 算法--Go版本 (靳宇栋) (Z-Library)

Page 1

(This page has no text content)

Page 2

(This page has no text content)

Page 3

Hello 算法 Go 语言版 作者：靳宇栋（@krahets） 代码审阅：刘代富（@Reanon） Release 1.0.0 2024‐02‐09 序 两年前，我在力扣上分享了“剑指 Offer”系列题解，受到了许多读 者的鼓励和支持。在与读者交流期间，我 最常被问的一个问题是“如 何入门算法” 。逐渐地，我对这个问题产生了浓厚的兴趣。 两眼一 抹黑地刷题似乎是最受欢迎的方法，简单、直接且有效。然而刷题就 如同玩“扫雷”游戏，自学能力 强的人能够顺利将地雷逐个排掉，而 基础不足的人很可能被炸得满头是包，并在挫折中步步退缩。通读教 材 也是一种常见做法，但对于面向求职的人来说，毕业论文、投递简 历、准备笔试和面试已经消耗了大部分精 力，啃厚重的书往往变成了 一项艰巨的挑战。 如果你也面临类似的困扰，那么很幸运这本书 “找”到了你。本书是我对这个问题给出的答案，即使不是最 优解， 也至少是一次积极的尝试。本书虽然不足以让你直接拿到 Offer，但 会引导你探索数据结构与算法的 “知识地图”，带你了解不同“地 雷”的形状、大小和分布位置，让你掌握各种“排雷方法” 。有了这 些本领， 相信你可以更加自如地刷题和阅读文献，逐步构建起完整的 知识体系。 我深深赞同费曼教授所言：“Knowledge isn’t free. You have to pay attention.”从这个意义上看，这本 书并非完全“免费”。为了 不辜负你为本书所付出的宝贵“注意力” ，我会竭尽所能，投入最大 的“注意力” 来完成本书的创作。本人自知学疏才浅，书中内容虽然 已经过一段时间的打磨，但一定仍有许多错误，恳请 各位老师和同学 批评指正。

Page 4

本书中的代码附有可一键运行的源文件，托管于 github.com/krahets/hello‐algo 仓库。动画在PDF 内的 展示效果 受限，可访问hello‐algo.com 网页版以获得更优的阅读体验。 推荐语 “一本通俗易懂的数据结构与算法入门书，引导读者手脑并用地学 习，强烈推荐算法初学者阅读！ ” —— 邓俊辉，清华大学计算机系 教授 “如果我当年学数据结构与算法的时候有《Hello算法》，学起来应该 会简单10 倍！ ” —— 李沐，亚马逊资深首席科学家 目 录 i 第0 章 前言 1 0.1 关于本书 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 0.2 如何使用本书 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 0.3 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 第1 章 初识算法 10 1.1 算法无处不在 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2 算法是什么 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Page 5

1.3 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 第2 章 复杂度分析 17 2.1 算法效率评估 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 迭代与递归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 时间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4 空间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 第3 章 数据结构 51 3.1 数据结构分类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.2 基本数据类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.3 数字编码* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4 字符编码* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

Page 6

第4 章 数组与链表 66 4.1 数组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.2 链表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.3 列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.4 内存与缓存* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 第5 章 栈与队列 90 5.1 栈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.2 队列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.3 双向队列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 第6 章 哈希表 112 6.1 哈希表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 6.2 哈希冲突 . . . . . . . . . . . . . . . . . . . . . . . .

Page 7

. . . . . . . . . . . . . . . . 119 6.3 哈希算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 6.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 第7 章 树 135 7.1 二叉树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 7.2 二叉树遍历 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 7.3 二叉树数组表示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 7.4 二叉搜索树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 7.5 AVL 树* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 7.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 目 录 hello‐algo.com ii 第8 章 堆 172 8.1 堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 8.2 建堆操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

Page 8

8.3 Top‐k 问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 8.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 第9 章 图 189 9.1 图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 9.2 图的基础操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 9.3 图的遍历 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 9.4 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 第10 章 搜索 209 10.1 二分查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 10.2 二分查找插入点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 10.3 二分查找边界 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 10.4 哈希优化策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 10.5 重识搜索算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223

Page 9

10.6 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 第11 章 排序 226 11.1 排序算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 11.2 选择排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 11.3 冒泡排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 11.4 插入排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 11.5 快速排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 11.6 归并排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 11.7 堆排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 11.8 桶排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 11.9 计数排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 11.10 基数排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 11.11 小结 . . . . . . . . . . . . . . . . . . . . . . . . .

Page 10

. . . . . . . . . . . . . . . . 258 第12 章 分治 261 12.1 分治算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 12.2 分治搜索策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 12.3 构建二叉树问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 12.4 汉诺塔问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 12.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 第13 章 回溯 278 13.1 回溯算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 13.2 全排列问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 13.3 子集和问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 13.4 n 皇后问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 13.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 第14 章 动态规划 304

Page 11

14.1 初探动态规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 14.2 动态规划问题特性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 14.3 动态规划解题思路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 14.4 0‐1 背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325 14.5 完全背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 14.6 编辑距离问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 14.7 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 目 录 hello‐algo.com iii 第15 章 贪心 350 15.1 贪心算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 15.2 分数背包问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 15.3 最大容量问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358 15.4 最大切分乘积问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

Page 12

15.5 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 第16 章 附录 368 16.1 编程环境安装 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369 16.2 一起参与创作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371 16.3 术语表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 第0 章 前言

Page 13

(This page has no text content)

Page 14

算法犹如美妙的交响乐，每一行代码都像韵律般流淌。 愿这本书在你 的脑海中轻轻响起，留下独特而深刻的旋律。 1 第0 章 前言 0.1 关于本书 hello‐algo.com 2 本项目旨在创建一本开源、免费、对新手友好的数据结构与算法入门 教程。 ‧ 全书采用动画图解，结构化地讲解数据结构与算法知识，内容清晰易 懂，学习曲线平滑。 ‧ 算法源代码皆可一键运行，支持Python、C++、Java、C#、Go、 Swift、JavaScript、TypeScript、 Dart、 Rust、C 和Zig 等语言。 ‧ 鼓励读者在线上章节评论区互帮互助、共同进步，提问与评论通常可 在两日内得到回复。 0.1.1 读者对象 若你是算法初学者，从未接触过算法，或者已经有一些刷题经验，对 数据结构与算法有模糊的认识，在会与 不会之间反复横跳，那么本书 正是为你量身定制的！ 如果你已经积累一定的刷题量，熟悉大部分题 型，那么本书可助你回顾与梳理算法知识体系，仓库源代码可 以当作 “刷题工具库”或“算法字典”来使用。 若你是算法“大神”，我们期待收到你的宝贵建议，或者一起参与创 作 。

Page 15

前置条件 你需要至少具备任一语言的编程基础，能够阅读和编写简单代码。 0.1.2 内容结构 本书的主要内容如图0‐1 所示。 ‧ 复杂度分析 ：数据结构和算法的评价维度与方法。时间复杂度和空 间复杂度的推算方法、常见类型、示 例等。 ‧ 数据结构 ：基本数据类型和数据结构的分类方法。数组、链表、 栈、队列、哈希表、树、堆、图等数据 结构的定义、优缺点、常用操 作、常见类型、典型应用、实现方法等。 ‧ 算法 ：搜索、排序、分治、回溯、动态规划、贪心等算法的定义、 优缺点、效率、应用场景、解题步骤 和示例问题等。 第0 章 前言 hello‐algo.com 3

Page 16

图0‐1 本书主要内容 0.1.3 致谢 本书在开源社区众多贡献者的共同努力下不断完善。感谢每一位投入 时间与精力的撰稿人，他们是（按照 GitHub 自动生成的顺序） ：krahets、codingonion、nuomi1、 Gonglja、Reanon、justin‐tse、danielsss、 hpstory、 S‐N‐O‐R‐L‐A‐X、night‐cruise、msk397、gvenusleo、 RiverTwilight、gyt95、zhuoqinyue、 Zuoxun、Xia‐Sang、mingXta、FangYuan33、GN‐Yu、IsChristina、 xBLACKICEx、guowei‐gong、 Cathay‐ Chen、mgisr、JoseHung、 qualifier1024、pengchzn、Guanngxu、longsizhuo、L‐Super、 what‐is‐me、 yuan0221、lhxsm、Slone123c、WSL0809、

Page 17

longranger2、theNefelibatas、xiongsp、JeffersonHuang、 hongyun‐robot、K3v123、yuelinxin、a16su、gaofer、malone6、 Wonderdch、xjr7670、DullSword、 Horbin‐Magician、NI‐SW、 reeswell、XC‐Zero、XiaChuerwu、yd‐j、iron‐irax、 huawuque404、 MolDuM、 Nigh、KorsChen、foursevenlove、52coder、bubble9um、 youshaoXG、curly210102、gltianwen、 fanchenggang、Transmigration‐zhou、FloranceYeh、FreddieLi、 ShiMaRing、lipusheng、 Javesun99、 JackYang‐hellobobo、 shanghai‐Jerry、0130w、Keynman、psychelzh、logan‐qiu、 ZnYang2018、 MwumLi、1ch0、Phoenix0415、qingpeng9802、Richard‐Zhang1019、 QiLOL、Suremotoo、Turing‐ 1024‐Lee、Evilrabbit520、 GaochaoZhu、ZJKung、linzeyan、hezhizhen、ZongYangL、 beintentional、 czruby、coderlef、dshlstarr、szu17dmy、 fbigm、gledfish、hts0000、boloboloda、iStig、jiaxianhua、 wenjianmin、keshida、kilikilikid、lclc6、lwbaptx、liuxjerry、 lucaswangdev、lyl625760、chadyi、 noobcodemaker、selear、 siqyka、syd168、4yDX3906、tao363、wangwang105、weibk、 yabo083、 yi427、yishangzhang、zhouLion、baagod、 ElaBosak233、xb534、luluxia、yanedie、thomasq0、 YangXuanyi 和th1nk3r‐ing 。 第0 章 前言 hello‐algo.com 4 本书的代码审阅工作由codingonion、Gonglja、gvenusleo、 hpstory、justin‐tse、krahets、 night‐cruise、 nuomi1 和 Reanon 完成（按照首字母顺序排列） 。感谢他们付出的时间与精 力，正是他们确保了各语言代 码的规范与统一。 在本书的创作过程中，我得到了许多人的帮助。 ‧ 感谢我在公司的导师李汐博士，在一次畅谈中你鼓励我“快行动起 来” ，坚定了我写这本书的决心；

Page 18

‧ 感谢我的女朋友泡泡作为本书的首位读者，从算法小白的角度提出许 多宝贵建议，使得本书更适合新 手阅读； ‧ 感谢腾宝、琦宝、飞宝为本书起了一个富有创意的名字，唤起大家写 下第一行代码“Hello World!”的 美好回忆； ‧ 感谢校铨在知识产权方面提供的专业帮助，这对本开源书的完善起到 了重要作用； ‧ 感谢苏潼为本书设计了精美的封面和logo ，并在我的强迫症的驱使 下多次耐心修改； ‧ 感谢@squidfunk 提供的排版建议，以及他开发的开源文档主题 Material‐for‐MkDocs 。 在写作过程中，我阅读了许多关于数据结构与算法的教材和文章。这 些作品为本书提供了优秀的范本，确保 了本书内容的准确性与品质。 在此感谢所有老师和前辈的杰出贡献！ 本书倡导手脑并用的学习方 式，在这一点上我深受《动手学深度学习》 的启发。在此向各位读者 强烈推荐这 本优秀的著作。 衷心感谢我的父母，正是你们一直以来的支持与鼓励，让我有机会做 这件富有趣味的事 。 0.2 如何使用本书 为了获得最佳的阅读体验，建议你通读本节内容。 0.2.1 行文风格约定 ‧ 标题后标注* 的是选读章节，内容相对困难。如果你的时间有限，可 以先跳过。

Page 19

‧ 重要专有名词及其英文翻译会用「」括号标注，例如「数组 array 。建议记住它们，以便阅读文献。 ‧ 专有名词和有特指含义的词句会 使用“引号” 标注，以避免歧义。 ‧ 重要名词、重点内容和总结性语句会加粗 ，这类文字值得特别关 注。 ‧ 当涉及编程语言之间不一致的名词时，本书均以Python 为准，例如 使用None 来表示“空” 。 ‧ 本书部分放弃了编程语言的注释规范，以换取更加紧凑的内容排版。 注释主要分为三种类型：标题注 释、内容注释、多行注释。 /* 标题注释，用于标注函数、类、测试样例等 */ // 内容注释，用于详解代码 /** * 多行 第0 章 前言 hello‐algo.com 5 * 注释 */ 0.2.2 在动画图解中高效学习 相较于文字，视频和图片具有更高的信息密度和结构化程度，更易于 理解。在本书中， 重点和难点知识将主 要通过动画以图解形式展示 ，而文字则作为解释与补充。 如果你在阅读本书时，发现某段内容提供了如图0‐2 所示的动画图 解，请以图为主、以文字为辅 ，综合两者 来理解内容。

Page 20

图0‐2 动画图解示例 0.2.3 在代码实践中加深理解 本书的配套代码托管在GitHub 仓库。如图0‐3 所示，源代码附有测 试样例，可一键运行 。 如果时间允许，建议你参照代码自行敲一遍 。如果学习时间有限，请至少通读并运行所有代码。 与阅读代码相 比，编写代码的过程往往能带来更多收获。动手学，才是真的学 。 第0 章 前言 hello‐algo.com 6