算法是一个程序员的基本功，在面对一个问题的时候，如果用常规的思维来思考，往往只能得到一个中规中矩甚至效率十分低下的解法。这个时候如果稍加思考，或者think out the box，就会灵光乍现，得到算法的aha! insights，想出十分巧妙的解法。这个专栏主要讲的就是思考后得到的aha! algorithms（巧妙的算法）。Martin Gardner说过：“A problem that seems difficult may have a simple,unexpected solution”。
提出了三个问题：
1. 有一个文件包含有至多40亿个32位整数，找出一个文件中没有的32位整数。如果内存只有几百字节，但是可以使用几个外部文件，你怎么解决这个问题？
这个问题可以用二分搜索（Binary Search）来解决。（要记住，二分搜索是非常有用的算法，以后会经常用到，人家的时间复杂度可是logn啊！！！非常牛×啊！！）这一题的主要思路就是先遍历所有的32位整数，然后把0开头的放到一个顺序文件中，1开头的放到另一个文件中。如下图所示：
然后，我们使用那个最多有20亿个整数的文件，然后重复以上的步骤，不过这次从第二位开始看起，以此类推，缺少的那个整数就可以通过排序和扫描找到。
2. 一个非常经典的移位问题：把一个n个元素的一维向量左移i位，例如，n =8,i = 3。把向量abcdefgh左移3位成 defghabc，通常的简单的办法是使用一个n元素的中间向量在n步内做完。那么如何使用更少的空间更快地完成呢？
第一种方法有点Juggling的意味，写成伪代码可以表示如下（rotdist表示左移的位数）：
第二种方法叫reversal，反转法。
只需要三步即可(reverse(a,b)表示a到b沿中间轴反转)：
reverse(0,i-1) /* cbadefgh */
reverse(i,n-1) /* cbahgfed */
reverse(0,n-1) /* defghabc */
3. 给定一个英文单词的字典，找出所有的回文单词。例如：”pots” “stop” “tops”。
英文单词这么多，大概二十几万个，全部遍历一遍一个一个进行比较肯定是不现实的，书上算了下大概需要14.7个小时。问题的关键就在于需要了解到回文的各个单词之间拥有相同的signature（签名）。只要找到拥有同样签名的单词即可。例如这里可以把签名设定为把单词的字母按照字典排序，pots stop tops这三个的签名均为opst。问题便迎刃而解。实现一个回文程序大概是三个步骤：sign -> sort -> squash。sigh就是给字典里的单词增加签名，sort就是把签名按照字典序排列，squash就是把相同签名的单词输出到同一行。
感想：
/* Binary Search 在一个排好序的表中查找一个元素时非常有效，唯一的缺点是需要知道整个表，而且要事先排好序 */
/* 签名（Signatures）在划分一类事物时候非常有用 */
/* A Problem Solver’s Perspective. Good programmers are a little bit lazy: they sit back and wait for an insight rather than rushing forward with their idea */
全文完。EOF
/* 原创文章，本文采用 BY-NC-SA 协议进行授权. 转载请注明转自: Swarm’s Blog*/
0 Comments.