已知数组x[]储存了一组整数, 请写一个程序, 找出在数组中连续元素的和中最大的一个。举例而言, 如果有数组[1, 2, -6, 3, -2, 4, -1, 3, 2, -4], 那么连续的元素的和有1 + 2 = 3, 1 + 2 + (-6) = 3, 2 + (-6) = 4, …, 但值最大的就是3 + (-2) + 4 +(-1) + 3 + 2这一段, 值为9. 规定: 和为负值时就定成0, 所以结果永远不为负。这个题目通常叫做最大连续元素和(Maximum Consecutive Sum)问题

说明: 这个问题有个很简单的解法,但效率很低,一般采用效率很高的方法的程序比使用不好的方法的要长。一般人看到这个问题的自然反应就是用两个循环, 如程序所示。

1
2
3
4
5
6
7
8
9

def bad_method(x):
    max_sum = 0
    for i in range(len(x)):
        s = 0
        for j in range(i, 0, -1):
            s += x[j]
            if s > max_sum:
                max_sum = s
    return max_sum

想法是很简单的, 当固定在某个x[i]之后, 把x[i], x[i-1] + x[i], x[i-2] + x[i-1] + x[i], … x[0] + x[1] + … x[i]求出来, 一边算, 一边找出极大值, 这就是上面片段所隐含的意义。但是, 当处理到i时要查i个元素, 所以要把n个数都处理完,就要查1 + 2 + 3 + … + i + … + n = n(n+1)2、与n ** 2成正比的元素了。如果仔细看就会发现做了很多重复的工作, 为什么? 当i是2时,算了x[2], x[1] + x[2], x[0] + x[1] + x[2], 但当i进到下一个位置变成3时, 又算x[3], x[2] + x[3], x[1] + x[2] + x[3], x[O] + x[1] + x[2] + x[3], 于是x[1] + x[2] 与 x[O] + x[1] + x[2]不都是重复算了吗? 因此, 程序如果能够避免这些重复的部分, 就一定会非常快。

解答见maximum_consecutive_sum.py

假设有一个数组, 它有n个元素,每一个不外乎是红、白、蓝3种颜色之一的代号, 就说是R, W, B好了。这些元素在数组中并没有依同样颜色的元素排在一起的方式来排列, 请写一个程序把这些元素排成所有蓝色在前, 然后是白色, 最后是红色的排列方式, 不过在写程序时要满足下面的条件

1. 不能用到额外的内存,换句话说,只能在数组之内用互换的方式完成。
2. 互换两个元素的动作要越少越好
3. 对于每一个元素而言,测试它是红, 白, 还是蓝的工作, 每种颜色最多只能做一次测试

在这个限制之下,请编写一个最快的程序

说明: 有些人很自然地会想到把蓝色当成1、白色当成2、红色当成3, 然后用排大小的程序把次序排出来,自然地蓝色在前, 白色居中, 红色最后了; 完全正确, 不过却违背了规定。也就是说, 互换两个元素的动作是不是太多了呢? 对每一个元素测试它的颜色的行为是否违反了要求呢? 对前者而言,不同的排序方法会有不同数目的互换动作。比如说,如果用选择法, 每次找到计i+1 ~ n中最小的值, 与第i个元素互换, 那么排序的动作只不过用了n-1次互换。但是对第三个限制而言, 就很难保证对每一个元素、每一种颜色都最多只测试次了

第三个条件需要仔细地说明, x[i]表示第i个元素。第三个条件是说, x[i] == R, x[i] == W, x[i] == B 这3个比较的任何一个都最多只能做一次。举个例子, 如果在决定观应该放在什么地方时,上述3个比较都各做一次,是正确的。任取两个或任取一个各做一次,也是正确的。但x[i] == R、x[i] == W、x[i] == R就是错的了, 因为对R的测试做了两次。

其实这个题目并不难, 把数组从头到尾查一次就可以做出结果, 那3个繁琐的条件, 不过是防止去用排序或“不够快”的方法来解题而已。

解答见three_flag.py

