实例介绍
【实例简介】高效算法：竞赛、应试与提高必修128例
【实例截图】
【核心代码】
目录
第 1 章 引言............................................................................................................................................... 1
1.1 编程竞赛............................................................................................................................1
1.1.1 线上学习网站.........................................................................................................3
1.1.2 线上裁判的返回值 .................................................................................................4
1.2 我们的选择：Python.......................................................................................................5
1.3 输入输出............................................................................................................................6
1.3.1 读取标准输入.........................................................................................................6
1.3.2 显示格式................................................................................................................9
1.4 复杂度................................................................................................................................9
1.5 抽象类型和基本数据结构 .............................................................................................11
1.5.1 栈.........................................................................................................................11
1.5.2 字典.....................................................................................................................12
1.5.3 队列.....................................................................................................................12
1.5.4 优先级队列和最小堆............................................................................................13
1.5.5 并查集 .................................................................................................................16
1.6 技术..................................................................................................................................18
1.6.1 比较.....................................................................................................................18
1.6.2 排序.....................................................................................................................18
1.6.3 扫描.....................................................................................................................19
1.6.4 贪婪算法..............................................................................................................20
1.6.5 动态规划算法.......................................................................................................20
1.6.6 用整数编码集合...................................................................................................21
1.6.7 二分查找..............................................................................................................23
1.7 建议..................................................................................................................................25
1.8 走得更远..........................................................................................................................27
第 2 章 字符串....................................................................................................................................... 28
2.1 易位构词..........................................................................................................................28
2.2 T9：9 个按键上的文字...................................................................................................29
2.3 使用字典树进行拼写纠正 .............................................................................................31vi 高效算法：竞赛、应试与提高必修 128 例
2.4 KMP（Knuth-Morris-Pratt）模式匹配算法..............................................................33
2.5 最大边的 KMP 算法.......................................................................................................35
2.6 字符串的幂......................................................................................................................38
2.7 模式匹配算法：Rabin–Karp 算法 ...............................................................................38
2.8 字符串的最长回文子串：Manacher 算法 ..................................................................42
第 3 章 序列............................................................................................................................................ 44
3.1 网格中的最短路径 .........................................................................................................44
3.2 编辑距离（列文斯登距离）
...........................................................................................45
3.3 最长公共子序列 .............................................................................................................47
3.4 升序最长子序列 .............................................................................................................49
3.5 两位玩家游戏中的必胜策略 .........................................................................................52
第 4 章 数组............................................................................................................................................ 53
4.1 合并已排序列表 .............................................................................................................53
4.2 区间的总和......................................................................................................................54
4.3 区间内的重复内容 .........................................................................................................54
4.4 区间的最大总和 .............................................................................................................55
4.5 查询区间中的最小值：线段树......................................................................................55
4.6 计算区间的总和：树状数组（Fenwick 树）
................................................................57
4.7 有 k 个独立元素的窗口 .................................................................................................59
第 5 章 区间............................................................................................................................................ 61
5.1 区间树（线段树）
...........................................................................................................61
5.2 区间的并集......................................................................................................................64
5.3 区间的覆盖......................................................................................................................64
第 6 章 图................................................................................................................................................. 66
6.1 使用 Python 对图编码...................................................................................................66
6.2 使用 C 或 Java 对图编码 .........................................................................................67
6.3 隐式图..............................................................................................................................68
6.4 深度优先遍历：深度优先算法......................................................................................69
6.5 广度优先遍历：广度优先算法......................................................................................70
6.6 连通分量..........................................................................................................................71目录 vii
6.7 双连通分量......................................................................................................................74
6.8 拓扑排序..........................................................................................................................77
6.9 强连通分量......................................................................................................................79
6.10 可满足性 .......................................................................................................................84
第 7 章 图中的环.................................................................................................................................. 86
7.1 欧拉路径..........................................................................................................................86
7.2 中国邮差问题..................................................................................................................88
7.3 最小长度上的比率权重环：Karp 算法........................................................................89
7.4 单位时间成本最小比率环 .............................................................................................92
7.5 旅行推销员问题 .............................................................................................................93
第 8 章 最短路径.................................................................................................................................. 94
8.1 组合的属性......................................................................................................................94
8.2 权重为 0 或 1 的图.........................................................................................................96
8.3 权重为正值或空值的图：
Dijkstra 算法........................................................................97
8.4 随机权重的图：Bellman-Ford 算法 .........................................................................100
8.5 所有源点 - 目标顶点对：Floyd-Warshall 算法......................................................101
8.6 网格................................................................................................................................102
8.7 变种问题........................................................................................................................104
8.7.1 无权重图............................................................................................................104
8.7.2 有向无环图 ........................................................................................................104
8.7.3 最长路径............................................................................................................104
8.7.4 树中的最长路径.................................................................................................104
8.7.5 最小化弧上权重的路径 ......................................................................................105
8.7.6 顶点有权重的图.................................................................................................105
8.7.7 令顶点上最大权重最小的路径 ...........................................................................105
8.7.8 所有边都属于一条最短路径...............................................................................105
第 9 章 耦合性和流...........................................................................................................................106
9.1 二分图最大匹配 ...........................................................................................................107
9.2 最大权重的完美匹配：
Kuhn-Munkres 算法............................................................110
9.3 无交叉平面匹配 ...........................................................................................................116
9.4 稳定的婚姻：Gale-Shapley 算法.............................................................................117
9.5 Ford-Fulkerson 最大流算法 ......................................................................................119viii 高效算法：竞赛、应试与提高必修 128 例
9.6 Edmonds-Karp 算法的最大流...................................................................................121
9.7 Dinic 最大流算法..........................................................................................................122
9.8 s-t 最小割 .....................................................................................................................125
9.9 平面图的 s-t 最小割 ....................................................................................................126
9.10 运输问题 .....................................................................................................................127
9.11 在流和匹配之间化简.................................................................................................127
9.12 偏序的宽度：Dilworth 算法......................................................................................129
第 10 章 树.............................................................................................................................................132
10.1 哈夫曼编码 .................................................................................................................133
10.2 最近的共同祖先 .........................................................................................................135
10.3 树中的最长路径 .........................................................................................................138
10.4 最小权重生成树：Kruskal 算法...............................................................................140
第 11 章 集合.......................................................................................................................................142
11.1 背包问题 .....................................................................................................................142
11.2 找零问题 .....................................................................................................................143
11.3 给定总和值的子集.....................................................................................................145
11.4 k 个整数之和 ..............................................................................................................146
第 12 章 点和多边形........................................................................................................................148
12.1 凸包问题 .....................................................................................................................149
12.2 多边形的测量 .............................................................................................................150
12.3 最近点对 .....................................................................................................................151
12.4 简单直线多边形 .........................................................................................................153
第 13 章 长方形..................................................................................................................................156
13.1 组成长方形 .................................................................................................................156
13.2 网格中的最大正方形.................................................................................................157
13.3 直方图中的最大长方形.............................................................................................158
13.4 网格中的最大长方形.................................................................................................159
13.5 合并长方形 .................................................................................................................160
13.6 不相交长方形的合并.................................................................................................164目录 ix
第 14 章 计算.......................................................................................................................................165
14.1 最大公约数 .................................................................................................................165
14.2 贝祖等式 .....................................................................................................................165
14.3 二项式系数 .................................................................................................................166
14.4 快速求幂 .....................................................................................................................167
14.5 素数 .............................................................................................................................167
14.6 计算算数表达式 .........................................................................................................168
14.7 线性方程组 .................................................................................................................170
14.8 矩阵序列相乘 .............................................................................................................174
第 15 章 穷举.......................................................................................................................................176
15.1 激光路径 .....................................................................................................................176
15.2 精确覆盖 .....................................................................................................................179
15.3 数独 .............................................................................................................................184
15.4 排列枚举 .....................................................................................................................186
15.5 正确计算 .....................................................................................................................188
调试工具 ...................................................................................................................................................191
参考文献 ...................................................................................................................................................192
好例子网口号：伸出你的我的手 — 分享！
相关软件
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论