[经典面试题][百度]求比指定数大且最小的“不重复数”

【题目】

给定任意一个正整数，求比这个数大且最小的“不重复数”，“不重复数”的含义是相邻两位不相同，例如1101是重复数，而1201是不重复数。

【来源】

2014年百度校招笔试题

【思路一：暴力】

数值加一，判断是否是重复数，如果是，继续加一判断，直到找到一个不是重复数的。

【代码一】

/*————————————-* 日期：2015-02-05* 作者：SJF0115* 题目: 最小不重复数* 来源：百度* 博客：————————————*/#include <iostream>#include <cstring>#include <vector>#include <algorithm>using namespace std;class Solution{public:int MinNoRepetition(int n){// 加一 判断是否是最小不重复数while(isRepetition(n)){++n;}//whilereturn n;}private:// 判断相邻字符是否重复bool isRepetition(int n){string str = to_string(n);int size = str.size();for (int i = 0;i < size;++i) {if(i > 0 && str[i] == str[i-1]){return true;}//if}//forreturn false;}//};int main(){Solution s;int result = s.MinNoRepetition(19900);cout<<result<<endl;return 0;}

【思路二】

经过分析得到：

只要找到最高重复位即可破题 如1123455 最高重复位为11则改为12其他填充01结果就是1201010 所以从最高位开始截 找到重复的2位，低位+1，然后填充01。

但有一种情况例外 就是99重复 这时候需要进位+1，反向判断 。如2199，则进位+1变为2200，反向判断22重复变为2300，然后填充01变为2301。最惨的就是8989899这种，，最后99重复，进位变为8989900，反向判断99重复，进位变为8990000，继续反向判断99重复，进位变为9000000，反向判断通过，填充01变为9010101，结果就是8989899->9010101

【代码二】

/*————————————-* 日期：2015-02-05* 作者：SJF0115* 题目: 最小不重复数* 来源：百度* 博客：————————————*/#include <iostream>#include <cstring>#include <vector>#include <algorithm>using namespace std;class Solution{public:int MinNoRepetition(int n){string str = to_string(n);int size = str.size();int result = 0;// 开始填充01的位置int pos = size;for (int i = 0;i < size;) {// 情况：99if(i > 0 && str[i] == '9' && str[i-1] == '9'){str[i–] = '0';str[i–] = '0';// 99前一位加一if(i >= 0){str[i–] += 1;}//ifelse{result = 1;}//else}//if//情况：44else if(i > 0 && str[i] == str[i-1]){str[i] += 1;pos = i + 1;break;}//elseelse{++i;}}//for// 前面不重复的for(int i = 0;i < pos;++i){result = result * 10 + str[i] – '0';}//for// 添加的01个数int count = size – pos;for(int i = 1;i <= count;++i){// 添加0if(i % 2){result = result * 10;}//if// 添加1else{result =result * 10 + 1;}//else}//forreturn result;}};int main(){Solution s;int result = s.MinNoRepetition(99);cout<<result<<endl;return 0;}

放下一种执着，收获一种自在。放下既是一种理性抉择，也是一种豁达美。