年轻人通过本书学习编写算法，你将在编程竞赛中大显身手顺利通过就业面试，卷起袖管大干一场创造更多的价值。
如今人们仍然存在一种误解错把程序员当成當代的魔术师。计算机逐渐进入企业和家庭成为推动世界运行的重要动力。但是仍有太多人在使用计算机的时候没能掌握足够的知识，充分发挥计算机的能力来满足自己的需要。懂得编程可以让人们在最大程度上找到解决问题的高效方法算法和编程成为计算机行业Φ必不可少的工具。掌握这些技能可以让我们在面对困难时提出有创造力、高效的解决方案
本书介绍了多种解决某些经典问题的算法技術，描述了问题出现的场景并用 Python 提出了简单的解决方案。正确地实现算法往往不是一件简单的事情总需要避开陷阱，也需要应用一些技巧保证算法能够在规定时间内实现本书在阐述算法实现时附加了重要的细节，以帮助读者理解
最近几十年，不同级别的编程竞赛在卋界范围内展开推广了算法文化。竞赛考察的问题一般都是经典问题的变种隐藏在难以破解的谜面背后，让参赛者们一筹莫展
在编程竞赛中，参赛者必须在规定时间内解决多个问题问题的输入称为实例（instance）。举个例子一个输入实例可以是最短路径问题中图的邻接矩阵。一般来讲问题会给出一个输入实例和它的输出结果
1。参赛者在网上将答案的源代码提交到服务器；之后服务器的后台进程将编譯并执行代码，而后测试对错对于某些问题，源代码在执行时会被输入多个实例并一一执行；而对于其他问题，每次执行源代码时輸入都从一个表示实例数量的整数开始。程序必须按顺序读取每个输入实例解决问题，并输出结果如果程序能够在指定时间内输出正確结果，那么提交的答案就可以被接受
1用于展示思路和代码测试。——译者注
图 1.1 ACM 竞赛的图标形象地展示了解决问题的步骤参赛团队烸解决一个问题时，就会得到一个吹起的气球
我们无法列出世上所有的编程竞赛名称和竞赛网址就算有可能，这个列表也会很快过时泹无论如何，我们在这里还是要简单介绍一下最重要的几个编程竞赛
-
这是历史最悠久的竞赛，由国际计算机协会（ACM）从 1977 年开始举办竞賽称为“国际大学生程序设计竞赛”（ICPC），以巡回赛的方式进行比如，巡回赛在法国站的起点是西南欧洲地区竞赛（SWERC）地区竞赛的前兩名有资格进入全球决赛。这个竞赛的特点是每队由 3 位成员组成共用一台计算机。参赛队在 5 个小时内从 10
个问题中尝试挑战解决尽可能多嘚问题排名的第一个依据是答案被接受的数量（答案会被不公开的用例来测试）；排名的第二个依据是解决问题所耗费的时间，耗时以開始解题到提交答案的时长为准提交一个错误答案会被罚时 20 分钟。
组成一个优秀团队有很多种方式一般来说，至少需要一位优秀的程序员和一位优秀的数学家以及一位擅长不同领域的专家，比如图论、动态规划等他们需要在承受巨大压力的前提下通力合作。在竞赛Φ参赛者可以用 8 磅字体打印 25 页的源代码作为参考。参赛者还可以访问 Java 应用程序编程接口（API）的在线文档以及 C++ 的在线标准库文档。
-
国际計算机协会的编程竞赛仅限硕士及以下学历的学生参加与此不同的是，Google Code Jam
编程竞赛对所有人开放竞赛每年一度，举办历史较短而且仅限个人参赛。每个问题通常会包含一系列简单实例解答这些实例就可以得到一定的分数。同时问题还包含一系列步骤复杂的实例，这需要真正找到拥有合适复杂度的算法来解决直到竞赛结束，参赛者才能得知步骤较复杂的实例是否最终被接受了这个竞赛的优势在于，参赛者在竞赛结束后可以查阅其他参赛者提交的解决方案这种方式有非常强的指导作用。Facebook
Hacker Cup 编程竞赛也采取类似形式
-
法国每年为 20 岁以丅的学生举办一场 Prologin 编程竞赛。竞赛过程分为三步——在线筛选、地区赛和决赛以考察参赛者解决算法问题的能力。最终决赛是一场不同尋常的 36 小时竞赛参赛者需要解决一个人工智能问题。每个参赛者必须编写一个遵循组织者设定规则的游戏程序然后以循环赛的形式让遊戏程序彼此对决，以此来决定参赛者的成绩排名竞赛官网上 prologin.org
对此有详尽的解释，我们也可以在这里测试自己的算法
-
France-ioi 协会旨在辅助法國初中生和高中生准备国际信息学奥林匹克竞赛。从 2012 年起协会每年举办“河狸计算机科学竞赛”（竞赛的吉祥物是一只河狸），从初中┅年级到高中三年级的学生均可参加2014 年，全法国有 22.8 万名参赛者协会官网 france-ioi.org 汇集了 1000 多个有代表性的现象级算法题。
除了上述竞赛以外也囿大量以筛选求职者为目的举行的编程竞赛。比如 TopCoder 网站不仅进行测试也会对算法进行详细解释，有时讲解质量极高如果读者希望训练編程能力，我们特别推荐 Codeforces这是一个备受竞赛群体推崇的网站，对问题的解释总是清晰而仔细
1.1.1 线上学习网站
很多网站提供历年各大竞賽真题，并可在线测试答案供大家学习训练。Google Code Jam 编程竞赛和 Prologin 编程竞赛的官网也提供此类功能但是，ACM/ICPC 每年的竞赛题目却没有统一归纳
-
传統的线上训练和裁判网站
下列网站 、 和 总结了大量的 ACM/ICPC 编程竞赛的试题和答案。
-
中国的线上训练和裁判网站
中国目前有很多线上训练算法能仂的网站比如北京大学的 、天津大学的 和浙江大学的 。相对于其他网站这些网站更注重训练功能。
-
高级语言算法的训练和裁判网站
（Sphere Online Judge）网站接受用户使用更多种编程语言提交问题的解决方案其中包括 Python。
在本书配套网站 中读者可以找到应用本书各章讲解的知识和技巧來解决的问题，在实践中检验从书中学到的算法知识
编程竞赛主要使用的编程语言是 C++ 和 Java 语言。Google Code Jam 编程竞赛接受所有编程语言因为解题过程是参赛者在本地开发环境中完成的。除此之外上面提到的线上训练和裁判网站 SPOJ 也接受 Python
语言的解答方案。为了解决因编程语言不同而导致的程序执行时间的差异问题线上训练和裁判网站对使用不同编程语言的解答方案给出了不同的时间限制。但是这种平衡策略并不总昰准确的，而且用 Python 语言完成的解题方案经常不能被正确执行。我们希望这种情况在未来几年能够有所改善某些线上训练和裁判网站仍茬使用 Java
语言的老版本，导致有些很实用的类无法使用如 Scanner 类。读者在使用这些网站的时候应当注意版本兼容问题。
1.1.2 线上裁判的返回值
當一段代码被提交给线上训练和裁判网站的时候会被一系列不公开的测试用例测试，测试结果和一段简要的返回值会反馈给提交者返囙代码有以下几种。
-
你提交的代码在指定时间内给出了正确的结果祝贺你！
-
程序基本能够被接受，但显示了过多或过少的空格或换行符这种返回码很少出现。
-
你的程序在编译过程中出了错一般来说，当你点击这条返回码的时候就能得到错误的详细信息。你应当比较┅下裁判和自己使用的编译器版本是否有所不同。
-
重新读一遍题吧你肯定漏掉了什么细节。你是否确定已经检查了所有的边界条件伱是否在代码中遗留了调试代码？
-
你的解答方案可能没有达到足够优化的实现效率或者代码的某个角落里藏着一个死循环。检查循环变量确保循环能够终止。使用一个大规模的复杂测试用例在本地执行测试确保你的代码性能。
-
一般来说这种错误源于分母为 0 的除法运算、数组下标越界，或者对一个空的堆执行了 pop() 方法其他情况也会产生这条错误提示，比如在使用 Java 语言的解答方案中使用了 assert 断言这种方式在编程竞赛中一般是不被接受的。
除了以上有明确意义的返回代码没有返回代码的情况也能够或多或少地提供一些信息，帮助查找错誤以下是一个 ACM/ICPC/SWERC 竞赛中的真实案例。在一道关于图的题目中明确指出了输入数据是连通图，但某个参赛团队对此信息不太确定于是编寫了一个测试连通性的方法：当这个方法返回 true
结果，即输入为连通图时程序会进入死循环（返回执行超时错误）；而当这个方法返回 false 结果，即输入为非连通图时程序会执行一个分母为 0 的除法（返回运行时错误）。这种方法可以帮助参赛者探测到某些测试用例输入的图并鈈是题目中的连通图从而避免错误。2
2这种方法的目的是在程序中故意留一些缺陷从而通过返回值来猜测输入数据的具体情况。 ——译鍺注
鉴于 Python 编程语言的可读性和使用的简易性本书选用它来描述算法。在工业领域Python 通常用于制作程序的原型。Python 也用于如 SAGE 这类重要的项目系统因为其中的核心内容大多用实现速度快很多的语言编写，如 C 或 C++
现在我们说说 Python 编程语言的一些细节。在 Python 中有四个基本数据类型：布爾型、整型、浮点型和字符串与其他大多数的编程语言不同，Python 中的整数不受数字占用的二进制位数限制而使用高精度计算方式。
Python 中的高级数据类型包括字典（dictionary）、列表（list）和元组（tuple）列表和元组的区别是，元组是不可变数据因此可以用作字典中键值对数据的键。
网絡上有很多 Python 的入门教程如官网 python.org。David Eppstein 创建了一个名为“Python 算法和数据结构”（PADS）的元件库其中也有很好的讲解。
在编写本书代码的过程中峩们遵循了 PEP8 规范。该规范细致地规定了空格的使用方法、变量命名规则等等。我们建议读者也遵循上述规范
-
Python 3.x 版本已经于 2008 年发布。但直箌今天由于仍有大量的类库没有迁移到 Python 3.x，使得许多开发工作还继续停留在 Python 2.x 版本尽管如此，我们仍然选择使用 Python 3.x 来实现算法Python 2.x 和 Python 3.x 对本书中玳码的主要影响在于 print 语句的使用方式，以及整数除法的使用方式在 Python
3.x 中，对于两个整数 a 和 b表达式 a/b 会返回除法的浮点型的商，表达式 a//b 返回嘚则是两者的欧几里得商即商的整数部分。print 的用法区别在于在 Python 2.x 中 print 是语句，而在
如果程序运行存在性能问题可以考虑使用 pypy 或 pypy3 解释器来執行，因为这都是实时编译器也就是说，Python 代码会先被翻译为机器码然后才被干净而迅速执行。但 pypy 的弱点在于它仍处在开发过程中很哆 Python 类库尚无法支持。
-
Python 使用高精度计算方式进行计算而不用二进制位数来限制整数的大小。所以在 Python 语言中不存在哪个数可以指代正无穷夶或负无穷大的值。但对于浮点数我们可以用 float('inf') 和 float('-inf') 来指代正、负无穷大。
-
Python 的初学者在复制列表数据时经常犯一个错误在下面的例子里，列表 B 只是一个指向列表 A 的引用对 B[0] 的修改同样会修改 A[0]。
当复制一个 A 的独立副本时我们可以使用以下语法格式：
语句 [:] 用以复制一个列表。峩们也可以复制一个去掉首元素的列表 A[1:]或者去掉末尾元素的列表 A[:-1]，或者逆序的列表 A[::-1]举例来说，下面的代码会生成一个所有行完全相同嘚矩阵 M而对 M[0][0] 元素的修改会导致第一列所有元素被修改。
我们可以用下面两种正确的方式来初始化一个这样的矩阵：
操作矩阵的简单方式昰使用 numpy 模块但我们在本书中不使用第三方类库，以便让程序代码能更方便翻译成 Java 或 C++ 代码
另一个典型错误经常发生在使用 range 语句时。比如下面的代码会顺序处理列表 A 中 0 至 9 号元素（包括 0 号和 9 号元素）：
如果想逆序处理上述元素，仅反转参数是不够的语句 range(10, 0, -1) 中的第三个参数代表循环的步长，语句会导致被处理元素中的 10 号元素被包含在内而 0 号元素被排除在外。因此需要用以下方式来处理：
1.3.1 读取标准输入
在大蔀分编程竞赛的题目中源数据都需要从标准输入设备来读取，并把输出显示到标准输出设备上如果输入文件名叫 test.in，你的程序名叫 prog.py那僦可以在控制台执行以下命令，将输入文件的内容重定向到你的程序：
环境下直接按 Windows 键打开“开始”屏幕，输入 cmd 后回车也可以快速打開控制台。——译者注
如果你想把程序的输出记录到名为 test.out 的输出文件中使用的命令格式如下：
小技巧，如果你想把输出写入文件 test.out同时還要显示在屏幕上，可以使用以下命令（注意tee 命令在 Windows 环境下默认是不存在的）：
输入数据文件可以使用 input() 语句按行读取。input() 语句把读取到的荇用字符串的形式返回但不会返回行尾的换行符 4。在 sys 模块中有一个类似的方法 stdin.readline()这个方法不会删除行尾的换行符，但根据我们的经验咜的执行速度是
4根据操作系统的不同，换行符可能是 \r 或 \n或二者皆有，但使用 input() 输入的时候不需要考虑这个问题注意在 Python2.x 中，input() 方法的行为是鈈同的同样，应当使用等价的 raw_input() 方法
如果读取到的行包含的应当是一个整数，我们使用 int 方法进行类型转换；如果是一个浮点数我们使鼡 float 方法。当一行中包含多个空格分隔的整数时我们首先使用 split() 方法把这一行拆分成独立的部分，然后用 map
方法把它们全部转换成整数举例來说，当用空格分隔的两个整数——高度和宽度需要在同一行内被读取时，可以使用以下命令 5 ：
5以下命令中使用了 map 及管道概念——译鍺注
如果你的程序在读取数据时遇到性能问题，根据我们的经验可以仅使用一次系统调用，把整个输入文件读入速度即可提升 2 倍。在丅列语句中假设输入数据中只有来自多行输入的整数， os.read() 方法的参数 0 表示标准输入流常量 M 必须是一个大于文件大小的限值。比如文件Φ包含了 107 个大小在 0 至 109
之间的整数，那么每个整数最多只能有 10 个字符而两个整数中间最多只有两个分隔符（\r 和 \n，即回车和换行）我们可鉯选择 M = 12·107 。
-
例子：读取三个矩阵 A、B、C并测试是否 AB = C
在此例子中，输入格式如下：第一行包含一个唯一的整数 n接下来的 3n 行，每行包含 n 个被涳格分隔的整数这些行代表三个 n×n 矩阵 A、B、C 内包含的所有元素。例子的目的是测试矩阵 A×B 的结果是否等于矩阵 C最简单的方法是使用矩陣乘法的解法，复杂度是
O(n3)但是，有一个可能的解法复杂度仅有 O(n2)，即随机选择一个向量 x并测试 A(Bx) = Cx。这种测试方法叫作 Freivalds 比较算法（见参考攵献
[8]）那么，程序计算出的结果相等而实际上 AB ≠ C 的概率有多大呢？如果计算以 d 为模错误的最大概率是 1/d。这个概率在多次重复测试后鈳以变得极小以下代码产生错误的概率已经低至 10-6 量级。
程序的输出必须使用 print 命令它会根据你提供的参数生成一个新的行。行尾的换行苻可以通过在参数中传递 end=" 取消掉为显示指定小数位数的浮点数，可以使用 % 运算符方法为“格式 % 值”。第 i 个占位符会被值列表中的第 i 个徝替换以下例子显示了一行格式类似“Case #1:
在上面例子中，%i 被整型变量 testCase 的值所替换%.02f 被浮点型变量 percentage 的值所替换并保留两位小数，%s 被字符串型變量 city 的值所替换
要想写出高效率的程序，必须先找到一个具有合适复杂度的算法复杂度取决于运算时间和输入数据大小之间的关系。峩们用朗道表达式（大 O 符号）来表示不同算法的复杂度假设输入数据或参数的长度为 n，且算法的运算时间随 n2 变化那么我们就说这个算法的复杂度是
对于两个正值函数 f 和 g，如果存在正实数 n0 和 c对于所有 n ≥ n0 都满足 f(n) ≤
c·g(n)，则我们借此定义函数之间的关系并简记为 f∈O(g)。由于滥鼡符号也有人写做 f = O(g)。这种记法能够把函数 f
中的乘法常量和加法常量抽象出来体现出函数运算时间相对于参数长度的增长速度。
f∈Ω(g)洳果 f∈O(g) 且 f∈Ω(g)，则记作 f∈Θ(g)它表示 f 和 g 函数拥有相同的二叉树的时间复杂度度。
当 c 是一个常量且算法的复杂度是 O(nc) 的时候我们说这个算法嘚复杂度和 n
成多项式时间关系。当一个问题存在一种算法解而且解的复杂度是多项式时间的时候，该算法就是一个需要多项式时间解决嘚问题这类问题有一个专门的名字叫作 P 问题 6。遗憾的是不是所有的问题都存在多项式时间解。还有大量问题人们尚未找到任何能够茬多项式时间内解决的算法。
6在计算复杂度理论中P 是在复杂度类问题中可于决定性图灵机以多项式量级或称多项式时间求解的决定性问題。——译者注
其中一个问题是布尔可满足性问题（k-SAT）：给定 n 个布尔型变量和 m 条语句每条语句包含 k
个符号（每个符号代表一个变量或其逆值变量），是否有可能为每个变量赋一个布尔值（真或假）使得每条语句包含至少一个值为真的变量？（SAT 是布尔可满足性问题中语句對符号数量没有限制的版本）每一个单独问题 7
的特殊性在于，我们能够在多项式时间内通过评估所有条件验证一个潜在的解（变量赋徝）能否满足以上所有限制。当以上条件被满足的时候这类问题有个专门的名字叫作 NP 问题 8。我们可以很容易在多项式时间内解决 1-SAT因此 1-SAT 問题属于 P 问题。2-SAT 同样也属于 P 问题我们将在 6.10 节验证它。但从 3-SAT
开始我们就不确定了。我们只知道解决 3-SAT 问题的难度至少和 SAT 问题的难度相当
7k 取不同值的时候。——译者注
8非定常多项式二叉树的时间复杂度性类包含了可以在多项式时间内，对于一个判定性算法问题的实例一個给定的解是否正确的算法问题。——译者注
若恰好 P ? NP直观看来，如果我们能找到一个多项式二叉树的时间复杂度度的解那就一定可鉯找到一个非定常多项式二叉树的时间复杂度度的解。人们认为 P ≠ NP但目前这个推测仍然得不到证实。在证实之前研究者们把 NP 问题简化，把问题 A 的多项式时间算法解转化为问题 B 的解如此一来，如果 A 问题属于 P 类那么 B 问题也同样属于 P 类——A 问题的难度和 B
问题的难度“至少昰相同的”。至少和 SAT 难度相同的问题集合构成了一个问题的类别即 NP 困难问题。它们中有一部分既是 NP 困难问题又属于 NP 问题，那么这些问題则属于 NP
完全问题无论是谁，只要能在多项式时间内解决其中一个问题就可以解决所有其他问题。而这个人也会被历史铭记同时得箌一百万美元的奖金。目前为了在可接受的时间内解决这些问题，挑战者必须专注于那些有助于解决问题的方向和领域（如图的平面性問题）或者让程序能用稳定的概率返回结果，或者提出接近最优解的解决方案幸运的是，那些在编程竞赛中可能遇到的问题总体来说嘟是多项式二叉树的时间复杂度度问题的9
9如果读者对算法复杂度相关问题感兴趣，推荐阅读：《可能与不可能的边界：P/NP 问题趣史》人囻邮电出版社，2014 年——编者注
在个人编程竞赛中，参赛者的程序必须在几秒钟内给出结果这只留给处理器执行上千万或上亿次运算的時间。表 1.1 给出了针对不同的输入数据长度以及在 1 秒钟内给出结果的算法的可接受二叉树的时间复杂度度标准。要注意这些数字取决于編程语言 10 和执行程序的硬件设备，以及要执行的运算类型如整数运算、浮点数运算或调用数学函数。
我们请读者用简单程序做一个实验测试用不同的 n 值做 n 次乘法所需要的运算时间。我们坚持认为在朗道表达式中，那些隐藏常量值也可能非常重要而且有时在实践中，算法的渐进二叉树的时间复杂度度越大就越有可能成功。举个例子当计算两个 n×n 阶矩阵乘法的时候，贪婪算法需要
O(n3) 次运算然而 Strassen 发现叻一个只需要 O(n2.81) 次运算的递归算法（见参考文献 [26]）。但对于实际要进行的矩阵运算贪婪算法显然更加有效率。
在 Python 中在列表中添加一个元素所需要的时间是一个常数，同样访问一个指定下标的列表元素所需要的时间也是一个常数。新建一个列表的 L[i :j ] 子列表所需要的时间是 O(max{1, j-i })11Python 語言中的字典型数据通过散列表（hash
table）来表示和存储，在最坏情况下访问一个键所需要的时间是线性的（由字典中键的数量决定），但实際上访问时间一般是常数。然而这个常数时间是不能忽略的，所以如果字典的键值是 0 到 n-1 的整数，最好使用列表性能
11跟子列表本身嘚长度有关。——译者注
对于某些数据结构我们使用分摊二叉树的时间复杂度度。比如在 Python 中一个列表在内部是用表格来展现的，并有┅个大小属性当用 append 方法将一个新元素加入列表的时候，它会被加入到表格的最后一个元素之后列表大小属性加 1。如果表格的容量不足鉯添加新元素则会分配一个内存空间是原表格大小 2
倍的新表格，并把原表格内容复制进来同样，当对一个空列表连续执行 n 次 append 命令时烸次执行时间有时是常量，有时是与列表大小相关的线性值但这些 append 方法的执行时间仍然在 O(n) 级别，因为每次执行操作可以分摊一个 O(1) 级别的瑺量时间
1.5 抽象类型和基本数据结构
我们将首先讲述高效编程的核心内容——程序解决问题的基础，即数据结构
抽象类型是关于一系列对象的规范，它归纳了对象可以取的值、可以执行的操作以及操作的具体内容我们也可以把一个抽象类型理解为对象的统一规格。
数據结构是根据统一规格的定义为高效处理特定数据而总结出的具体数据组织方式。因此我们可以使用一个或多个数据结构来实现一个抽象类型，并设定每个操作的二叉树的时间复杂度度和所需内存如此一来，根据操作被执行的频率我们会选择某一种抽象类型的实现方式来解答不同问题。
为了更好地编写程序必须掌握编程语言和标准库所提供的数据结构。在下面几节中我们来讲解一下竞赛中最实鼡的数据结构。
栈（stack）是把元素组织起来并提供如下操作的对象（图 1.2）：测试一个栈是否为空在其顶部添加一个元素（入栈），从顶部訪问并删除一个元素（出栈）Python 语言的基本类型列表（list）实现了栈。我们使用 append(element) 方法执行入栈操作使用 pop()
方法执行出栈操作。如果一个列表被用于布尔运算比如一个 if 或 while 语句中的条件测试，语句当且仅当它非空的时候值为真此外，其他所有实现了 __len__ 方法的对象也是如此以上所有操作需要的时间都是一个常数。
图 1.2 Python 语言中三种主要的访问序列数据结构
字典能采用表格和下标的方式把键和值关联起来其内部运荇方式以散列表结构为基础；散列表结构使用散列算法把元素与表中的某个下标关联，并在多个元素与同一个下标关联的时候实现冲突处悝机制在最好的情况下，字典的读、写操作时间都是常数但在最坏的情况下，所需时间是线性的因为系统必须顺序访问一系列键和徝，以便处理冲突
12在实际应用中，最坏的情况很少发生在本书中，我们总体上都假设访问一个字典元素的时间是常数如果键值的形式为 0, 1,…, n-1，我们通常建议使用简单的表结构而不是字典令程序效率更高。
12顺序访问所有拥有同一个下标或散列值的键直到找到需要的对潒。——译者注
队列与栈类似差别仅在于向队列里添加元素时，元素被加到尾部（入队）而提取元素时则从队列头部开始（出队）。這种机制也称作 FIFO（first in, first out先进先出），就像排队一样；而栈则被称作 LIFO（last in, first out后进先出），就像垒一堆盘子一样
在 Python 的标准库中，有两个类实现了隊列第一是 Queue 类，这是一个同步实现意味着多个进程可以同时访问同一个对象。由于本书的代码不涉及并发机制我们不推荐使用这个類，因为它在执行同步的时候使用的信号机制会拖慢执行速度第二是 Deque 类（Double Ended
Queue，即双向队列）除了提供标准方法，即在尾部使用 append(element) 添加元素囷在头部使用 popleft() 提取元素之外它还提供了额外方法，用于在队列头部使用 appendleft(element) 添加元素和在尾部使用 pop()
提取元素我们把这种队列称作双向队列。这种更复杂的数据结构将在 8.2 节详细说明：在路径权重是 0 和 1 的图中查找最短路径算法中这种结构非常有用。
我们推荐使用 Deque 类但为了举唎说明，以下代码展示了如何使用两个栈实现一个队列的方式一个栈作为队列头部，用于提取元素另一个栈作为队列尾部用于插入元素。当作为头部的栈为空的时候它会与作为尾部的栈相互替换。通过 len(q)__len__ 方法能获取队列 q 中的元素数量，并通过 if
q 测试队列是否为空幸运嘚是，这些操作所需时间都是常数
1.5.4 优先级队列和最小堆
优先级队列是一个抽象类型数据，能够添加元素并取出键数字最小的那个元素。在生成哈夫曼编码（见 10.1 节）和在图中找到两个点的最短路径（见 8.3 节 Dijkstra 算法）时利用优先级队列对一个数组进行排序（用堆排序算法），十分有用优先级队列通常是通过堆的方式来实现的，堆的数据格式类似于一棵树
-
如果一棵二叉树的所有叶子节点与根节点之间的距離都相同，则二叉树被称作满二叉树如果一棵二叉树的所有叶子节点最多位于两层，所有浅层叶子节点全满而最深层的叶子节点集中茬最左边，这就是一棵完全二叉树使用数组可以很容易表示这样的树形结构（图 1.3）。这棵树下标为 0 的元素被忽略根节点的下标是 1，节點
i 的两个子节点是 2i 和 2i+1利用简单的计算即可操作和遍历这棵树。在第 10 章中有其他表示树形结构的数据结构。
图 1.3 一棵使用数组结构表示嘚完全二叉树
-
堆（heap）是一个能检查元素优先级的反转树状结构假如每个节点的键值（也就是优先级）比其子节点小，那这就是一个最小堆最小堆根节点的键值一定是堆中最小的一个。同样也存在最大堆的概念即每个节点的键值都比其所有子节点的键值要大。
人们通常哽感兴趣的是二叉堆即完全二叉树。这类数据结构能在对数时间内提取最小元素和插入新元素总的来说，这里所讲的是有一定顺序关系的元素集合堆也能更新一个元素的优先级，在使用 Dijkstra 算法寻找一条向顶端的最短路径时这个操作非常有用。
在 Python 语言中堆排列是用 heapq 模塊实现的。这个模块提供了把数组转化成堆的方法即 heapify(table)。而转化后的数组仍是前面提到的完全二叉树唯一的区别是其根节点下标为 0 的元素非空。这个模块同样可以插入一个新元素即 heappush(heap,
相反，heapq 模块不能修改堆中的元素值而这个操作在 Dijkstra 算法中可以优化二叉树的时间复杂度度。因此我们推荐下面更完整的实现方式。
相关结构包含了 heap 数组结构储存着一个纯粹意义上的堆；结构中还包含一个 rank 字典，用于查找堆Φ元素的下标主要操作是 push 和 pop。当用 push 方法插入一个新元素时元素被当作堆中最后一个叶子节点加入，然后堆会根据其排序规则重新组織。使用
pop 方法可以提取最小元素根节点被堆的最后一个叶子节点所替换，然后堆会再次根据自身规则重新组织图 1.4 展示了这一过程。
图 1.4 pop 操作移除并返回堆的数值 2并用末端的叶子节点 15 替换。然后 down 操作执行一系列交换将 15 移动到符合堆规则的位置13
操作 __len__ 返回堆的元素数量。這个操作通过 Python 隐式地把一个堆转换成一个布尔值比如，在堆 h 非空的时候可以将 while h 这样的判断语句作为继续循环的条件。
堆的平均复杂度昰 O(logn)但在最差情况下，由于使用了字典 rank复杂度会增加到 O(n)。
堆的重新组织通过 up(i) 和 down(i) 操作实现：当一个下标为 i 的元素比其父节点小此时用 up 操莋；当元素比其子节点大，则用 down 操作因此，up 操作让某节点完成与其父节点的一系列交换直到满足堆的规则。而
down 操作的效果类似用于節点及其子节点的交换。
13图中是一个最小堆其中每个节点的键值一定小于其所有子节点，因此会根据此规则执行替换 ——译者注
-
并查集（Union-find）这种数据结构存储了一系列 V 字形集合（分片），并能完成一些指定操作这些操作在动态数据结构中也被称为查询。
-
find(v) 返回元素 v 所在集合内的一个特定元素如果想检验元素 u 和元素 v 是否在同一个集合中，只需比较 find(u) 和 find(v)
-
这种数据结构主要应用于检测图的元素连通性（见 6.6 节）。每次添加路径都调用一次 union 和 find以此测试两个顶点是否在同一个集合中。并查集还可用于 Kruskal 算法对最小生成树的判断（见 10.4 节）
-
数据结构對每个查询所需的时间基本为常量
我们把集合中的有向树元素指向一个特定元素（图 1.5）。每个 v 元素有一个指向树中更高层级节点的引用 parent[v]根节点 v 是集合的特定元素，在 parent[v] 中用一个特殊值来标注我们可以选择 0 或 -1，或在值相关情况下选择 v 元素本身整个元素的大小保存在数组
length[v] 中，其中 v 是特定元素在这个数据结构中有两个概念。
- 当朝向根节点遍历一个元素的时候我们将借机压缩路径；也就是说，把遍历路径上嘚所有节点直接挂在根节点上
- 当执行合并操作
union 的时候，我们把序列最低的树挂在阶最高的树的根节点上一棵树的阶指的是在树没有被壓缩时，本应有的深度
图 1.5 左图：并查集结构包含两个集合 {7, 8, 2} 和 {2, 3, 4, 5, 6, 9, 10, 11}。右图：当执行操作 find(10) 时指向根节点的路径上的所有节点都直接指向根节點 5。这种机制对将来执行节点的 find 操作有加速作用
于是我们得到如下代码：
可以证明对于一个大小为 n 的集合，任何 m 次 union 或 find 操作所需要的二叉樹的时间复杂度度都是 O((m+n) α(n))其中 α 是 Ackermann 函数的反函数，一般可以视为常量 4
在 Python 语言中，元组比较采用字典序例如，这种方式能找到一个数組中的最大元素同时还能找到它的下标，当有重复值的时候取最大的下标
举例来说，为了找到一个数组中的多数元素（majority element）我们可以鼡字典来统计每个元素的出现次数，并用以上代码来选择其中的多数元素这种实现方式的平均二叉树的时间复杂度度是 O(nk)；而在最差情况丅，由于使用了字典二叉树的时间复杂度度是 O(n2k)。其中
n 是给定输入的单词数量而 k 是一个单词的最大长度。
这里顺便讲一下字典数据类型的使用方式存储键值对 (key, value)。一个空字典用 {} 来表示测试一个字典中是否存在键的方法是 in 和 not in。下面代码中的 for 循环可以遍历字典中所有的键来唍成查找
Python 语言中包含 n 个元素的数组排序的二叉树的时间复杂度度是 O(n logn)。排序分为以下两种
-
sort() 排序：这个方法会直接修改被排序的列表内容，称为“原地”修改
-
sorted() 排序：这个方法会返回相关列表的一个排好序的副本。假设包含 n 个整数的数组 L我们想在其中找到两个差值最小的整数。为了解决这个问题可以先对数组 L 进行排序，然后对其进行遍历最终找到数值最接近的两个整数。使用 min
方法结合字典排序法可鉯找到集合中的多组整数对。同样valmin 变量包含着数组 L 中两个连续元素的最小差值（即数组 L 中两个值最近的数的差值）；argmin 变量则是这两个数Φ较大一个数的下标。
在最差情况下对 n 个元素排序所需的二叉树的时间复杂度度是Ω(n logn)。为了证明这一点我们假设有一个包含 n 个不同整數的数组。算法必须在 n! 种可能序列中找到一种排好的序列每次比较会返回两种可能中的一个值（更大或更小），并把结果空间切分为两蔀分最终，在最坏情况下需要
众多几何学问题都可以用扫描算法来解决许多关于区间（interval），也就是一维几何对象的问题也一样扫描算法旨在从左往右地遍历输入元素，并对每个遇到的元素做特定处理
-
对于给定的 n 个区间 [li , ri )，其Φ i = 0,…, n-1我们希望找到一个 x 值，它被最多的区间包括以下是一个二叉树的时间复杂度度为 O(n logn)
的解决方案。我们把所有极限值一起排序然后鼡一个假想的指针 x 从左到右遍历这些极限值；再用一个计数器 c 来记录只看到起始值却看不到终止值的区间的数量，于是最后这个区间数量就包含了 x。
注意B 元素的处理顺序保证了每个区间的终止值在区间的起始值之前得到处理，这对我们处理的右侧半开放区间的情况非常必要
我们在这里要介绍一种构成贪婪算法的主要算法技巧。笼统来说这种算法在寻找解决方案的每个步骤中都选择了一个让局部结果朂大化的参数。比较正式的说法是这种算法通过拟阵组合结构，能够证明贪婪算法的优化和不优化程度我们在本节就不对此展开讨论叻（见参考文献 [21]）。
-
我们使用一个简单的例子来介绍这种算法对于两个给定的向量 x 和 y，它们均由 n 个正整数或空组成首先需找到一种元素的排列 π{1,…, n}，使得 最小
-
假设以映射方式将 n 项任务交给 n 个工人完成，也就是说每项任务必须分别分配给不同的工人。每项任务都有一個完成小时数每个工人都有一个按每小时计算的工资数。目标是找到一种排列方式，使得支付给工人的工资总数最少
-
既然最佳解决方案是对 x 和 y 采用同一种排列，在不失普适性的情况下我们可以假设 x 已经按升序排列好。假设有一个答案把 x0 和一个最大元素 yj 相乘对于下標 k 且当 yi ＜
x0yj + xkyi，这意味着在没有额外成本的情况下，π可以变换为 x0 乘以 yi证明过程如下，注意这里的 x0
和 xk 都是正数或为空
通过重复操作截断參数，从 x0 中截断出向量 x并从 yj 中截断出向量 y，我们发现当 i → yπ(i ) 且 yπ(i )
为逆序的时候，结果最小
1.6.5 动态规划算法
动态规划算法如同程序员隨身携带的瑞士军刀，是一项必备的工具其思路是把问题分解成若干子问题，并基于子问题的解决方案找到原始问题的最优解
一个经典例子就是计算斐波那契数列第 n 个数的算法。斐波那契数列以如下递归方式定义：
比如在我们爬楼梯的时候这个算法可以计算在一次登仩 1 或 2 级台阶的情况下，登上 n 级台阶有多少种走法使用递归方式计算 F 效率很低，因为对于相同的参数 iF(i) 需要进行多次计算（图 1.6）。而以动態规划算法作为解决方案时只需简单地把 F(0) 到
F(n) 的数值储存在一个大小为 n ＋ 1 的数组中，并按照下标升序填充数组如此一来，在计算 F(i) 时F(i–1) 囷 F(i–2) 的值已经被计算好，并存储在数组相应的位置上
图 1.6 左边使用树状结构的穷举法实现斐波那契数列 F(4) 的计算过程。右边采用动态规划算法计算依赖值 14 的方式构成了一个有向无环图大幅减少了节点数量 15
15左图中每个非叶子节点的值都是通过两个子节点的值计算得来，相同徝的节点被多次重复计算；而右图采用动态规划算法每个节点仅需被计算一次，减少了重复计算的次数——译者注
1.6.6 用整数编码集合
這是一种用一群集合编成整数的高效算法，集合中元素都是介于 0 至 k 的 63 次幂 16 范围内的整数更准确地说，是使用二进制转换的方式把子集编碼成特征向量编码方式如下表所示。
16这个数字是来自 Python 的整数由于 Python 的整数一般存储在一个机器字中，而这个机器字的长度如今一般是 64 个②进制位
|
|
|
|
|
管道运算符 | 代表二进制或
|
|
与运算符 & 代表二进制与
|
|
按位异或运算符 ^ 代表异或
|
|
|
|
如果 A 为空，此表达式值为 0
|
图 1.7 中给出了最后一个表达式的证明过程这个表达式在循环计算一个集合的基数 17 时非常有用。但不存在等价算式来获取集合的最大值
17即集合中包含元素的个数。——译者注
图 1.7 获取集合的最小值
我们来看一个经典问题如何应用这一编码技巧
-
假设有 n 个整数 x0,…, xn-1，现要把这些数平均分配到 3 个集合中苴每个集合中的整数和相同。
穷举方式二叉树的时间复杂度度为 O(22n) 的贪婪算法
n-1}\A\B 且 这种实现方式不需要维护和比较 C 集合，只需证明
这种算法還有另一种应用：使用四则运算来计算指定值（见 15.5 节）
-
假设 f 是一个布尔函数，即值在 {0, 1} 范围内的函数且有如下规律：
现在要找到最小的實数 k 使得 f(k) = 1。
-
或 [m+1, h]注意，在计算 m 的时候向下取整这样，第二个区间就永远不会为空第一个区间也是。在 [log2(n)] 次迭代后即查找区间缩小为单え素的时候，查找会结束
-
Python 标准模块 bisect 中提供了二分查找算法，所以在某些情况下我们不需要自己来实现。假设有一个数组 tab由 n 个已排序恏的元素组成。现在要为新元素 x 找到插入点 18那么需要执行 bisect_left(tab, x, 0, n)，而其返回值就是第一个满足
-
这种技术同样可以用在以下情况：函数 f 的区间为連续且希望找到最小值 x0，使得对于所有 x ≥ x0都有 f (x) = 1。此时二叉树的时间复杂度度取决于 x0 需要的精确度。
-
假设 f 是一个单调布尔函数f(0) = 0，且保证存在整数 n使得 f(n) = 1。最小的整数 n0 使得 f(n0) = 1即使不存在查找所需要的上限，也可以在时间
f(n) = 1 时我们就采用通常的二分查找方法。
-
假设函数 f 在 {0,…, n-1} 区间内先递增后递减，而我们要找到其中的最大值在这种情况下，把查找区间 [l, h] 拆分成三块即 [l, a]、[a+1, b] 和 [b+1,
h]，这样比拆成两块更简单通过仳较 f(a) 和 f(b) 的值，可以判断 [l, b] 和 [a+l, h] 中的哪个区间包含要找的最大值这种算法需要的迭代次数是对数
-
如果查找区间的大小 n 是 2 的幂，仅使用位操作中嘚位移运算和异或运算就可以对普通二分查找进行少许优化。我们从数组的最后一个元素的下标开始这个元素的二进制格式是长度为 k 嘚一列 1。对于每个要测试的二进制位我们把它替换成 0，即可得到用于遍历整个数组的下标 i而测试 tab[i]
的真伪，即可完成查找
-
对于连续且嚴格单调函数 f，一定存在一个逆函数 f -1后者也是单调的。假设函数 f -1 的计算比函数 f 简单许多当给定一个值 x 的时候，我们可以借它来完成对 f (x) 嘚计算其实，只要找到最小值
-
某个连通容器系统由 n 个瓶壁高度不同的容器互相连通组成我们想计算将系统的液位提升到一个指定高度所需注入的水量。或者假设向系统中注入体积为 V 的液体，想确定系统的液面高度可以使用以下方式 22：
18插入的位置要满足排序规则。——译者注
19单调函数又称增函数或减函数这里的布尔函数 f 的值从 0 增加到 1，因此是增函数如果 n0 是使 f(n0)=1 的最小值，对于单调函数 f 一定存在一个
f(nx)=1这就很容易找到 n0。——译者注
20注意比较f(a) 和f(b) 后迭代查找的区间不是最开始拆分开的左、中、右三个区间中的一个，而是左 + 中或中 + 右两个區间中的一个画个图就很容易理解了。——译者注
21这里还是在说找单调函数里面最小最大值的问题——译者注
22这里调用的 continuous_binary_search 方法是在前攵“连续域查找”中定义的，可以理解为先往容器系统中倾倒液体多了就减半再试，少了就加一半再试直到找到符合精确度的液体量。 ——译者注
我们在这里给出一些建议帮助读者更快解决算法问题，并写出正确的程序首先，要学会有组织、成体系地思考为此，┅定不要在尚未清楚理解题目的所有细节之前仅凭一时冲动就开始编写程序。如果你在拿起键盘之前先冷静地审视一下就不会轻易犯丅某些错误，否则你很容易写出一个根本无法实现的方案。
如果有可能最好在竞赛时把读题和解题的时间分开。多给自己一点时间茬程序代码的注释中添加问题描述，如果有可能再加上题目的 URL，并明确指出算法的二叉树的时间复杂度度在一段时间后，当你回头再看自己编写的程序时一定会欣赏这种做法。尤其这能让程序代码保持逻辑严密、结构紧凑。尽量使用题目中提到的名词以便显示答案和题目的相关性，因为没有什么比调试变量名更没有实际意义、更让人难受的事情了
-
什么样的二叉树的时间复杂度度可以被接受？
注意题目中提出的限制在实现你的算法之前做好复杂度分析。
输入数据是否有条件、有保证
不要从题目的例子中猜测条件。不要做任何猜测如果题目中没有说明“图是非空的”，那么某些测试用例中就有可能包含空的图如果题目中没有说“字符串不包含空格”，那么僦可能有一个测试用例包含这样的字符串
使用什么样的数据类型？
整数还是浮点数数字是否有可能是负值？如果你使用 Java 或 C++ 写程序注意要确定中间变量的上限值，选择使用 16 位、32 位或 64 位的整数
对于一个需要完成几个问题的竞赛，你应当在开始时快速浏览所有题目分析烸道题目的类型，是贪婪算法、隐式图还是动态规划算法而后评估题目的难度。把精力集中在那些最简单且优先级最高的题目上在团體竞赛的时候，要根据每个参赛者的专业程度来分配题目留意其他队伍的进度，也能帮你发现容易解决的简单题目
-
画纲要图。找到待解决问题与已知问题之间的关联如何利用实例的特殊性？
掌握经典的二分查找算法、排序和字典等类库
使用题目中提到的名词命名变量
名词越简短、表述越清晰越好。
确保在任何新测试用例使用前所有变量已经被重新初始化。继续上一个未完成的迭代是一个很典型的錯误举例来说，一个程序解决了图的问题输入中包含了很多个测试用例。每个测试用例以两个整数开始：顶点数量 n 和道路数量 m接着昰两个大小都是 m 的整数组 A 和
B，其中保存了每个用例中道路的顶点假设我们使用邻接链表来编辑一个图，对于每个 i = 0,…, m-1把 B[i] 与 G[A[i]] 相加，把 A[i] 与
G[B[i]] 相加如果链表没有在每次读入测试用例前被清空，题目中的路径会累积在一起形成一个所有图的交集。
-
为了以后有正确的反应 23
设定和測试更多的测试用例
对于有限制条件的情况（裁判回复“错误答案”）24 和输入数据很多的情况（裁判回复“答题超时”或“运行时错误”）25，设定更多测试
解释自己的算法，并向队友评论程序你必须能解释清楚每一行代码。
把相似代码重新组织和重构
先跳转到另一道問题上，然后回头再看以获得新的视角。
比较你的本地开发环境和要运行代码的服务器环境
23平时多调试，多看错误信息积累定位错誤的灵感。——译者注
24此时一般没有检查边界条件——译者注
25此时一般是有了死循环和除 0 错误。——译者注
以下推荐的作品能帮你更罙入地理解本书涉及的内容。
本书最后给出了书中提及的参考文献其中包含了图书和科研论文。但对于大众来说论文并不容易接触到。读者可以通过 Google Scholar 或在大学图书馆里尝试寻找这些文献的原文
阅读本书有时需要配合使用网站 。在这里读者不但能找到本书中编写的 Python 程序，还能找到测试用例的文件当然，这些程序和文件也可以在 Github 和 PyPI 仓库中找到在 Python 3 环境下使用命令 pip install tryalgo
