本文主要是介绍百度笔试题:找最小的不重复数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
版权所有。所有权利保留。
欢迎转载,转载时请注明出处:
http://blog.csdn.net/xiaofei_it/article/details/17123835
给定任意一个正整数,求比这个数大且最小的“不重复数”,“不重复数”的含义是相邻两位不相同,例如1101是重复数,而1201是不重复数。
思路很简单:
1、把原数加1。
2、从高位开始找重复位。
3、将这位加1。
4、如果是10,此位变0,指针指向高位,转3。如果不是10,转5。
5、这位是否与高位相同,相同的话,转3。不同则转6。
6、把这位以后刷成01串。
其实本质就是贪心,把最高的重复位变掉,之后刷成01串,但变后可能又重复了,那么再变。
自己试试即可。
代码如下:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 100
int n[MAX],len;
void convert(string str)
{memset(n,0,sizeof(n));for (int i=0;i<str.length();i++)n[str.length()-1-i]=str[i]-'0';len=str.length();
}
void find()
{int i;n[0]++;for (i=0;n[i]==10;i++){n[i]=0;n[i+1]++;}if (i==len) len++;bool yes=true;for (i=len-1;i>=1;i--)if (n[i]==n[i-1]){yes=false;break;}if (yes) return;n[--i]++;while (true){while (n[i]==10){n[i]=0;n[++i]++;}if (i==len)len++;if (n[i]==n[i+1])n[i]++;elsebreak;}if (i==0) return;n[--i]=0;for (i--;i>=0;i--)n[i]=1-n[i+1];
}
int main()
{string str;while (cin>>str){convert(str);find();for (int i=len-1;i>=0;i--) cout<<n[i];cout<<endl;}return 0;
}
输入样例:
121
19898989
989898989
989898
1989898
2199
120
0
2
21
20
输出样例:
123
20101010
1010101010
1010101
2010101
2301
121
1
3
23
21
这篇关于百度笔试题:找最小的不重复数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!