算法训练营：提高篇（全彩版）-图书

推荐0
收藏0
浏览9

算法训练营：提高篇（全彩版）

书　　号：9787121490729
页　　数：284
开　　本：16(170*240)
出版状态：正在印刷
维护人：张国霞

本书图文并茂、通俗易懂，详细讲解常用的算法知识，又融入大量的竞赛实例和解题技巧，可帮助读者熟练应用各种算法解决实际问题。
本书总计8章。第1章讲解STL，涉及双端队列、优先队列、位图、集合、映射和STL中的常用函数；第2章讲解实用的数据结构，涉及并查集、倍增、稀疏表、区间最值查询、最近公共祖先、树状数组和线段树；第3章讲解查找算法，涉及散列表、字符串模式匹配和字典树；第4章讲解平衡树，涉及树高与性能、平衡二叉搜索树、树堆和伸展树；第5章讲解图论提高方面的知识，涉及连通图与强连通图、桥与割点、双连通分量的缩点和Tarjan算法；第6章讲解图论算法，涉及最小生成树、最短路径、拓扑排序和关键路径；第7章讲解搜索算法提高方面的知识，涉及剪枝优化、嵌套广度优先搜索、双向广度优先搜索和启发式搜索；第8章讲解动态规划提高方面的知识，涉及树形动态规划、状态压缩动态规划和动态规划优化。
本书面向对算法感兴趣的读者，无论是想扎实内功或参加算法竞赛的学生，还是想进入名企的学生、求职者，抑或是想提升核心竞争力的在职人员，都可以参考本书。若读者想系统学习数据结构与算法，则可参考《算法训练营：入门篇》（全彩版）和《算法训练营：进阶篇》（全彩版）。

本书具有以下特色。
（1）完美图解，通俗易懂。本书对每个算法的基本操作都有全彩图解。通过图解，许多问题都变得简单，可迎刃而解。
（2）实例丰富，简单有趣。本书结合了大量竞赛实例，讲解如何用算法解决实际问题，使复杂难懂的问题变得简单有趣，可帮助读者轻松掌握算法知识，体会其中的妙处。
（3）深入浅出，透析本质。本书透过问题看本质，重点讲解如何分析和解决问题。本书采用了简洁易懂的代码，对数据结构的设计和算法的描述全面、细致，而且有算法复杂度分析及优化过程。
（4）实战演练，循序渐进。本书在讲解每个算法后都进行了实战演练，使读者在实战中体会算法的设计思路和使用技巧，从而提高独立思考、动手实践的能力。书中有丰富的练习题和竞赛题，可帮助读者及时检验对所学知识的掌握情况，为从小问题出发且逐步解决大型复杂性工程问题奠定基础。
（5）网络资源，技术支持。本书为读者提供了配套源码、课件、视频，并提供了博客、微信群、QQ群技术支持，可随时为读者答疑解惑。

作者简介
陈小玉
高级程序员，主要研究方向为算法优化和机器学习。出版著作有《趣学算法》《趣学数据结构》《算法训练营》，所教学生多次获得ACM-ICPC、蓝桥杯等算法竞赛奖项。

