2014百度研发真题及其解析-求比指定数大且最小的“不重复数”

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/article/details/54773392

题目:

给定一个正整数n,求比n大的第一个“不重复数”。”不重复数“的定义:如果一个数,任何相邻两个数位上的数字都不相同,则称为不重复数。例如1234是不重复数,而1101不是。


思路一:暴力

数值加一,判断是否是重复数,如果是,继续加一判断,直到找到一个不是重复数的。

#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。

 #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;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Jack-Cui

Day3、Python

题目 输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数。 1、程序分析     根据题意可知,需要用到字符串的操作方法。本题中要用到的三...

18200
来自专栏PHP在线

php面试题(二)

1 <?php echo count (false); $a = count ("567") + count(null) + count(false); ec...

44980
来自专栏数据结构与算法

26:字符串最大跨距

26:字符串最大跨距 总时间限制: 1000ms 内存限制: 65536kB描述 有三个字符串S,S1,S2,其中,S长度不超过300,S1和S2的长度不超过...

45480
来自专栏python3

python random模块

随机输出一个0~4的数字和range()输出的数字,去比较。猜对了,就是字母,否则是数字

8620
来自专栏数据结构与算法

1696:逆波兰表达式

1696:逆波兰表达式 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述逆波兰表达式是一种把运算符前置的算术表达式,例如普通的...

37970
来自专栏数据结构与算法

U9249 【模板】BSGS

题目描述 给定a,b,p,求最小的非负整数x 满足a^x≡b(mod p) 若无解 请输出“orz” 输入输出格式 输入格式: 三个整数,分别为a,b,p 输出...

36370
来自专栏老秦求学

题目1054:字符串内排序

题目描述: 输入一个字符串,长度小于等于200,然后将输出按字符顺序升序排序后的字符串。 输入: 测试数据有多组,输入字符串。 输出: 对于每组输入,输出处理后...

34870
来自专栏C/C++基础

常见排序算法分类

  此篇博客不讨论排序算法的思想,时间复杂度,空间复杂度,实现代码。只介绍常见排序算法有哪些,并按照什么进行分类。   排序算法分为两大类: 比较类...

14720
来自专栏数据结构与算法

洛谷P2181 对角线(组合数)

题目描述 对于一个N个定点的凸多边形,他的任何三条对角线都不会交于一点。请求楚图形中对角线交点的个数。 例如,6边形: ? 输入输出格式 输入格式: 第一行一个...

36050
来自专栏desperate633

LintCode 完美平方题目分析代码

给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。

9520

扫码关注云+社区

领取腾讯云代金券