内容简介

本书旨在探讨如何优化算法效率，详细阐述了经典算法和特殊算法的实现、应用技巧和复杂度验证过程，内容由浅入深，能帮助读者快速掌握复杂度适当、正确率高的高效编程方法以及自检、自测技巧，是参加ACM/ICPC、Google Code Jam等国际编程竞赛、备战编程考试、提高编程效率、优化编程方法的参考书目。

目录

第 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 使用字典树进行拼写纠正　31
2　4 KMP（Knuth-Morris-Pratt）模式匹配算法　33
2　5 最大边的 KMP 算法　35
2　6 字符串的幂　38
2　7 模式匹配算法：Rabin?CKarp 算法　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
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 最大流算法　119
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
第　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

文档截图