目前，信息技术已被广泛应用于互联网、金融、航空、军事、医疗等各个领域，未来的应用将更加广泛和深入。并且，很多中小学都开设了计算机语言课程，越来越多的中小学生对编程、算法感兴趣，甚至在NOIP、NOI等算法竞赛中大显身手，进入名校深造。对信息技术感兴趣的大学生通常会参加ACM-ICPC、CCPC、蓝桥杯等算法竞赛，其获奖者更是被各大名企所青睐。
学习算法，不仅可以帮助我们具备较强的思维能力及解决问题的能力，还可以帮助我们快速学习各种新技术，拥有超强的学习能力。
——写作背景——
很多读者都觉得算法太难，市面上晦涩难懂的各种教材更是“吓退”了一大批读者。实际上，算法并没有我们想象中那么难，反而相当有趣。
每当有学生说看不懂某个算法的时候，笔者就会建议其画图。画图是学习算法最好的方法，因为它可以把抽象难懂的算法展现得生动形象、简单易懂。笔者曾出版《算法训练营：海量图解+竞赛刷题》（入门篇）和《算法训练营：海量图解+竞赛刷题》（进阶篇），很多读者非常喜欢其中的海量图解，更希望看到这两本书的全彩版。经过一年的筹备，笔者对上述书中的所有图片都重新进行了绘制和配色，并精选、修改、补充和拆分上述书中的内容，形成了《算法训练营：入门篇》（全彩版）、《算法训练营：提高篇》（全彩版）和《算法训练营：进阶篇》（全彩版），本书就是其中的《算法训练营：提高篇》（全彩版）。在此衷心感谢各位读者的大力支持！
本书详细讲解常用的算法知识，还增加了STL的内容。本书不是知识点的堆砌，也不是粘贴代码而来的简单题解，而是将知识点讲解和对应的竞赛实例融会贯通，读者可以在轻松阅读本书的同时进行刷题实战，在实战中体会算法的妙处，感受算法之美。
——学习建议——
学习算法的过程，应该是通过大量实例充分体会遇到问题时该如何分析：用什么数据结构，用什么算法和策略，算法复杂度如何，是否有优化的可能，等等。这里有以下几个建议。
第1个建议：学经典，多理解。
算法书有很多，初学者最好选择图解较多的入门书，当然，也可以选择多本书，从多个角度进行对比和学习。先看书中的图解，理解各种经典问题的求解方法，如果还不理解，则可以看视频讲解，理解之后再看代码，尝试自己动手上机运行。如有必要，则可以将算法的求解过程通过图解方式展示出来，以加深对算法的理解。
第2个建议：看题解，多总结。
在掌握书中的经典算法之后，可以在刷题网站上进行专项练习，比如练习贪心算法、分治算法、动态规划等方面的题目。算法比数据结构更加灵活，对同一道题目可以用不同的算法解决，算法复杂度也不同。如果想不到答案，则可以看题解，比较自己的想法与题解的差距。要多总结题目类型及最优解法，找相似的题目并自己动手解决问题。
第3个建议：举一反三，灵活运用。
通过专项刷题做到“见多识广”，总结常用的算法模板，熟练应用套路，举一反三，灵活运用，逐步提升刷题速度，力争“bug free”（无缺陷）。
——本书特色——
本书具有以下特色。
（1）完美图解，通俗易懂。本书对每个算法的基本操作都有全彩图解。通过图解，许多问题都变得简单，可迎刃而解。
（2）实例丰富，简单有趣。本书结合了大量竞赛实例，讲解如何用算法解决实际问题，使复杂难懂的问题变得简单有趣，可帮助读者轻松掌握算法知识，体会其中的妙处。
（3）深入浅出，透析本质。本书透过问题看本质，重点讲解如何分析和解决问题。本书采用了简洁易懂的代码，对数据结构的设计和算法的描述全面、细致，而且有算法复杂度分析及优化过程。
（4）实战演练，循序渐进。本书在讲解每个算法后都进行了实战演练，使读者在实战中体会算法的设计思路和使用技巧，从而提高独立思考、动手实践的能力。书中有丰富的练习题和竞赛题，可帮助读者及时检验对所学知识的掌握情况，为从小问题出发且逐步解决大型复杂性工程问题奠定基础。
（5）网络资源，技术支持。本书为读者提供了配套源码、课件、视频，并提供了博客、微信群、QQ群技术支持，可随时为读者答疑解惑。
——建议和反馈——
写书是极其琐碎、繁重的工作，尽管笔者已经竭力使本书内容、网络资源和技术支持接近完美，但仍然可能存在很多漏洞和瑕疵。欢迎读者反馈关于本书的意见，因为这有利于我们改进和提高，以帮助更多的读者。如果对本书有意见和建议，或者有问题需要帮助，则都可以加入QQ群281607840，也可以致信rainchxy@126.com与笔者交流，笔者将不胜感激。
对于本书提供的读者资源，可参照本书封底的“读者服务”信息获取。
——致谢——
感谢笔者的家人和朋友在本书写作过程中提供的大力支持。感谢电子工业出版社工作严谨、高效的张国霞编辑，她的认真、负责促成了本书的早日出版。感谢中国计算机学会常务理事李轩涯老师的帮助。感谢码蹄集平台的大力支持。感谢提供了宝贵意见的同事们。感谢提供了技术支持的同学们。感恩遇到这么多良师益友！

第1章 STL 1
1.1 deque（双端队列） 1
训练度度熊学队列 1
1.2 priority_queue（优先队列） 4
训练1 第k大的数 4
训练2 表演评分 6
1.3 bitset（位图） 7
1.3.1 定义和初始化 8
1.3.2 基本操作 9
训练集合运算 10
1.4 set、multiset（集合、多重集合） 12
训练1 集合合并 13
训练2 并行处理 14
1.5 map、multimap（映射、多重映射） 16
训练1 硬木种类 18
训练2 水果 19
1.6 STL中的常用函数 21
1.6.1 fill() 21
1.6.2 nth_element() 22
1.6.3 lower_bound()、upper_bound() 23
1.6.4 next_permutation()、pre_permutation() 23
训练1 中位数 25
训练2 字谜 26

