算法训练营:海量图解+竞赛刷题(进阶篇)
  • 推荐1
  • 收藏2
  • 浏览444

算法训练营:海量图解+竞赛刷题(进阶篇)

陈小玉 (作者) 

  • 书  号:978-7-121-40886-1
  • 出版日期:2021-05-01
  • 页  数:656
  • 开  本:16(185*235)
  • 出版状态:正在印刷
  • 维护人:张国霞
本书以海量图解的形式,详细讲解常用的数据结构与算法,并结合竞赛实例引导读者进行刷题实战。通过对本书的学习,读者可掌握22种高级数据结构、7种动态规划算法、5种动态规划优化技巧,以及5种网络流算法,并熟练应用各种算法解决实际问题。
本书总计8章。第1章讲解实用数据结构,包括并查集、优先队列;第2章讲解区间信息维护与查询,包括倍增、ST、RMQ、LCA、树状数组、线段树和分块;第3章讲解字符串处理,包括字典树、AC自动机和后缀数组;第4章讲解树上操作问题,包括点分治、边分治、树链剖分和动态树;第5章讲解各种平衡二叉树,包括Treap、伸展树和SBT;第6章讲解数据结构进阶,包括KD树、左偏树、跳跃表、树套树和可持久化数据结构;第7章讲解动态规划及其优化,包括背包问题、线性DP、区间DP、树形DP、数位DP、状态压缩DP、插头DP和动态规划优化方法;第8章讲解网络流问题,包括常用网络流算法、二分图最大匹配、最大流最小割定理和最小费用最大流。本书对每个算法都进行详细图解并搭配竞赛实例,重点讲解如何分析问题、优化算法,以期读者在短时间内掌握该算法并进行刷题实战。
本书面向对算法感兴趣的读者,无论是想扎实内功或参加算法竞赛的学生,还是想进入行业领先企业的求职者,抑或是想提升技术的在职人员,都可以参考本书。若读者从未学过数据结构与算法方面的基础知识,则可参考《算法训练营:海量图解+竞赛刷题(入门篇)》。
内容多:涵盖数据结构、高级数据结构、经典算法
题量大:带您细刷300道竞赛题目
理解易:海量图解,一览算法细微变化
作者棒:已出版多本算法好书。
上手快:通过问题透析本质,通俗易懂,学习体会更轻松
陈小玉
南阳理工学院副教授,高级程序员,主要研究方向为算法优化和机器学习。出版著作有《趣学算法》《趣学数据结构》《算法训练营:海量图解+竞赛刷题(入门篇)》《算法训练营:海量图解+竞赛刷题(进阶篇)》,所教学生多次获得ACM、蓝桥杯等算法竞赛奖项。
近年来,算法行业非常火爆,越来越多的人在学习算法。目前,计算机的最重要领域之一是人工智能,而人工智能的核心是算法,算法已渗透到互联网、商业、金融业、航空、军事等各个领域,正在改变着这个世界。
写作背景
在IT领域,数据结构与算法的应用无处不在。数据结构与算法是计算机开发人员的基本功,很多面试都要考查数据结构与算法。学习数据结构与算法不仅可以培养我们的算法思维,提高我们分析问题、解决问题的能力,还可以让我们快速学习新技术,以更高的视角看待问题。
数据结构与算法教材一般晦涩难懂。为了让更多的人轻松学习算法、爱上算法,笔者写作了《趣学数据结构》《趣学算法》两本书。笔者发现,读者特别喜欢搭配了大量图解的通俗易懂的讲解方式。很多读者也在呼吁笔者写一本结合算法竞赛实例进行讲解的书。经过近两年的筹备,《算法训练营:海量图解+竞赛刷题(入门篇)》和《算法训练营:海量图解+竞赛刷题(进阶篇)》两本书终于要和大家见面了,非常感谢各位读者的大力支持。
学习建议
算法学习的过程,实际上是通过大量实例,充分体会遇到问题时该如何分析:采用什么数据结构,使用什么算法策略,算法的复杂性如何,是否有优化的可能,等等。这里有以下几个建议。
 第1个建议:学经典,多理解。
算法书有很多,初学者最好选择图解较多的入门书,当然,也可以选择多本书,从多个角度进行对比和学习。先看书中的图解,理解各种经典问题的求解方法,如果还不明白,则可以看视频讲解,理解之后再看代码,尝试自己动手上机运行。如有必要,则可以将算法的求解过程通过图解方式展示出来,以加深对算法的理解。
 第2个建议:看题解,多总结。
在掌握书中的经典算法之后,可以在刷题网站进行专项练习,比如贪心算法、分治算法、动态规划、网络流等。算法比数据结构更加灵活,对同一道题目可以采用不同的算法解决,算法复杂性也不同。如果想不到答案,则可以看题解,比较自己的想法与题解的差距。要多总结题目类型及最优解法,然后找相似的题目并自己动手解决问题。
 第3个建议:举一反三,灵活运用。
