最新百度实习生面试一试题

1万 · 2012-6-12 10:45

第一题、任意给一个数，试证明这个数的某个倍数的十进制表示是01串，比如3的倍数111是二进制表示，5的倍数10是二进制表示，等等。

第二题、证明素数有无穷多个。

第三题、给一个很大的数组，里面有两个数只出现过一次，其他数都出现过两次，把这两个数找出来。

第四题、把一个链表逆过来，要求空间复杂度O(1)，这个算简单的。

这几道题我看了半天的，的却我这种凡夫俗子短期内是整不出来的，求助高手了。。

只看该作者 · 2012-6-12 12:47

第三题
要判断的数组为A
定义一个数组B用来存不重复数,和索引bindex
定义一个数组C用来存对应数的数量
把第0个数放入A
A循环 i=1
{
   B循环 j=0
  {
      如果A[i]等于B[j]
C[j]+=1;
否则
B[bindex++]=A[i];

}
}
C循环
查找value为1的索引
B[C索引。。]就是想要找的值

只看该作者 · 2012-6-12 16:26

要判断的数组为A
定义一个数组B用来存放只出现一次的数据,和索引bindex
把第A[0]个数放入B[0]
A循环 i=1
{
   B循环 j=0
  {
      如果A[i]等于B[j]
      B[j]=B[bindex--];删除重复数据
      否则
      B[bindex++]=A[i];

}
}
最后bindex为只出现一次的数量
B里存放的为只出现过一次的数据

只看该作者 · 2012-6-12 16:30

学习了

只看该作者 · 2012-6-12 16:31

1# shenmu2012 学习了

只看该作者 · 2012-6-12 19:47

前面二题是数学里的吧，你怎么用程序来证明呢？

只看该作者 · 2012-6-12 21:08

这要不跟二楼学习，我是做不出来的。汗。我承认我也是个凡夫俗子

只看该作者 · 2012-6-12 21:21

长见识了。

只看该作者 · 2012-6-12 22:17

本帖最后由 joseph2675 于 2012-6-12 22:30 编辑

第一题任何整数都可以用二进制来表示任意给一个数它的某个倍数可以是整数
第二题如果素数是有限的话那么合数是由若干个质数相乘而得到的若干个质数相乘必然也是有限的
而素数和合数一起组成了正整数那么正整数也是有限的和事实相悖

只看该作者 · 2012-6-12 22:19

素数和合数一起组成了除1外的正整数参见百度百科

只看该作者 · 2012-6-12 22:24

确实挺考验老子灵活性的！！！

只看该作者 · 2012-6-12 23:01

9# joseph2675 你的证明是错的，思路有点沾边
2的N次方也可以趋近无穷大可是只有一个因子；
正确的证明是
假设自然数中只有有限多个素数，不妨设为n个，它们是q1,q2,q3,…,qn。现构造一个数A=(q1*q2*q3*…*qn)+1，A比q1,…qn中的任何一个都大，因此与它们都不同，假设A是合数。A不能被q1,…qn中的任何一个整除，因为会余1，所以q1,…qn都不是A的因子，即A不能表示成q1,…qn的乘积，这与我们假设的只有q1,…qn是素数是矛盾的，因此自然数中有无限多个素数，证毕