高效算法：竞赛、应试与提高必修128例

【实例简介】高效算法：竞赛、应试与提高必修128例

高效算法 竞赛 应试 提高必修

版权声明

译者序
序
第 1 章　引言
1.1　编程竞赛
1.1.1　线上学习网站
1.1.2　线上裁判的返回值
1.2　我们的选择：Python
1.3　输入输出
1.3.1　读取标准输入
1.3.2　显示格式
1.4　复杂度
1.5　抽象类型和基本数据结构
1.5.1　栈
1.5.2　字典
1.5.3　队列
1.5.4　优先级队列和最小堆
1.5.5　并查集
1.6　技术
1.6.1　比较
1.6.2　排序
1.6.3　扫描
1.6.4　贪婪算法
1.6.5　动态规划算法
1.6.6　用整数编码集合
1.6.7　二分查找
1.7　建议
1.8　走得更远
第 2 章　字符串
2.1　易位构词
2.2　T9：9 个按键上的文字
2.3　使用字典树进行拼写纠正
2.4　KMP（Knuth-Morris-Pratt）模式匹配算法
2.5　最大边的 KMP 算法
2.6　字符串的幂
2.7　模式匹配算法：Rabin-Karp 算法
2.8　字符串的最长回文子串：Manacher 算法
第 3 章　序列
3.1　网格中的最短路径
3.2　编辑距离（列文斯登距离）
3.3　最长公共子序列
3.4　升序最长子序列
3.5　两位玩家游戏中的必胜策略
第 4 章　数组
4.1　合并已排序列表
4.2　区间的总和
4.3　区间内的重复内容
4.4　区间的最大总和
4.5　查询区间中的最小值：线段树
4.6　计算区间的总和：树状数组（Fenwick 树）
4.7　有 k 个独立元素的窗口
第 5 章　区间
5.1　区间树（线段树）
5.2　区间的并集
5.3　区间的覆盖
第 6 章　图
更多电子书请搜索「慧眼看」www.huiyankan.com 微信：huiyankan
6.1　使用 Python 对图编码
6.2　使用 C 或 Java 对图编码
6.3　隐式图
6.4　深度优先遍历：深度优先算法
6.5　广度优先遍历：广度优先算法
6.6　连通分量
6.7　双连通分量
6.8　拓扑排序
6.9　强连通分量
6.10　可满足性
第 7 章　图中的环
7.1　欧拉路径
7.2　中国邮差问题
7.3　最小长度上的比率权重环：Karp 算法
7.4　单位时间成本最小比率环
7.5　旅行推销员问题
第 8 章　最短路径
8.1　组合的属性
8.2　权重为 0 或 1 的图
8.3　权重为正值或空值的图：Dijkstra 算法
8.4　随机权重的图：Bellman-Ford 算法
8.5　所有源点 - 目标顶点对：Floyd-Warshall 算法
8.6　网格
8.7　变种问题
8.7.1　无权重图
8.7.2　有向无环图
8.7.3　最长路径
8.7.4　树中的最长路径
8.7.5　最小化弧上权重的路径
8.7.6　顶点有权重的图
8.7.7　令顶点上最大权重最小的路径
8.7.8　所有边都属于一条最短路径
第 9 章　耦合性和流
9.1　二分图最大匹配
9.2　最大权重的完美匹配：Kuhn-Munkres 算法
9.3　无交叉平面匹配
9.4　稳定的婚姻：Gale-Shapley 算法
9.5　Ford-Fulkerson 最大流算法
9.6　Edmonds-Karp 算法的最大流
9.7　Dinic 最大流算法
9.8　s-t 最小割
9.9　平面图的 s-t 最小割
9.10　运输问题
9.11　在流和匹配之间化简
9.12　偏序的宽度：Dilworth 算法
第 10 章　树
10.1　哈夫曼编码
10.2　最近的共同祖先
10.3　树中的最长路径
10.4　最小权重生成树：Kruskal 算法
第 11 章　集合
11.1　背包问题
11.2　找零问题
11.3　给定总和值的子集
11.4　k 个整数之和
第 12 章　点和多边形
更多电子书请搜索「慧眼看」www.huiyankan.com 微信：huiyankan
12.1　凸包问题
12.2　多边形的测量
12.3　最近点对
12.4　简单直线多边形
第 13 章　长方形
13.1　组成长方形
13.2　网格中的最大正方形
13.3　直方图中的最大长方形
13.4　网格中的最大长方形
13.5　合并长方形
13.6　不相交长方形的合并
第 14 章　计算
14.1　最大公约数
14.2　贝祖等式
14.3　二项式系数
14.4　快速求幂
14.5　素数
14.6　计算算数表达式
14.7　线性方程组
14.8　矩阵序列相乘
第 15 章　穷举
15.1　激光路径
15.2　精确覆盖
15.3　数独
15.4　排列枚举
15.5　正确计算
调试工具
参考文献