请写一个程序, 输入一个正整数的值, 然后列出所有由n个左括号与n个右括号正确成的字符串; 当然, 正确的左, 右括号一定个数一样多, 所以输入的值要是个偶数

说明: 所谓由括号正确地组成的字符串, 指的是如果有一个左括号, 那么在它的右边就一定有一个与它相匹配的右括号。例如,()()、(()),就是仅有的两个有4个符号的, 由括号正确地组成的字符串:()()()、()(())、(())()、(()())、((()))则是5个有6个符号, 由括号正确地组成的字符串。正因为有一个左(或右)括号就一定有相对应的右(或左)括号, 左、右括号成双出现, 因此输入就一定要是偶数, 奇数是不可能的。当输入n之后, 在字符串中左、右括号的个数就各是n/2个。

如何产生这样的字符串呢？下面就是一个有用的想法：如果在产生的过程中已经产生了若干左、右括号，为了要把产生的行为完成，还欠R个左括号、L个右括号，那么有没有办法找出产生下一个括号时L与R的关系呢？记住，递归是一个不容忽视的利器。

解答见generate_parenthesis.py

已知一个n列n行的矩阵M,它的元素满足一个很特殊的性质, 即任一元素M[i][j]都小
于在它右边与下方的元素(如果存在的话), 换言之,M[i][j] < M[i][j+1]且M[i][j] < M[i+1][j]. 现在有一个值K, 编写一个程序, 检查矩阵M中是否有K。

说明: 这个矩阵有了一种很特殊的结构, 换言之, 每一列与每一行都从小到大排列, 所以
做寻找的工作时就可以通过这个特殊的顺序来编写程序。注意, 虽然有n ^ 2个元素, 但理论上可以证明, 在最坏的情况下, 2n - 1就可以决定K在不在M中; 关键所在, 就是如何模仿二分查找法的技巧在一次比较之后就尽可能去掉多余的元素.

解答见matrix_search.py

已知一个整数数组x[], 其中的元素彼此都不相同,而且也已经从小到大排列好,请用
比较大小、相等的方式编写一个程序, 找出给定的数组中是否存在一个元素满足x[i] = i的关
系。举例而言, 如果x[]={-2,-1,3,7,8}, x[3] = 3, 因此 3 就是答案, 因为编程语言中数组是从0开始的，所以最终是检测是否存在一个元素满足x[i] = i + 1.

说明: 用笨方法, 一个循环就可以找出答案, 如下程序所示

1
2
3
4
5
6
7
8
9
10
11

def bad_index_search(x):
    index = -1
    for i in range(0, len(x)):
        if x[i] == i + 1:
            index = i + 1
            break
    return index

if __name__ == "__main__":
    x = [-2, -1, 3, 7, 8]
    print(bad_index_search(x))

这个程序在最坏的情况下, for一共绕了n圈, 作了n次比较, 但却没有用到x[]的元
素已经排列好的条件. 事实上, 如果输入有n个元素, 应该可以写出与log(n)次成正比的比较的程序,关键是x[]的元素是排好顺序的。

解答见index_search.py

对于一个正整数n而言，它的一个分割(Partition),就是把n写成若干个正整数的和，但不计较书写的顺序。编写一个程序，输入n，把n的所有分割显示出来。
说明: 如果n=7, 那么有如下的分割.

7

6 1

5 2

5 1 1

4 3

4 2 1

4 1 1 1

3 3 1

3 2 2

3 2 1 1

3 1 1 1 1

2 2 2 1

2 2 1 1 1

2 1 1 1 1 1

1 1 1 1 1 1 1

一共有15个，仔细观察在各个输出中前后两者的差异，并且自己做一做其他的结果(比如n=5时有7个，n = 6时有11个等),就不难写出程序了。

将整数的所有不同分割数目递归解稍加改变，就可以得到一个递归解，解答见integer_partition_method.py

