python算法实例精讲（程序员用Python解算法谜题2）
python算法实例精讲（程序员用Python解算法谜题2）下面是算法的代码：[i j)内在场的名人，会在i i 1 … j − 1点内在场。算法简单计算每个小时内名人的数量，并选出最大值。参加派对的最佳时间是几点？或者说，你应在哪个时间参加派对？通过查看每个小时并计算名人的数量，你可能发现如果在10点到11点之间参加，将得到与Brad、Katy和Drake的自拍。没有比得到3张自拍更好的了。这段简单的算法查看每一小时，检查每一小时内有几位名人在场。一位在区间
谜题2 参加派对的最佳时间本谜题涵盖的程序结构和算法范型：元组、元组列表、嵌套for循环和浮点数、列表切片、排序。
你在办公室抽奖中赢得了一张奖票，去参加一场名人庆祝派对。由于门票的需求量很高，你只能待一个小时，但是由于拥有一张特等票，因此你可以选择在哪个小时出席。你有一张时间表，上面准确地列有每位名人出席派对的时间，你希望与尽可能多的名人合影来提高你的社会地位。这意味着你需要在特定的某个时段出席派对，这样你可以和最多的名人交谈，并获得与他们每个人的自拍。
我们得到一组区间的列表，对应于每位名人出席、离开的时间。假设区间是[i j]，其中i和j对应小时，区间为左闭右开区间。这意味着名人会在i点出席派对，但在j点开始时离开。因此即使你第j点准点到达，也会错过这位名人。
表2-1给出的是一个例子。
参加派对的最佳时间是几点？或者说，你应在哪个时间参加派对？
通过查看每个小时并计算名人的数量，你可能发现如果在10点到11点之间参加，将得到与Brad、Katy和Drake的自拍。没有比得到3张自拍更好的了。
2.1 反复检查时间这段简单的算法查看每一小时，检查每一小时内有几位名人在场。一位在区间
[i j)内在场的名人，会在i i 1 … j − 1点内在场。算法简单计算每个小时内名人的数量，并选出最大值。
下面是算法的代码：
1. sched = [(6 8) (6 12) (6 7) (7 8) (7 10) (8 9) (8 10) (9 12) (9 10) (10 11) (10 12) (11 12)] 2. def bestTimeToParty(schedule): 3. start = schedule[0][0] 4. end = schedule[0][1] 5. for c in schedule: 6. start = min(c[0] start) 7. end = max(c[1] end) 8. count = celebrityDensity(schedule start end) 9. maxcount = 0 10． for i in range(start end 1): 11． if count[i] > maxcount: 12． maxcount = count[i] 13． time = i 14． print ('Best time to attend the party is at' time 'o\'clock' ':' maxcount 'celebrities will be attending!')
算法的输入是一个时间表，也就是一组区间的列表。每段区间是一个二元组，其中的两个元素都是数字。第一个元素是开始时间，第二个元素是结束时间。该算法不能修改这些区间，因此用元组来表示。
第3～7行代码确定名人出席派对的最早时间与最晚时间。代码第3行和第4行假定schedule中至少有一个元组，用该元组初始化变量start和end。我们希望变量start表示每位名人最早开始时间，变量end表示每位名人的最晚结束时间。schedule[0]给出schedule的第一个元组。访问这个元组的两个元素的方式和访问列表中的元素完全相同。由于schedule[0]为元组，我们需要另外一个[0]用于访问元组的第一个元素（第3行代码），[1]用于访问元组的第二个元素（第4行代码）。
在for循环中会遍历列表中的所有元组，将其中的每个元组命名为c。注意，如果我们将c[0]修改为10（例如），程序会抛出错误，因为c是元组。另一方面，如果声明sched = [[6 8] [6 12] ...]，我们便可以将6改为10（例如），因为sched中的每个元素都是列表。
第8行代码调用一个函数，填充列表count，用于表示start和end时间范围内每一小时内在场的名人数量。
第9～13行代码用于找出最大的名人数量出席的时段，循环start到end时间范围内的各个小时，通过变量maxcount跟踪最大的名人数量。这些代码可以替换为：
9a. maxcount = max(count[start:end 1]) 10a. time = count.index(maxcount)
Python提供了一个函数max可用于查找列表中的最大元素。此外，我们可以使用切片（slice）来选取列表中一段特定连续范围内的元素。在第9a行中，我们找到索引start和end之间（包含end）的最大元素。如果有b = a[0:3]，意思是将a的前3个元素（即a[0]、a[1]、a[2]）复制到列表b中，其长度为3。第10a行确定最大元素的索引。
下面是算法的核心内容，实现在函数celebrityDensity中：
1． def celebrityDensity(sched start end): 2． count = [0] * (end 1) 3． for i in range(start end 1): 4． count[i] = 0 5． for c in sched: 6． if c[0] <= i and c[1] > i: 7． count[i] = 1 8． return count
这一函数包含一个嵌套循环。外层循环从range的第一个参数start指定的时间开始，遍历不同的时间，每次迭代后将时间i递增1。内层循环（第5～7行）遍历所有的名人，第6行代码检查当前名人当前时间是否在场。如前所述，时间必须要大于等于名人的开始时间且小于结束时间。
如果运行语句
bestTimeToParty(sched)
代码将打印
Best time to attend the party is at 9 o'clock : 5 celebrities will be attending!
这一算法看起来似乎很合理，但是有一点不能令人满意。时间单位是什么？在我们的例子中，可以假设6代表下午6点，11代表下午11点，12代表上午12点，这意味着时间的单位是1小时。但是如果名人像他们习惯的那样，在任意时间来去将会怎么样呢？例如，假设Beyoncé在6:31到场并在6:42离开，Taylor在6:55到场并在7:14离开。我们可以将时间单位设为1分钟而非1小时。这意味着在第6行循环中要执行60次检查。如果碧昂丝（Beyoncé）选择在6:31:15到场，我们就该要检查每一秒。名人到达和离开的时间单位也可能在毫秒级（好吧，即使是Beyoncé，这也很难做到）！时间单位不得不做出选择，很烦人。
你能想出一个不需要依赖时间精度的算法吗？这一算法应该利用大量只与名人的数量相关而与他们的日程安排无关的操作。
2.2 聪明地检查时间我们绘图表示所有名人的区间，以时间为横轴。图2-1是一种可能的名人日程表。
图2-1
这张图片耐人回味—— 它告诉我们，如果在特定时间拿一把“标尺”（如图2-1中的虚线所示），就可以计量与标尺相交的名人时间区间个数，从而得知这时可以见面的名人数量。在前面的简单算法中，我们早已得知名人数量，也编写了相关代码。但是可以从图中额外观察到以下两点。
（1）我们只需要关心名人时间区间的起点和终点，因为只有这些时刻在场名人数量才会发生变化。没有必要计算第二条虚线时间在场的名人数量——它和第一条虚线完全相同，因为在第一条和第二条虚线或时间范围内，没有新的名人到达或者离开（回忆一下，第4位名人——从上往下数第4条线——在第一条虚线对应的时间便已到达派对现场了）。
（2）我们可以将标尺从左侧向右侧移动，通过增量计算找出名人数量最多的时间，这一点将在下面详述。
我们保存名人的计数，初始为零。每当看到名人时间区间的开始时间，便递增这个计数，每当看到名人时间区间的结束时间，便递减这个计数。我们同时也跟踪最大的名人数量。名人数量在名人时间区间的开始和结束时发生变化，而最大的名人数仅在名人时间区间的开始时间发生变化。
这里有一个关键点，我们必须随着时间的增加来执行这一计算，从而模拟标尺从左往右移动。这意味着必须对名人日程表的开始时间和结束时间进行排序。我们在上面的图片中，想首先看出第二位名人的开始时间，然后是第三位名人的开始时间，再是第一位名人的开始时间，依此类推。我们稍后会操心怎样对这些时间进行排序，但现在先来看看如下代码，这段代码会以更高效和优雅的方式来发现参加派对的最佳时间。
1． sched2 = [(6.0 8.0) (6.5 12.0) (6.5 7.0) (7.0 8.0) (7.5 10.0) (8.0 9.0) (8.0 10.0) (9.0 12.0) (9.5 10.0) (10.0 11.0) (10.0 12.0) (11.0 12.0)] 2． def bestTimeToPartySmart(schedule): 3． times = [] 4． for c in schedule: 5． times.append((c[0] 'start')) 6． times.append((c[1] 'end')) 7． sortList(times) 8． maxcount time = chooseTime(times) 9． print ('Best time to attend the party is at' time 'o\'clock' ':' maxcount 'celebrities will be attending!')
注意，schedule和sched2是二元组的列表，如前所述，每个元组的第一个元素是开始时间，第二个元素是结束时间。但是在sched2中用浮点数而非在schedule中用整数来表示时间。6.0、8.0等数字都是浮点数。在这道谜题中，我们仅比较这些数字，没有必要对它们执行其他算术操作。
另一方面，在第3行被初始化为空的列表times是二元组的列表，每个元组的第一个元素是时间，第二个元素是用来指示时间是开始时间还是结束时间的字符串标记。
第3～6行代码收集所有名人的开始时间和结束时间，每次都做这样的标记。列表未经排序，因为我们不能假定参数schedule曾按任何方式排过序。
第7行代码通过调用一个排序过程对列表进行排序，稍后我们会介绍这个排序过程。一旦列表经过排序，第8行代码会调用关键的过程chooseTime，用以执行增量计算来确定各个时间段内名人的数量（密度）。
这段代码将会按与打印原始时间表sched相同的方式，打印出sched2：
Best time to attend the party is at 9.5 o'clock : 5 celebrities will be attending!
按时间进行排序怎么样？我们有一组区间列表，需要将其转换为按'start'和'end'进行标记的时间列表。接着按时间升序进行排序，并保留这些与时间关联的标签。下面是执行相关操作的代码：
1． def sortList(tlist): 2． for ind in range(len(tlist) - 1): 3． iSm = ind 4． for i in range(ind len(tlist)): 5． if tlist[iSm][0] > tlist[i][0]: 6． iSm = i 7． tlist[ind] tlist[iSm] = tlist[iSm] tlist[ind]
这段代码是如何工作的？它对应于可能是最简单的排序算法——选择排序[1]。该算法找到最小的时间，并在外层for循环的第一次迭代之后（第2～7行），将其放在列表的起始位置。对最小值的搜索需要len(tlist) - 1次计算而非len(tlist)次计算，因为我们在仅剩一个元素时不需要仍找寻最小值。
寻找最小元素需要遍历列表的所有元素，执行于内层for循环（第4～6行）。因为列表起始位置已经有元素存在，该元素需要保留在列表中的其他某位置，所以算法在第7行代码将两个元素交换。可将第7行代码理解为并行发生的两次赋值：tlist[ind]获取tlist[iSm]的旧值，tlist[iSm]获取tlist[ind]的旧值。
在外层for循环的第二轮迭代中，算法查看列表中的其余条目（不包含第一个条目），找出最小值，通过在迭代中将最小值与当前第二位的元素交换，将最小值作为第一个条目后的第二个条目放置。注意，第4行代码range有两个参数，确保在外层循环的每次迭代中，内层循环都以ind开始，这样可以确保索引小于ind的元素都保持在正确的位置。这一过程持续到列表中所有的元素完成排序为止。因为参数列表中每个元素都是一个二元组，我们必须在第5行的比较中使用二元组第一项的时间值，这便是我们在第5行中使用额外的[0]的原因。当然，我们是在对二元组进行排序，第7行代码交换的是二元组，'start'和'end'标签依然附着在原来的时间上。
一旦列表完成排序，过程chooseTime（如下所示）会通过单次遍历列表确定最佳时间和该时间的名人数量。
1. def chooseTime(times): 2. rcount = 0 3. maxcount = time = 0 4. for t in times: 5. if t[1] == 'start': 6. rcount = rcount 1 7. elif t[1] == 'end': 8. rcount = rcount - 1 9. if rcount > maxcount: 10． maxcount = rcount 11． time = t[0] 12． return maxcount time
迭代次数是名人数量的两倍，因为列表times中有两个条目（每个都是二元组），分别对应每位名人的开始时间和结束时间。将该算法和前面双层嵌套循环的简单算法进行比较，简单的算法的迭代次数等于名人的数量乘以小时数（或者根据具体情况为分钟数或秒数）。
注意，参加派对的最佳时间往往和某些名人到达派对的开始时间相对应，这是由于rcount仅在这些开始时间递增，因而在这些时间之一达到峰值。我们将在习题2中利用这一观察结果。
2.3 有序的表示为更有效地处理列表而对其进行排序，是一种基本的技巧。假设我们有两个单词列表，想要检查它们是否相等。假设每个列表都没有重复的单词，并且他们的长度相同，都有n个单词。明显的方法是获取列表1中的每个单词，检查是否存在于列表2中。最坏的情况下需要n2次比较，因为每个单词在检查成功或者失败之前都需要比较n次。
更好的方法是按照字母顺序将两个列表中的单词排序。一旦它们经过排序，我们便可以简单地检查有序列表1中的第一个单词是否等于有序列表2中的第一个单词，有序列表1中的第二个单词是否等于有序列表2中的第二个单词，依次类推。这种方式只需要比较n次。
等等，你说，排序所需的操作次数是多少呢？选择排序过程在最坏的情况下不是需要n2次比较吗？这里正在对两个列表做排序。请关注更好的排序算法，我们将在本书后面介绍在最坏情况下只需要n log n次比较的排序算法。对于较大的n值，n log n会比n2小得多，这使在比较相等性之前进行排序是非常值得的。
2.4 习题习题1 假设你是一位非常忙碌的名人，并不能自由选择参加派对的时间。对过程增加参数并修改，使它能够在给定的时间范围ystart和yend内，确定能见到最多多少位名人。与名人一样，你的时间区间为 [ystart yend)，表示你会在任意满足ystart≤t＜yend 的时间t时在场。
习题2 有另一种方法，可以不依赖时间精度来计算参加派对的最佳时间。我们依次选择每位名人的时间区间，并确定有多少其他名人的时间区间包含所选名人的开始时间。我们选择出某位名人，使他的开始时间被最大数量的其他名人时间区间所包含，并将他的开始时间作为参加派对的时间。编写代码实现该算法，并验证它的结果与基于排序算法的结果是否相同。
难题3 假设每位名人都有一个权重，取决于你对这位名人的喜爱程度。可以在时间表中将其表示为一个三元组，如(6.0 8.0 3)。开始时间是6.0，结束时间是8.0，权重是3。修改代码，找出最大化名人总权重的时间。例如，给定图2-2，我们想要返回与右侧虚线对应的时间，即使当时只有两位名人。
图2-2
因为这两位名人对应的权重为4，大于第一条虚线时在场的3位名人对应的权重3。
下面是一个更复杂的例子：
sched3 = [(6.0 8.0 2) (6.5 12.0 1) (6.5 7.0 2) (7.0 8.0 2) (7.5 10.0 3) (8.0 9.0 2) (8.0 10.0 1) (9.0 12.0 2) (9.5 10.0 4) (10.0 11.0 2) (10.0 12.0 3) (11.0 12.0 7)]
根据名人的日程安排，你想要在11点参加派对，此时参加派对名人权重之和是13，为最大值。
[1] 不一定是最高效的算法，但最容易编写与理解。在谜题11与谜题13中，我们将会见到更好的排序算法。
消息交流
