首页 > 试题广场 >

给定N是一个正整数,求比N大的最小“不重复数”,这里的不重复

[问答题]
给定N是一个正整数,求比N大的最小“不重复数”,这里的不重复是指没有两个相等的相邻位,如1102中的11是相等的两个相邻位故不是不重复数,而12301是不重复数。
推荐

算法思想:当然最直接的方法是采用暴力法,从N+1开始逐步加1判断是否是不重复数,是就退出循环输出,这种方法一般是不可取的,例如N=11000000,你要一个个的加1要加到12010101,一共循环百万次,每次都要重复判断是否是不重复数,效率极其低下,因此是不可取的。这里我采用的方法是:从N+1的最高位往右开始判断与其次高位是否相等,如果发现相等的(即为重复数)则将次高位加1,注意这里可能进位,如8921—>9021,后面的直接置为010101...形式,如1121—>1201,此时便完成“不重复数”的初步构造,但此时的“不重复数”不一定是真正的不重复的数,因为可能进位后的次高位变为0或进位后变成00,如9921—>10001,此时需要再次循环判断重新构造直至满足条件即可,这种方法循环的次数比较少,可以接受。


Source Code:


// 求比指定数大且最小的“不重复数”
#include void minNotRep(int n)
{
    // 需要多次判断
    while(1)
    {
        int a[20], len = 0, i, b = 0;
        // flag为true表示是“重复数”,为false表示表示是“不重复数” 
       bool flag = false; 
       // 将n的各位上数字存到数组a中
        while(n)
        { 
           a[len++] = n % 10;
            n = n / 10;
        }
        // 从高位开始遍历是否有重复位
        for(i = len - 1; i > 0; i--) 
       { 
           // 有重复位则次高位加1(最高位有可能进位但这里不需要额外处理)
            if(a[i] == a[i - 1] && !flag) 
           {
                a[i - 1]++; 
               flag = true;
            }
            else if(flag) 
           {
                // 将重复位后面的位置为0101...形式
                a[i - 1] = b;
                b = (b == 0) ? 1 : 0;
            }
        } 
       // 重组各位数字为n,如果是“不重复数”则输出退出否则继续判断
        for(i = len - 1; i >= 0; i--)
        {
            n = n * 10 + a[i];
        } 
       if(!flag)
        {
            printf("%d\n", n); 
           break; 
       }
    }
}
int main()
{
    int N;
    while(scanf("%d", &N))
    {
        minNotRep(N + 1); 
   } 
   return 0;
}



编辑于 2015-01-28 17:42:23 回复(2)
string Test38_ADJ(string str){
	//++ to ensure the smallest 自增一,确保比之前的数 大
	int orilen = str.size();
	if( str[str.size()-1] !='9' ){
		str[str.size()-1] += 1;
	}else{
		int pos = str.size()-1;
		str[pos--]='0';
		bool jump = true;
		while(jump && pos>=0){
			if( str[pos] == '9' ){
				str[pos] ='0';jump = true; pos--;
			}else{
				str[pos] +=1;
				jump = false;
			}
		}
		if(jump){
			str = "1"+str;
		}
	}
	//cout<<str;
	

	if( str.size() > orilen ){
		//length increase
		for(int i =1;i< str.size();i++){
			if(i%2==1)str[i]='0';else str[i]='1'; //010101...
		}
	}else{
		//length stay
		if(str.size()>1){ //ensure length > 1
			int fixed = 1;
			while(fixed < str.size()){ //every bit
				if(str[fixed]!=str[fixed-1]){
					fixed++; //@OK,no repeat
				}else{//poorly wrong
					if(str[fixed]=='9'){
						//Circle
						string tmp = Test38_ADJ(str.substr(0,fixed+1));
						//int tchar = tmp[tmp.size()-1]-'0';
						//cout<<"h3:"<<tmp<<endl;
						if(tmp[tmp.size()-1]=='0'){
							for( int i = 0; i< str.size()-fixed-1;i++ ){
								if(i%2==0)tmp+='1';else tmp +='0';
							}
						}else{
							for( int i = 0; i< str.size()-fixed-1;i++ ){
								if(i%2==0)tmp+='0';else tmp +='1';
							}
						}
						str = tmp;
						fixed++;
						//cout<<"he1:"<<str<<endl;
					}else{ //adjust while not wrong
						str[fixed]+=1;
						fixed++;
						//cout<<"he2:"<<str<<endl;
					}
				}
			}
		}
	}
	return str;
}

