Archive for ‘Programming Pearls’ Category

2011/07/19

问题:有一个数组 31,-41,59,26,-53,58,97,-93,-23,84 。现在要求出它的连续子串的最大值。 比如,31,-41,59,26是它的一个连续的子串,他们的和为75。但是75并不是最大值,有一个子串 59,26,-53,58,97它们的和187才是最大的。 求解:《Programming Pearls》第77页开始一共给出了4种解法,前两种非常简单,是大多数人思考几分钟就能想出的方法,但是复杂度却很高,分别为O(n^3)和O(n^2)。后两种解法则非常巧妙,更神奇的是第四种方法居然只有线性复杂度O(n)! 解法1、解法2略。 解法3:分治法,复杂度为O(nlogn)。 分治法在结构上是递归的,在保证不改变原问题的条件下,将问题的规模减小,生成多个子问题,并多次递归调用自身来解决子问题,之后再将子问题的求解结果合并成原问题的解。

10,790 views
2011/01/30

Programming Pearls Second Edition Page 11 Problem C : Given a dictionary of english words,find all sets of anagrams,For instance, “posts”,”stop”and ”tops” are all anagrams of one another because each can be formed by permuting the letters of the others. 按照书上给出的解法,先对每一个单词生成相应的“签名”(“signature”),即把单词中的字母按照字母表的顺序重新排列,例如stop 重新排列成opst , 然后把有相同signature的单词归为一组输出。基本过程如下: 其中sign()函数用于生成每一个单词的”签名“,如何生成呢?由于每个单词的长度一般都很短(不超过10个字母)于是可选择用直接插入排序法。其他的数据结构和函数很简单,直接看代码吧!

Tags: . 6,449 views