第2章实用的数据结构 28
2.1 并查集 28
训练1 畅通工程 33
训练2 方块栈 35
2.2 倍增、稀疏表（ST）、区间最值查询（RMQ） 38
2.2.1 倍增 38
2.2.2 稀疏表 39
2.2.3 区间最值查询 41
训练1 区间最值差 41
训练2 最频繁值 42
2.3 最近公共祖先（LCA） 45
2.3.1 暴力搜索法 46
2.3.2 树上倍增法 47
2.3.3 在线区间最值查询算法 51
2.3.4 离线Tarjan算法 53
训练1 最近公共祖先 57
训练2 树上距离 59
2.4 树状数组 61
2.4.1 一维树状数组 61
2.4.2 多维树状数组 67
训练1 数星星 68
训练2 矩形区域查询 70
2.5 线段树 71
2.5.1 基本操作 71
2.5.2 懒操作 76
训练1 敌兵布阵 80
训练2 简单的整数问题 83

第3章查找算法 85
3.1 散列表 85
3.1.1 散列函数 86
3.1.2 开放地址法 88
3.1.3 链地址法 96
3.1.4 建立公共溢出区 98
3.1.5 散列查找及其性能分析 98
训练雪花 99
3.2 字符串模式匹配 100
3.2.1 BF算法 101
3.2.2 KMP算法 103
训练1 统计单词数 109
训练2 字符串匹配 111
3.3 字典树（Trie树） 112
3.3.1 创建 113
3.3.2 查找 115
3.3.3 应用 116
训练单词翻译 116

第4章平衡树 118
4.1 树高与性能 118
4.2 平衡二叉搜索树（AVL树） 119
4.2.1 调整平衡的方法 120
4.2.2 插入 122
4.2.3 创建 126
4.2.4 删除 128
训练双重队列 131
4.3 树堆（Treap） 134
4.3.1 右旋和左旋 135
4.3.2 插入 136
4.3.3 删除 138
4.3.4 前驱 140
4.3.5 后继 140
训练少林功夫 141
4.4 伸展树（Splay树） 144
4.4.1 时空局部性的原理 144
4.4.2 右旋和左旋 145
4.4.3 伸展 146
4.4.4 查找 149
4.4.5 插入 150
4.4.6 分裂 150
4.4.7 合并 150
4.4.8 删除 151
4.4.9 区间操作 151
4.4.10 算法分析 152
训练1 玩链子 152
训练2 超强记忆 159

第5章图论提高 169
5.1 连通图与强连通图 169
5.2 桥与割点 170
5.3 双连通分量的缩点 171
5.4 Tarjan算法 172
5.4.1 无向图的桥 173
5.4.2 无向图的割点 174
5.4.3 有向图的强连通分量 175
训练1 道路建设 177
训练2 校园网络 180

第6章图论算法 183
6.1 最小生成树 183
6.1.1 Prim算法 184
6.1.2 Kruskal算法 191
训练1 丛林之路 195
训练2 联网 197
6.2 最短路径 199
6.2.1 Dijkstra算法 199
6.2.2 Floyd算法 204
6.2.3 Bellman-Ford算法 208
6.2.4 SPFA算法 209
训练1 重型运输 211
训练2 货币兑换 212
训练3 虫洞 214
6.3 拓扑排序 216
训练1 家族树 220
训练2 标签球 222
6.4 关键路径 224
训练1 指令安排 232
训练2 家务琐事 233

第7章搜索算法提高 235
7.1 剪枝优化 235
训练1 数独游戏 235
训练2 小木棍 238
7.2 嵌套广度优先搜索 240
训练推箱子 240
7.3 双向广度优先搜索 244
训练魔鬼Ⅱ 244
7.4 启发式搜索 246
7.4.1 A*算法 247
7.4.2 IDA*算法 247
训练1 八数码问题 248
训练2 第k短路径 257

第8章动态规划提高 260
8.1 树形动态规划 260
训练1 战略游戏 260
训练2 工人请愿书 262
8.2 状态压缩动态规划 264
训练1 旅行商问题 265
训练2 玉米田 269
8.3 动态规划优化 271
8.3.1 倍增优化 272
8.3.2 数据结构优化 272
8.3.3 单调队列优化 272
训练1 最长公共上升子序列 273
训练2 滑动窗口 275