題目：

給定一個正整數(shù)n，求比n大的第一個“不重復(fù)數(shù)”。”不重復(fù)數(shù)“的定義：如果一個數(shù)，任何相鄰兩個數(shù)位上的數(shù)字都不相同，則稱為不重復(fù)數(shù)。例如1234是不重復(fù)數(shù)，而1101不是。

---

思路一：暴力

數(shù)值加一，判斷是否是重復(fù)數(shù)，如果是，繼續(xù)加一判斷，直到找到一個不是重復(fù)數(shù)的。

#include <iostream>#include <cstring>#include <vector>#include <algorithm>using namespace std;class Solution{public:int MinNoRepetition(int n){// 加一 判斷是否是最小不重復(fù)數(shù)while(isRepetition(n)){++n;}//whilereturn n;}private:// 判斷相鄰字符是否重復(fù)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;}

---

思路二：

經(jīng)過分析得到：

只要找到最高重復(fù)位即可破題 如1123455 最高重復(fù)位為11則改為12其他填充01結(jié)果就是1201010 所以從最高位開始截 找到重復(fù)的2位，低位+1，然后填充01。

但有一種情況例外 就是99重復(fù) 這時候需要進位+1，反向判斷 。如2199，則進位+1變?yōu)?200，反向判斷22重復(fù)變?yōu)?300，然后填充01變?yōu)?301。最慘的就是8989899這種，最后99重復(fù)，進位變?yōu)?989900，反向判斷99重復(fù)，進位變?yōu)?990000，繼續(xù)反向判斷99重復(fù)，進位變?yōu)?000000，反向判斷通過，填充01變?yōu)?010101，結(jié)果就是8989899->9010101。

#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// 前面不重復(fù)的for(int i = 0;i < pos;++i){result = result * 10 + str[i] - '0';}//for// 添加的01個數(shù)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;}

總結(jié)

以上是生活随笔為你收集整理的2014百度研发真题及其解析-求比指定数大且最小的“不重复数”的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。