[经典面试题][百度]求比指定数大且最小的“不重复数”-阿里云开发者社区

开发者社区> 人工智能> 正文

[经典面试题][百度]求比指定数大且最小的“不重复数”

简介:

【题目】

给定任意一个正整数,求比这个数大且最小的“不重复数”,“不重复数”的含义是相邻两位不相同,例如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;
    }




版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章