百度2014校招笔试题目题解
—-武汉站,9.28号百度校招笔试题目算法题目部分
二、算法与程序设计题
1、给定任意一个正整数,求比这个数大且最小的“不重复数”,“不重复数”的含义是相邻两位不相同,例如1101是重复数,而1201是不重复数。(15分)
2、长度为N(N很大)的字符串,求这个字符串里的最长回文子串。(15分)
3、数轴上从左到右有n各点a[0], a[1], ……,a[n -1],给定一根长度为L的绳子,求绳子最多能覆盖其中的几个点。(15分)
这是百度的笔试题目,好像是什么系统行为分析师职位的笔试题目!博文最后会贴出试题照片!
题解:(题解非官方,仅供参考,转载请联系博主,有错误的地方望指正!谢谢)
1、给定任意一个正整数,求比这个数大且最小的“不重复数”,“不重复数”的含义是相邻两位不相同,例如1101是重复数,而1201是不重复数。
解: 这道题目我也没有什么特别出彩的算法,就是按照常规思路来求解,首先要理解什么叫做“不重复数”,这是解题的关键之一,相邻两位不相同的数即为“不重复数”;还有一个地方要注意的就是“求比这个数大且最小的”,就是在比给定数大的不重复数中找到最小的!理解了这两个地方,这道题目就可以着手求解了!
我用一个实例来说说我的思路,加入给定的正整数为11233:
用最常规的方法,就是每次对这个数加1,判断是不是“不重复数”,加1后为11234,有两个1重复了,于是继续加1,……,那么主要就在判断是不是“不重复数”上面了,我设置了两个变量,是currentBit, lastBit,顾名思义,lastBit保存上一个数位的值,currentBit保存当前数位的值,拿整数12345来说,就是初始化lastBit = 5,然后计算currentBit = 4;下一步,把currentBit 值赋给lastBit,即lastBit = 4,计算currentBit = 3;依次类推。
说到这里,很多朋友觉得可以有更加高效的方法,小难点有4:
1、因为可以直接定位到“重复”的数位那里,比如12344,我们可以直接定位到个位数4和十位数4上面,然后在低位数(这里就是个位数)上加1即可,事实上,不是如此简单,假设是对整数12199呢?还能简单的加1操作吗,加1之后结果为12200,那结果显然是错的,当然这也是可以处理的,处理方法就是把12200继续拿到循环去判断是不是“非重复数”;
2、这里又产生一个问题,因为“重复“的数位可能不止一对,有可能有多对,比如整数11233,定位“33”之后变为“34”,定位“11”之后变为“12”,结果就是12234。又有重复的地方,就是“22”。继续拿到循环去重复;
3、还有要注意的是,你的程序设计,是如何存储数位的值的,是一个一个数位的值求出来呢?还是像我这样设置一个前后索引?每个数位取值,程序会变得繁琐复杂,不易读懂,如果是设置前后索引,则要注意程序退出循环的条件!
4、对于存在多对“重复”数位的正整数,数位“重复”的定位和变换,是从高位到低位,还是从低位到高位呢?正确的应该是从高位到低位,这与我们的程序设计也带来了不便。
这些就是我在试图找到高效算法时得到的经验,每个小难点都要处理,有点繁琐,有耐心的朋友,可以试着写一下更高效的算法,另外,使用了比较高效的算法,代码尽量保持简洁,并告知博主,谢谢!
注:评论网友13楼“巴鲁斯”给出了高效的C#算法代码,这个算法我当初也考虑了,我主学C,只是C处理字符串没有C#、Java那么方便,类型转换也比较麻烦,就没去管,十分感谢“巴鲁斯”朋友的code!来自评论中24楼朋友“garbageMan”给出了比较简洁的c语言代码,采用递归方法,值得借鉴!再次感谢!
my code:(简单加1的方法)
/*给定任意一个正整数,求比这个数大且最小的“不重复数”,“不重复数的含义是相邻两位不相同,例如1101是不重复数”*/#include <stdio.h>#include <stdlib.h>int getNumNonrepetition(const int NumGived){numRepeat = NumGived;int numTemp = 0;// (1){numRepeat++;//初始化后索引numTemp = numRepeat;lastBit = numTemp % 10;numTemp /= 10;flag = 1;(numTemp != 0){currentBit = numTemp % 10;numTemp /= 10;if(lastBit == currentBit){flag = 0;break;}lastBit = currentBit;}if(flag == 1)//该数为不重复数,返回{return numRepeat;}}}int main(void){int NumGived = 19922884;int result = getNumNonrepetition(NumGived);printf(, result);return 0;}
View Code
更新内容:(10.9号下午)
简单加1的算法,效率太低,看到这么多的朋友的评论,大家的算法大同小异,我也写了一个算法,拿出来和大伙分享。
算法:
1、把整数放到字符数组里面去,从高位为低位(用变量i)扫描,找到重复的数位,重复数位为“99”跳到第2步,否则跳到第3步,若没有重复的数位,则该数为不重复数,返回;
思念带着一种默默地忧伤,