【题目】
给定任意一个正整数，求比这个数大且最小的“不重复数”，“不重复数”的含义是相邻两位不相同，例如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;
}//while
return 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
}//for
return 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;) {
// 情况：99
if(i > 0 && str[i] == '9' && str[i-1] == '9'){
str[i--] = '0';
str[i--] = '0';
// 99前一位加一
if(i >= 0){
str[i--] += 1;
}//if
else{
result = 1;
}//else
}//if
//情况：44
else if(i > 0 && str[i] == str[i-1]){
str[i] += 1;
pos = i + 1;
break;
}//else
else{
++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){
// 添加0
if(i % 2){
result = result * 10;
}//if
// 添加1
else{
result =result * 10 + 1;
}//else
}//for
return result;
}
};
int main(){
Solution s;
int result = s.MinNoRepetition(99);
cout<<result<<endl;
return 0;
}
