数学学不好 编程做不了

PHP 林涛 8907℃ 0评论

看到某人翻译的一个帖子,是关于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点的博客

本文链接地址: 数学学不好 编程做不了

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

喜欢 (0)
发表我的评论
取消评论

表情
(6)个小伙伴在吐槽
  1. 确实有道理,因为不懂所以头疼,哈哈
    美金兄弟连2012-09-03 22:26 回复
    • 别着急,代码要多看、要多谢,其实编程是个技术活,没有什么难度。
      林涛2012-09-03 22:30 回复
  2. 处理代码我会头疼,这样子是不是数学肯定不好
    美金兄弟连2012-08-30 17:00 回复
    • 处理代码头疼说明你还没有完全进入状态,处理问题的方式不合理才是数学不好的表现呢
      林涛2012-09-03 22:20 回复
  3. 行啊 小文章
    种植网2012-08-29 22:04 回复