通过专项刷题,见多识广,总结常用的算法模板,熟练应用套路,举一反三、灵活运用,逐步提升刷题速度,力争“bug free”(无缺陷)。
如何进行刷题实战
刷题的过程就是熟练应用数据结构与算法的过程。在刷题过程中,要学会分析问题、解决问题的方法,总结常用的算法模板和套路,快速写出代码,通过锻炼达到“bug free”。可以集中时间进行系统性专项刷题,不可三天打鱼、两天晒网,也不可随机刷题。题不在多,在于精。通过看书掌握一种数据结构与算法之后,便可找该知识相关的简单题目试手,从易到难。刷题时,可以先在编译系统中编译通过,等测试用例通过且检查无误后再提交,因为在比赛中多次提交会被罚时。刷题网站有很多,算法竞赛刷题网站有Vjudge、POJ、HDU、Code Forces、洛谷等,找工作刷题网站有LeetCode。提交结果类型如下。
 AC(Accepted):通过。
 WA(Wrong Answer):答案错误。
 TLE(Time Limit Exceed):超时。
 OLE(Output Limit Exceed):超过输出限制。
 MLE(Memory Limit Exceed):超出内存。
 RE(Runtime Error):运行时错误。
 PE(Presentation Error):格式错误。
 CE(Compile Error):无法编译。
测试用例通过而提交不通过是很正常的,因为在测试用例中仅有一两组数据,而在后台有大量测试数据。遇到提交不通过的情况时,要首先根据提示判断错误类型,根据错误类型分析原因;然后冷静分析算法逻辑、易错点、特殊情况判断等,看看选择的数据结构和算法是否合适,是否存在死循环。在刷题过程中会发现很多“坑”,一定要记录下来,避免下次“踩坑”。
看题目时要看数据规模、时间限制和空间限制,看看设计的算法是否会超时超限,做到心中有数。如果限制时间为1s,则问题规模(n)和算法时间复杂度之间的关系如下。
 n≤11:O(n!)。
 n≤25:O(2n)。
 n≤5000:O(n2)。
 n≤106:O(nlogn)。
 n≤107:O(n)。
 n>108:O(logn)。
本书特色
本书具有以下特色。
(1)完美图解,通俗易懂。本书对每个算法的基本操作都有图解演示,通过图解,许多问题都变得简单,可迎刃而解。
(2)实例丰富,简单有趣。本书结合大量竞赛实例,讲解如何利用数据结构与算法解决实际问题,使复杂难懂的问题变得简单有趣,帮助读者轻松掌握算法知识,体会其中的妙处。
(3)深入浅出,透析本质。本书透过问题看本质,重点讲解如何分析和解决问题。本书采用了简洁易懂的代码,对数据结构设计和算法的描述全面细致,而且有算法复杂性分析及优化过程。
(4)实战演练,循序渐进。本书在对每个数据结构与算法讲解清楚后,都进行了实战演练,使读者在实战中体会数据结构与算法的设计和操作,从而提高独立思考、动手实践的能力。书中有丰富的练习题和竞赛题,可帮助读者及时检验知识掌握情况,为从小问题出发,逐步解决大型复杂性工程问题奠定基础。
(5)网络资源,技术支持。本书为读者提供书中所有范例程序的源代码、竞赛题及答案解析,读者对这些源代码可以自由修改编译,以符合自己的需要。本书提供博客、微信群、QQ群技术支持,可随时为读者答疑解惑。
建议和反馈
写书是极其琐碎、繁重的工作,尽管笔者已经尽力使本书的内容和网络支持接近完美,但仍然可能存在很多漏洞和瑕疵。欢迎读者提供关于本书的反馈意见,因为对本书的评论和建议都有利于我们改进和提高,以帮助更多的读者。如果对本书有什么评论和建议,或者有问题需要帮助,则可以致信rainchxy@126.com与笔者交流,笔者将不胜感激。
读者资源请参照本书封底提示。
致谢
感谢笔者的家人和朋友在本书写作过程中提供的大力支持。感谢电子工业出版社工作严谨、高效的张国霞编辑促成本书的早日出版。感谢提供宝贵意见的同事们。感谢提供技术支持的同学们。感恩遇到这么多良师益友!

目录

第1章 实用数据结构 1
1.1 并查集 1
原理 并查集详解 1
训练1 畅通工程 6
训练2 方块栈 7
训练3 食物链 10
训练4 帮派 16
1.2 优先队列 19
原理1 优先队列的实现原理 19
原理2 优先队列详解 23
训练1 第k大的数 26
训练2 围栏修复 27
训练3 表演评分 29
训练4 丛林探险 30

