看到某人翻译的一个帖子，是关于Google面试的，其中我最感兴趣的是拿到面试题，问题是这样的：

假设这有一个各种字母组成的字符串，假设这还有另外一个字符串，而且这个字符串里的字母数相对少一些。从算法是讲，什么方法能最快的查出所有小字符串里的字母在大字符串里都有？

比如，如果是下面两个字符串：

String 1: ABCDEFGHLMNOPQRS

String 2: DCGSRQPOM

答案是true，所有在string2里的字母string1也都有。如果是下面两个字符串：

String 1: ABCDEFGHLMNOPQRS

String 2: DCGSRQPOZ

答案是false，因为第二个字符串里的Z字母不在第一个字符串里。

这道题最聪明的解决方法不是对两个字符串的轮询，而是用到质数：

给每个字母分配一个素数，从2开始，往后类推。这样A将会是2，B将会是3，C将会是5，等等。现在遍历第一个字串，把每个字母代表的素数相乘。最终会得到一个很大的整数，然后 —— 轮询第二个字符串，用每个字母除它。如果除的结果有余数，这说明有不匹配的字母。如果整个过程中没有余数，就应该知道它是第一个字串恰好的子集了。

什么是质数，质数有那些听说的很多，但是真正拿到编程时候用的还是第一次看见，回想从初中、高中、大学学到的那些数理化，到现在为止真正用到编程上的还真没有，所以，我不是一个好的程序员。

参考：http://www.aqee.net/google-interviewing-story/

转载请注明：26点的博客 » 数学学不好 编程做不了