学步园

在大卫david的博客看到题解，但是他给出的方法是蛮力法，我就想了下解法，然而忘了看他博客下面的评论，做出来才发现和其他人的方法一样。

/*
	给定任意一个正整数，求比这个数大且最小的“不重复数”，“不重复数”的含义是相邻两位不相同，例如1101是重复数，而1201是不重复数。
	
	算法描述：
			求比NumGived大的最小“不重复数”res：（简单说就是找最高重复对，然后重复对的低位加1，重复对后面用0101...代替，需要注意的是重复数对值为9时需要额外考虑，因为存在进位）
			1.res=NumGived+1;
			2.找最高位重复对，若不存在此数即为所求；存在：重复数对值为0-8转3，值为9转4
			3.重复对低位+1，后面用01填充，此值即为所求；
			4.需要循环判断进位后的情况，因为进位可能导致重复对，此时再+1又可能导致重复对。
*/
//适用于int范围内的正整数
#include<iostream>
#include<vector>
using namespace std;

const int pre=2;//前两位填充0，用于在首位是9且要进位时的辅助判断

inline void intToVector(int &n,vector<int>&v){
	//989922884:v[0]=0,v[1]=0;v[2]=9,v[3]=8依次类推
	int mid=n;
	while(mid){
		v.insert(v.begin(),mid%10);
		mid/=10;
	}//while
	for(int i=0;i<pre;i++)//前两位填充0，用于在首位是9且要进位时的辅助判断
		v.insert(v.begin(),0);
}//inline void intToVector

inline int vectorToInt(const vector<int>&v){
	int res=v[pre-1];//v[1]，因为有可能进位
	for(size_t i=pre;i<=v.size()-1;i++)
		res=res*10+v[i];
	return res;
}//inline int vectorToInt

bool findRepeat(const vector<int>&v,int &pos){//pos是最高重复对的低位
	bool flag=false;
	for(size_t i=pre;i<v.size()-1;i++){
		if(v[i]==v[i+1]){
			flag=true;
			pos=i+1;
			break;
		}//if
	}//for
	return flag;
}//bool findRepeat

inline void fill(vector<int>&v,int begin){//从begin位开始填充010101...
	int mid=0;
	for(size_t i=begin;i<=v.size()-1;i++){
		v[i]=mid;
		++mid;
		mid%=2;
	}//for
}//fill

int getNumNonrepetition(const int NumGived) {
	int res=NumGived+1;
	int pos=0;
	vector<int> v;
	intToVector(res ,v);

	/*std::cout<<"Vector:";
	for(size_t i=0;i<v.size();i++)
		std::cout<<v[i];
	std::cout<<std::endl;
	*/
	if(findRepeat(v,pos)){
		if(v[pos]!=9){
			v[pos]++;
		}else{
			//v[pos]和v[pos-1]为9，因为寻找的是最高位重复对，所以v[pos-2]不可能为9，可以直接加1
			v[pos-2]++;//
			pos-=2;
			int flagPos=0;
			while(v[pos]==v[pos-1]){
				if(v[pos]!=9){
					v[pos]++;
					break;
				}else{
					v[pos-2]++;//
					pos-=2;
				}//else
			}//while		
		}//else
		fill(v,pos+1);
	}//if
	res=vectorToInt(v);
	return res;
}//getNumNonrepetition

int main(int argc,char** argv){
	int NumGived = 989922884;
	int res=0;

	res=getNumNonrepetition(NumGived);
	std::cout<<"Result="<<res<<std::endl;
		
	return EXIT_SUCCESS;
}