百度2014校招笔试题目题解
百度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、对于存在多对“重复”数位的正整数，数位“重复”的定位和变换，是从高位到低位，还是从低位到高位呢？正确的应该是从高位到低位，这给我们的程序设计也带来了不便。
这些就是我在试图找到高效算法时得到的经验，每个小难点都要处理，有点繁琐，有耐心的朋友，可以试着写一下更高效的算法，另外，使用了比较高效的算法，代码尽量保持简洁，并告知博主，谢谢！
my code：(简单加1的方法)
第二类“123321”：中间是两个相同的字符。算法思想同上，其实是一样的过程！图解也是一样的！
my code：
my code：
注：1.本文版权归作者和CSDN所有，未经允许不得转载，侵权必究！
2.本博客与博客园上的博客为同一博客主：http://www.cnblogs.com/bestDavid/
