【题目】
给定任意一个正整数,求比这个数大且最小的“不重复数”,“不重复数”的含义是相邻两位不相同,例如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;
}
分享到:
相关推荐
嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题嵌入式经典面试题
C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题C ++经典面试题
Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 ...
PHP经典面试题 PHP经典面试题 PHP经典面试题 PHP经典面试题 PHP经典面试题
阿里面试20题 百度面试10题 华为面试10题 京东面试13题 腾讯面试37题 头条面试10题 项目经理面试常遇问题 经典面试题 程序员 IT经理 项目经理 面试题 研发经理 高级程序员 经典面试题
SQL经典面试题及答案 SQL经典面试题及答案
10万字208道Java经典面试题总结(附答案).pdf 10万字208道Java经典面试题总结(附答案).pdf 10万字208道Java经典面试题总结(附答案).pdf 10万字208道Java经典面试题总结(附答案).pdf 10万字208道Java经典面试题总结(附...
C语言经典面试题 对求职者很有帮助 请大家下载 免积分 攒人品
面试时整理的资料,大家可以看看,面试的java题目,面试时整理的资料,大家可以看看,面试的java题目
cobol面试题 cobol面试题 cobol面试题
2022年SQL数据库经典面试题笔试题 (2).pdf2022年SQL数据库经典面试题笔试题 (2).pdf2022年SQL数据库经典面试题笔试题 (2).pdf2022年SQL数据库经典面试题笔试题 (2).pdf2022年SQL数据库经典面试题笔试题 (2).pdf2022...
c语音经典面试题,来自培训机构内部面试题库。
Spring经典面试题Spring经典面试题Spring经典面试题Spring经典面试题
各公司经典面试题选取
vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典面试题及答案.rar vue经典...
java经典面试题(典藏版)java经典面试题(典藏版)java经典面试题(典藏版)java经典面试题(典藏版)java经典面试题(典藏版)
oracle经典面试题,对于提升对oracle数据库的认知有很大帮忙,可以较快提高面试能力
sqlserver 经典面试题。详细说明面试重点,值得参考
2020 java经典面试题总汇.zip
百度面试题大收集百度面试题大收集百度面试题大收集