void Test38(){
	string str;
	cin>>str;
	
	str = Test38_ADJ(str);
	
	cout<<str<<endl;
}



Test case:

9 =>10
79->80
65->67
899654->901010
9999->10101


祝好!
发表于 2015-09-10 20:48:02 回复(0)
的高规格
发表于 2014-11-04 15:03:31 回复(0)
/*问题描述;
给定N是一个正整数,求比N大的最小“不重复数”,这里的不重复是指没有两个相等的相邻位,
例如1102中的11是相等的两个相邻位故不是不重复数,而12301是不重复数。*/
#include <iostream> 
#include <string.h> 
#include <stdlib.h> 
using namespace std;  
/****************************************************************************  
*函数功能:处理数字相加的进位  
*输入参数:num为字符数组,pos为进行加1操作对应的下标位置  
****************************************************************************/  
void carry(char *num, int pos)  
{  
    for (; pos>0; pos--)  
    {  
        if (num[pos]>'9')  
        {  
            num[pos] = '0';  
            num[pos - 1]++;  
        }  
    }  
}  
/****************************************************************************  
*函数功能:获取大于n的最小不重复数  
*输入参数:n为正整数  
*返回值:大于n的最小不重复数  
****************************************************************************/  
int findMinNonDupNum(int n)  
{  
    int count = 0; //用来记录循环次数  
    char* ch = new char[n];    
    //char ch[15];  
    sprintf(ch, "0%d", n + 1); //把给定数字+1并转换为字符数组,数组首位值为‘0’ 
//    for(int ii=0;ii<5;ii++)
//        cout<<ch[ii]<<" ";
    cout << strlen(ch) << endl;    
    int len = strlen(ch) - 1; //数字n的长度
    cout << "数字n的长度为:" << len << endl;
    int i = len; //从右向左遍历  
    while (i>0)  
    {  
        count++;  
        if (ch[i - 1] == ch[i])  
        {  
            ch[i]++;//末尾数字加1  
            carry(ch, i);//处理进位  
            //把下标为i后面的字符串变为0101...串  
            for (int j = i + 1; j <= len; j++)  
            {  
                if ((j - i) % 2 == 1)  
                    ch[j] = '0';  
                else  
                    ch[j] = '1';  
            }  
            //第i位加1后,可能会与第i+1位相等,i++用来处理这种情况  
            i++;  
        }  
        else  
        {  
            i--;  
        }  
    }  
    cout << "循环次数为:" << count << endl;  
    int num = atoi(ch);  
    delete[] ch;  
    return num;  
}  
int main()  
{  
    cout << findMinNonDupNum(23345) << endl;  
    cout << endl;

    cout << findMinNonDupNum(1101010) << endl; 
    cout << endl;

    cout << findMinNonDupNum(99010) << endl;  
    cout << endl;

    cout << findMinNonDupNum(8989) << endl;  
    cout << endl;
    return 0;  


发表于 2018-06-11 11:08:17 回复(0)
2022微软笔试原题
发表于 2022-02-12 22:46:12 回复(0)
#include<iostream>
using namespace std;
string minX(const string& s){
    if(s.size()==1)return string(s);
    string result;
    result.push_back(s[0]);
    bool carry=false;
    for(int i=1;i<s.size();++i){
        if(carry)result.push_back(result.back()=='0'?'1':'0');
        else if(s[i]==result.back()){
            carry=true;
            if(s[i]=='9'){
                result.pop_back();
                if(result.empty())result.push_back('1');
                else result.back()=result.back()+1;
                result.push_back('0');
                result.push_back('1');
            }else result.push_back(s[i]+1);
        }else result.push_back(s[i]);
    }
    return result;
}
int main(){
    string s;
    cin>>s;
    cout<<minX(s)<<endl;
    return 0;
}
嗯...好吧,这是大于等于N的不重复。。。只好在处理之前先加一了。
发表于 2018-09-26 17:31:05 回复(0)
最小循环次数,把高位重复的加1,低位全部用0101填充
#include <iostream>
#include <string>
using namespace std;

int main()
{
	int i = 0;
	char c = 0;
	long num = 0;
	cin >> num;
	string strNum = std::to_string(num+1);

	int nHightLength = strNum.length();
	do {
		//查找相邻的重复数
		i = 0;
		do {
			c = strNum[i];
		} while (++i < nHightLength && c != strNum[i]);	//在高位遍历

		//有重复位数,截取高位加1,替换原有的高位
		if (i != nHightLength)
		{
			string substr = strNum.substr(0, i+1);  //截取存在重复的高位
			nHightLength = substr.length();
			long nHignt = stol(substr) + 1;			//加1
			strNum.replace(strNum.begin(), strNum.begin() + i + 1, std::to_string(nHignt));
		}
	} while (i != nHightLength);	//如果循环中有重复,则再次循环,如99+1=100出现了两个0

	//尾部填充0或1,判断填充前高位的最后一个是0还是1
	bool change = strNum[nHightLength - 1] - '0';
	for (int i = nHightLength; i < strNum.length(); ++i, change = !change)
	{
		strNum[i] = change ? '0' : '1';
	}

	cout << strNum << endl;
	system("pause");
	return 0;
}

编辑于 2017-08-17 16:35:48 回复(1)
<pre class="prettyprint lang-java">import java.util.Scanner; public class NotDuplicate { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println(find(n)); } public static int find(int n){ if(n&lt;=0){ return 0; }else if(n&lt;10){ return n+1; } int res = n; int flag = 0; while(flag==0){ res++; char[] num = String.valueOf(res).toCharArray(); for(int i=1;i&lt;num.length;i++){ if(num[i]==num[i-1]){ break; }else if(i==num.length-1){ flag=1; } } } return res; } }</pre> <br />
发表于 2015-09-10 10:40:36 回复(0)
<pre class="prettyprint lang-cpp">#include&lt;iostream&gt; using namespace std; bool isValid(int num) { int i=num%10; num=num/10; while(num) { if(i==num%10) return false; i=num%10; num=num/10; } return true; } int main() { int N; cin&gt;&gt;N; ++N; while(1) { if(isValid(N)) break; ++N; } cout&lt;&lt;N&lt;&lt;endl; } </pre> <div> <br /> </div> <br />
发表于 2015-09-09 20:08:55 回复(0)
// 1) 逐个比较 O(n)

 1 /*************************************************************************  

  2     > File Name: no_overlap.cpp

  3     > Author: dsui

  4     */

  5 #include <iostream>

  6 using namespace std;

  7 int main(int argc, char* argv[]){

  8     int n;

  9     cin>>n;

 10     while(n>=10){

 11         int cur = n % 10;

 12         n /= 10;

 13         int next = n % 10;

 14         if(cur == next){

 15             cout<<"overlap"<<endl;

 16             return 0;

 17         }

 18     }

 19     cout<<"non-overlap"<<endl;

 20     return 0;

 21 }


