啊哈！算法

啊哈！算法

第2章圍繞3個(gè)問題展開。

• 給定一個(gè)包含32位整數(shù)的順序文件，它至多只能包含40億個(gè)這樣的整數(shù)， 并且整數(shù)的次序是隨機(jī)的。請(qǐng)查找一個(gè)此文件中不存在的32位整數(shù)。 在有足夠主存的情況下，你會(huì)如何解決這個(gè)問題？ 如果你可以使用若干外部臨時(shí)文件，但可用主存卻只有上百字節(jié)， 你會(huì)如何解決這個(gè)問題？

這是CTCI中的一道題目，詳細(xì)解答請(qǐng)戳以下鏈接：

請(qǐng)猛戳我

• 請(qǐng)將一個(gè)具有n個(gè)元素的一維向量向左旋轉(zhuǎn)i個(gè)位置。例如，假設(shè)n=8,i=3， 那么向量abcdefgh旋轉(zhuǎn)之后得到向量defghabc。

這個(gè)問題很常見了，做3次翻轉(zhuǎn)即可，無需額外空間：

reverse(0, i-1); // cbadefgh
reverse(i, n-1); // cbahgfed
reverse(0, n-1); // defghabc

• 給定一本英語單詞詞典，請(qǐng)找出所有的變位詞集。例如，因?yàn)椤皃ots”， “stop”，“tops”相互之間都是由另一個(gè)詞的各個(gè)字母改變序列而構(gòu)成的， 因此這些詞相互之間就是變位詞。

這個(gè)問題可以分3步來解決。第一步將每個(gè)單詞按字典序排序， 做為原單詞的簽名，這樣一來，變位詞就會(huì)具有相同的簽名。 第二步對(duì)所有的單詞按照其簽名進(jìn)行排序，這樣一來，變位詞就會(huì)聚集到一起。 第三步將變位詞分組，形成變位詞集。示意圖如下：