所谓的整数的分割(Partition of an Integer), 指的就是把一个正整数写成若干个正整数的和，但这里只计较有多少种分割方式，而不计较它的内容。例如，4=3+1,2+2,2+1+1,1+1+1+1+1, 再加上自己，就一共有5种分割方式。编写一个程序，输入一个正整数，输出它有多少种分割方式。

说明: 以下是几点重要的提示

1. 要把n进行分割，其实不完全只针对n, 还要看分割中最大的值是什么。例如，要把10进行分割，若在分割中最大的值是6，即10=6+…, 那么”…”的部分充其量的值是4而已，不仅如此，和还须等于4；因此，如果知道”…”, 即4有多少种分割方式，也正是在分割10时，最大值为6的分割方式！
2. 应该分析一下n这个输入值，与在分割中的极大值(如1.中的6)之间有什么联系，找出来，问题就解决了。

在C语言名题精选百则之整数的所有不同分割数目中得到一个递归解，我们可以将它转换成非递归解

解答见iteration_integer_partition.py

所谓的整数的分割(Partition of an Integer), 指的就是把一个正整数写成若干个正整数的和，但这里只计较有多少种分割方式，而不计较它的内容。例如，4=3+1,2+2,2+1+1,1+1+1+1+1, 再加上自己，就一共有5种分割方式。编写一个程序，输入一个正整数，输出它有多少种分割方式。

说明: 以下是几点重要的提示

1. 要把n进行分割，其实不完全只针对n, 还要看分割中最大的值是什么。例如，要把10进行分割，若在分割中最大的值是6，即10=6+…, 那么”…”的部分充其量的值是4而已，不仅如此，和还须等于4；因此，如果知道”…”, 即4有多少种分割方式，也正是在分割10时，最大值为6的分割方式！
2. 应该分析一下n这个输入值，与在分割中的极大值(如1.中的6)之间有什么联系，找出来，问题就解决了。
3. 不要忘了，递归是非常有效的武器

解答见integer_partition.py

编写一个程序,列出{1, 2, 3, … , n}这个集合的所有子集, 包括空集合.

说明: 列出一个集合的所有子集有很多做法,题目中并没有要求依某个特定的次序来排列,
因此是不难做出来的。 因为集合中一共有n个元素,所以总共就会有2 ^ n 个子集; 例如{1, 2, 3} 有如下子集: {} {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}

这里没有要求顺序，所以方法很多，随便选一种. 解答见direct.py

在C语言名题精选百则之产生所有排列字典顺序递归解说过，产生所有排列还有非递归解。

如何产生字典顺序的排列呢? 据Hall与 Knuth的考证, 200年(1812年)前Fischer与Kruse在他们的一本书中就已经提过这样的方法了。从1234…n开始,首先从右到左出第一对满足a(i) < a(i+1) 的a(i)与a(i+1),于是从a(i+1)起在它右边的就是越来越小的:有了a(i)之后再一次地从右到左查一次, 找出第一个满足a(i)< a(j)的a(j)。接着把a(i+1)到a(n)的各个元素反过来排, 就是字典顺序的下一个了。下面来看看如何找出153642的下一个:从右到左第一组满足a(i) < a(i+1)的是3与6,所以a(i),就是3。接着从右到左去找第一个a(j),使得a(i) < a(j),则是3 < 4; 把a(i)和a(j)换下位置，最后把a(i+1)与a(n)之间的元素反过来排,因此得到154236,这就是结果。

1. i = n - 1
2. 从右往左找，找到第一个i使得a(i) < a(i+1)
3. 从右往左找，找到第一个j使得a(i) < a(j)
4. 交换a(i)与a(j)
5. 将a(i+1),…a(n)反转
6. 回到第2步

如果找不到满足条件的i, 则结束程序。

例如153642, 从右往左找，找到第一个 i = 2 使得a(i) < a(i+1) 即3 < 6, 从右往左找，找到第一个 j = 3 使得a(i) < a(j) 即 3 < 4 交换a(i)和(j), 得到154632, 将a(i+1),..a(n)反转，即将632反转，得到154236, 所以154236就是153642的下一个排列。

解答见iteration_permutation.py