第2章 区间信息维护与查询 33
2.1 倍增、ST、RMQ 33
原理1 倍增 33
原理2 ST 34
原理3 RMQ 36
训练1 区间最值差 36
训练2 最频繁值 37
训练3 最小分段数 40
训练4 二维区间最值差 41
2.2 最近公共祖先LCA 43
原理1 暴力搜索法 44
原理2 树上倍增法 45
原理3 在线RMQ算法 49
原理4 Tarjan算法 51
训练1 最近公共祖先 55
训练2 树上距离 57
训练3 距离查询 59
训练4 城市之间的联系 60
2.3 树状数组 62
原理1 一维树状数组 62
原理2 多维树状数组 67
训练1 数星星 69
训练2 公路交叉数 71
训练3 子树查询 74
训练4 矩形区域查询 76
2.4 线段树 78
原理1 线段树的基本操作 78
原理2 线段树中的“懒操作” 83
训练1 敌兵布阵 87
训练2 简单的整数问题 89
训练3 数据结构难题 91
训练4 颜色统计 97
2.5 分块 102
原理 分块详解 102
训练1 简单的整数问题 105
训练2 数字序列 106
训练3 区间最值差 107
训练4 超级马里奥 109
训练5 序列操作 111

第3章 字符串处理 115
3.1 字典树 115
原理 字典树详解 115
训练1 单词翻译 120
训练2 电话表 122
训练3 统计难题 123
训练4 彩色的木棒 124
训练5 最长xor路径 127
3.2 AC自动机 129
原理 AC自动机详解 129
训练1 关键字检索 132
训练2 病毒侵袭 134
训练3 DNA序列 136
训练4 单词情结 140
3.3 后缀数组 145
原理1 基数排序 145
原理2 后缀数组详解 152
训练1 牛奶模式 169
训练2 口吃的外星人 171
训练3 音乐主题 173
训练4 星际迷航 175

第4章 树上操作 178
4.1 点分治 178
原理 重心分解 178
训练1 树上两点之间的路径数 179
训练2 游船之旅 185
训练3 摩天大树 189
训练4 查询子树 194
4.2 边分治 200
原理 边分治详解 200
训练1 树上查询I 203
训练2 树上查询II 212
训练3 树上两点之间的路径数 217
4.3 树链剖分 221
原理 树链剖分详解 221
训练1 树上距离 230
训练2 树的统计 231
训练3 家庭主妇 232
训练4 树上操作 233
4.4 动态树 236
原理 动态树详解 236
训练1 距离查询 247
训练2 动态树xor和 249
训练3 动态树的最值 252
训练4 动态树的第2大值 255
训练5 树上操作 261

第5章 平衡二叉树 263
5.1 Treap 263
原理 Treap详解 263
训练1 双重队列 270
训练2 普通平衡树 272
训练3 黑盒子 276
训练4 少林功夫 279
5.2 伸展树 283
原理 伸展树详解 283
训练1 双重队列 291
训练2 玩链子 293
训练3 超强记忆 300
训练4 循环 310
5.3 SBT 324
原理 SBT详解 324
训练1 双重队列 331
训练2 第k小的数 333
训练3 第k大的数 334
训练4 区间第k小 334
训练5 郁闷的出纳员 336

第6章 数据结构进阶 339
6.1 KD树 339
原理 KD树详解 339
训练1 最近的取款机 343
训练2 找旅馆 346
训练3 最近邻M点 348
训练4 蚁巢 349
6.2 左偏树 352
原理 左偏树详解 352
训练1 猴王 360
训练2 小根堆 363
训练3 路面修整 365
训练4 K-单调 369
6.3 跳跃表 373
原理 跳跃表详解 373
训练1 双重队列 379
训练2 第k大的数 381
训练3 郁闷的出纳员 386
6.4 树套树 388
原理 树套树详解 388
训练1 动态区间问题 389
训练2 动态区间第k小 395
训练3 矩形区域查询 396
训练4 马赛克处理 400
6.5 可持久化数据结构 406
原理1 可持久化线段树详解 406
原理2 可持久化Trie详解 413
训练1 超级马里奥 415
训练2 记忆重现 419
训练3 最大异或和 424

