## 啊哈!算法
第2章圍繞3個問題展開。
* 給定一個包含32位整數的順序文件,它至多只能包含40億個這樣的整數, 并且整數的次序是隨機的。請查找一個此文件中不存在的32位整數。 在有足夠主存的情況下,你會如何解決這個問題? 如果你可以使用若干外部臨時文件,但可用主存卻只有上百字節, 你會如何解決這個問題?
這是CTCI中的一道題目,詳細解答請戳以下鏈接:
[請猛戳我](http://www.hawstein.com/posts/12.3.html)
* 請將一個具有n個元素的一維向量向左旋轉i個位置。例如,假設n=8,i=3, 那么向量abcdefgh旋轉之后得到向量defghabc。
這個問題很常見了,做3次翻轉即可,無需額外空間:
~~~
reverse(0, i-1); // cbadefgh
reverse(i, n-1); // cbahgfed
reverse(0, n-1); // defghabc
~~~
* 給定一本英語單詞詞典,請找出所有的變位詞集。例如,因為“pots”, “stop”,“tops”相互之間都是由另一個詞的各個字母改變序列而構成的, 因此這些詞相互之間就是變位詞。
這個問題可以分3步來解決。第一步將每個單詞按字典序排序, 做為原單詞的簽名,這樣一來,變位詞就會具有相同的簽名。 第二步對所有的單詞按照其簽名進行排序,這樣一來,變位詞就會聚集到一起。 第三步將變位詞分組,形成變位詞集。示意圖如下:
