《高效算法：竞赛、应试与提高必修128例》是一本对于提升Python编程技巧和算法能力非常有益的法国畅销书。这本书以128个简单实用的算法实例为基础，透彻讲解了基于Python的高效算法思路和编程要点。通过学习本书，读者可以战胜编程竞赛中的技术难关。本书还在线提供更多趣题和拓展实战例子，帮助读者进一步巩固所学知识。这些算法实例的讲解源自国际编程大赛导师的经验精髓，使得读者能够从中得到更深层次的启发和指导。对于那些希望提升编程技能和算法水平的读者来说，这本书是一本不可多得的参考书。
高效算法：竞赛、应试与提高必修128例 电子书
读者评价
优点：选的这100来道题，算是比较有代表性的算法。还是有眼光的。缺点：里面代码，有些跑不通的
有些code是跑不动的，思路挺好的，也有让我惊呼"竟然还可以这样"的地方。中规中矩吧。
我很生气，第34页经典的KMP算法就是错的...while下面多敲了两个tab把不该放进循环的放进来了...我才刚刚开始看就发现问题了
内容介绍
本书旨在探讨如何优化算法效率，详细阐述了经典算法和特殊算法的实现、应用技巧和复杂度验证过程，内容由浅入深，能帮助读者快速掌握复杂度适当、正确率高的高效编程方法以及自检、自测技巧，是参加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
考虑以下在树上行走的随机过程： 1. 起始位置在根节点。 2. 如果现在位置在任何一个叶节点 (leaf node) 上，则结束。 3. 令现在所在的节点通往子节点i的边为 ei，其权重为 vi。 4. 定义 P(ei) 为选择到边 ei 的概率，以 P(ei)=vi/(2×105) 的概率分布随机选择一条边，移动至对应的子节点。 5. 跳至第 2. 步骤。 接下来我们定义以下的操作： 1. 选定一个非叶节点 2. 将这个节点所有通往子节点的边的权重随意重新排序，亦即可以无限次地交换彼此之间的权重，但不能改变权重的大小。 给定一个固定的 X 值，请对于每个叶节点分开考虑以下问题： 如果能进行至多 X 次的操作，那到达这个叶节点的概率最大可以多大呢？
使用大O符号来衡量算法效率 大O符号标记可以基于输入的大小得到一种衡量算法时间复杂度的函数。可以忽略函数中的倍乘常量和非主导项。其本质是比较算法之间的增长率。对于一个线性查找的算法，其时间复杂度表示方法为O(n)，读作“n阶”。 - 最佳情况输入：导致最短执行时间的输入 - 最差情况输入：导致最长执行时间的输入，可以确定算法不会比最差情况还慢 分析通常针对最坏情况进行。大O符号允许忽略非主导部分（例如，表达式n-1中的-1），并强调重要部分（例如，表达式n-1中的n），因此，该算法的复杂度为O(n)。如果执行时间与输入规模无关就称该算法耗费了常量时间，用符号O(1)表示。