发表于 2014-12-22 23:54:46 回复(0)
// 求比指定数大且最小的“不重复数”
#include <stdio.h>

void minNotRep(int n) { // 需要多次判断
    while (1 ) { int a[20 ], len = 0 , i, b = 0 ; // flag为true表示是“重复数”,为false表示表示是“不重复数”
        bool flag = false ; // 将n的各位上数字存到数组a中
        while (n) { a[len ++] = n % 10 ; n = n / 10 ; } // 从高位开始遍历是否有重复位
        for (i = len - 1 ; i > 0 ; i--) { // 有重复位则次高位加1(最高位有可能进位但这里不需要额外处理)
            if (a[i] == a[i - 1 ] && !flag) { a[i - 1]++; flag = true ; } else if (flag) { // 将重复位后面的位置为0101...形式
                a[i - 1 ] = b; b = (b == 0 ) ? 1 : 0 ; } } // 重组各位数字为n,如果是“不重复数”则输出退出否则继续判断
        for (i = len - 1 ; i >= 0 ; i--) { n = n * 10 + a[i]; } if (!flag) { printf( " %d\n " , n); break ; } } } int main() { int N; while (scanf(" %d " , &N)) { minNotRep(N + 1 ); } return 0 ; }
发表于 2014-12-08 01:10:50 回复(0)
发表于 2014-11-29 14:42:37 回复(0)
public int getBigNum(num)
{
    
}
bool isEqul(num2)
{
    
}
发表于 2014-11-05 21:25:43 回复(0)
2413412321
发表于 2014-11-05 13:59:11 回复(0)