第7章 动态规划及其优化 431
7.1 动态规划求解原理 431
原理1 动态规划的三个要素 432
原理2 动态规划设计方法 432
7.2 背包问题 433
原理1 01背包 433
训练1 骨头收藏家 441
原理2 完全背包 443
训练2 存钱罐 443
原理3 多重背包 445
训练3 硬币 447
原理4 分组背包 449
训练4 价值最大化 450
原理5 混合背包 452
训练5 最少的硬币 452
7.3 线性DP 455
训练1 超级楼梯 455
训练2 数字三角形 456
训练3 最长上升子序列 458
训练4 最长公共子序列 461
训练5 最大连续子段和 462
7.4 区间DP 464
训练1 回文 464
训练2 括号匹配 466
训练3 猴子派对 468
训练4 乘法难题 470
7.5 树形DP 472
训练1 别墅派对 473
训练2 战略游戏 476
训练3 工人请愿书 478
训练4 完美的服务 480
训练5 背包类树形DP 484
训练6 苹果树 487
训练7 二次扫描与换根 490
训练8 最远距离 494
7.6 数位DP 497
训练1 不吉利的数字 498
训练2 定时炸弹 503
训练3 Round Numbers 506
训练4 计数问题 508
训练5 数字权值 511
7.7 状态压缩DP 513
训练1 旅行商问题 514
训练2 旅行商变形1 520
训练3 旅行商变形2 521
训练4 玉米田 523
训练5 炮兵阵地 525
训练6 马车旅行 528
7.8 插头DP 531
训练1 铺砖 531
训练2 方格取数 537
训练3 多回路连通性问题 539
训练4 单回路连通性问题 543
训练5 单通路连通性问题 550
7.9 动态规划优化 552
原理1 倍增优化 552
原理2 数据结构优化 552
训练1 最长公共上升子序列 552
训练2 有序子序列 554
训练3 最大化器 557
训练4 洒水装置 559
原理3 单调队列优化 562
训练5 滑动窗口 563
训练6 洒水装置 564
训练7 股票交易 565
原理4 斜率优化 568
训练8 打印文章 569
训练9 覆盖走道 573
训练10 批处理调度 575
训练11 划分 580
训练12 劳伦斯 583
原理5 四边不等式优化 587
训练13 划分 590

第8章 网络流 592
8.1 EK算法 595
原理 EK算法详解 595
训练1 最大流问题 600
训练2 排水系统 600
8.2 Dinic算法 601
原理 Dinic算法详解 601
训练1 最大销售量 605
训练2 电力网络 606
8.3 ISAP算法 608
原理 ISAP算法详解 608
训练1 岛屿运输 613
训练2 美味佳肴 614
训练3 跳跃蜥蜴 615
训练4 计算机工厂 618
8.4 二分图匹配 619
原理1 最大匹配算法 620
原理2 匈牙利算法 621
训练1 完美的牛棚 624
训练2 机器调度 625
训练3 逃脱 626
8.5 最大流最小割 627
原理 最大流最小割定理 627
训练1 最小边割集 629
训练2 最小点割集 631
训练3 双核CPU 632
训练4 最大收益 633
8.6 最小费用最大流 635
原理 最小费用路算法 635
训练1 农场之旅 639
训练2 航空路线 640
训练3 区间覆盖 642
训练4 疏散计划 643

读者评论

相关图书

解忧程序员——高薪编程、求职面试与成长转型宝典

安晓辉 (作者)

本书是专为程序员而编写的。全书浅显易懂,深入浅出,书中从各个角度,全面地解读了程序员这个特定人群,在日常程序设计工作中遇到的种种问题及解决办法,如何设计代码,如...

¥39.00

快学Scala(第2版)

Cay S. Horstmann (作者) 高宇翔 (译者)

Scala是一门主要以Java虚拟机(JVM)为目标运行环境并将面向对象和函数式编程语言的最佳特性结合在一起的编程语言。你可以使用Scala编写出更加精简的程序...

¥108.00

产品之路:从靠谱想法到产品落地再到产品推广

于琪 (作者)

本书将产品领域里大家耳熟能详但很可能一知半解的概念串联起来,并整合到一个框架中,讲述如何将用户的问题变为产品设想,并基于此设想实现一个产品,然后将产品进行市场推...

¥79.00

算法神探:一部谷歌首席科学家写给程序员的小说

Jeremy Kubica (作者) 啊哈磊 李嘉浩 (译者)

本书围绕程序设计典型算法,精心编织了一个扣人心弦又趣味横生的侦探缉凶故事。小说主人公运用高超的搜索技巧和精深的算法知识,最终识破阴谋、缉拿元凶。其间,用二分搜索...

¥45.00

大数据时代的算法:机器学习、人工智能及其典型实例

刘凡平 张启玉 刘刚 (作者)

本书介绍在互联网行业中经常涉及的算法,包括排序算法、查找算法、资源分配算法、路径分析算法、相似度分析算法,以及与机器学习相关的算法,包括数据分类算法、聚类算法、...

¥49.00

啊哈C语言!逻辑的挑战(修订版)

纪磊 (作者)

这是一本非常有趣的编程启蒙书,全书从中小学生的角度来讲述,没有生涩的内容,取而代之的是生动活泼的漫画和风趣幽默的文字。并配合超萌的编程软件,从开始学习与计算机对...

¥31.50