面试题解:输入一个数A,找到大于A的一个最小数B,且B中不存在连续相当的两个数字

昨天发的算法有一处情况没考虑到,比如加一后有进位,导致又出现重复数字的情况,修正后今天重新发一次。

比如输入99,那B应该是101 因为100有两个连续相当的0。

基本思路:最坏的办法 加1一直加1 直到找到有不重复的数为止。

面试:这道题要是作为面试题的话,要跟面试官确认好,数A的范围,比如是否有小数是否有负数,等等。在这里我们把题确定为正数。

优化思路:

如果输入的数本身不存在重复,则加1;如果存在重复,比如我们输入的是11100234,那如果要找比11100234大的最小没有重复的数,最先重复的两位数是11,那么如果想让11不重复并且比11100234大,那么应该让第二位的1加1 变成12100234。然后为了让数字最小,则把2后面的数字都变成0,变成12000000;然后在从2后开始找不重复数,00重复,变成01;所以结果是12010101。这里需要注意:如果变化后又进位的情况,还需要重新处理一遍,比如199,第一遍处理后变成了200,200还是有重复,则需要重新处理。

# -*- coding: utf-8 -*-
"""
题目:输入一个数A,找到大于A的一个最小数B,且B中不存在连续相当的两个数字。
比如输入99,那B应该是101 因为100有两个连续相当的0
基本思路:最坏的办法 加1一直加1 直到找到有不重复的数为止
优化的思路 如果输入是1099 加1后变成1100,那么他下一个不重复的数如果一直加1效率就会比较低,这是可以优化的点
这道题要是作为面试提的话,要跟面试官确认好,数A的范围,比如是否有小数
是否有负数,等等。在这里我们把题确定为正数
"""

def get_data(num):
    """
    获取num个10相乘的数字,为了让重复的数字加1,比如num=4 则返回10000
    args:需要0的个数
    """
    data = 1
    while num > 0:
        data = data * 10
        num = num -1
    return data

def get_tail(num, data):
    """
    获取data的后面num个数,比如data=1345 num=3 则返回345
    args:num需要取后几位 data数字
    """
    list_data = []
    #获取到num位0的数字
    head = get_data(num)
    #用抹除的方式获取后几位
    need_data = data % head
    return need_data

def judge(data):
    """
    判断data中是否有连续重复数字
    args:data数字
    """

    i = 1
    while i < len(data):  
        #判断是否有两个数字相等
        if string_num[i-1] == string_num[i]:

            return True
        i = i + 1
    return False

if __name__ == "__main__":  
    #输入的数字 
    num = 1099
    num = num + 1
    #数字转字符串,为了判断是否有相等的数字
    string_num = str(num)   


    i = 1
    flag = 0 
    while True:  
        if(judge(string_num)==False):
            break
        while i < len(string_num):  
            #判断是否有两个数字相等
            if string_num[i-1] == string_num[i]:
                #如果有重复的数字,则把重复的两个数,中小的一位数字加1,然后在把后面的位置0
                new_len = len(string_num) - i - 1
                num = num + get_data(new_len)
                tail = get_tail(new_len, num)
                #置0的办法是用num减掉后面的几位数
                num = num - tail
                string_num = str(num)

                flag = 1
            #置0后 在找后面几位去找不重复的最小数
            i = i + 1 
        #如果flag=0 证明没有重复的 证明找到了不重复的数字,则退出 
        if flag == 0:
            num = num + 1
            string_num = str(num)

        #如果flag=0 并且运算到了最后一位
        if flag == 1 and i >=len(string_num):
            #在判断下是否有重复,如果有重新算,没有则停止
            if(judge(string_num)):
                i = 0
                flag = 0 
                continue
            else:
                break

    print  string_num  
1099输出是:1201 ; 99 输出是:101; 9 输出是:10 ;1098 输出是:1201

原文发布于微信公众号 - 玄魂工作室(xuanhun521)

原文发表时间:2018-08-27

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏zaking's

用js来实现那些数据结构03(数组篇03-排序及多维数组)

  终于,这是有关于数组的最后一篇,下一篇会真真切切给大家带来数据结构在js中的实现方式。那么这篇文章还是得啰嗦一下数组的相关知识,因为数组真的太重要了!不要怀...

38050
来自专栏糊一笑

非比较排序算法总结与实现

之前一篇文章介绍了几种常用的比较排序算法,下面介绍的是几种非比较排序算法。 非比较排序算法内部引用的都是计数排序,当然你也可以将计数排序换为其他的比较排序算法。...

32780
来自专栏数据小魔方

左手用R右手Python系列7——排序

排序可能是日常数据清洗过程中比较高频的应用了,今天这一篇给大家介绍R语言和Python中最为常见的排序函数应用。 R语言: sort order rank ar...

30340
来自专栏老九学堂

常用排序算法总结

一种是比较排序,时间复杂度O(nlogn) ~ O(n^2),主要有:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序等。

16330
来自专栏chenjx85的技术专栏

leetcode-908-最小差值 I

给定一个整数数组 A,对于每个整数 A[i],我们可以选择任意 x 满足 -K <= x <= K,并将 x 加到 A[i] 中。

19620
来自专栏钱塘大数据

【推荐收藏】十大经典排序算法(动图演示)

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也...

9720
来自专栏轮子工厂

快速搞定8大排序算法

11220
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第七章 归并排序的时间复杂度分析

上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度中经常看到的一...

387110
来自专栏顶级程序员

各大排序算法性能比较及演示实例

所谓排序,即将原来无序的一个序列重新排列成有序的序列。 排序方法中涉及到稳定性,所谓稳定性,是指待排序的序列中有两个或两个以上相同的项,在排序前和排序后看这些相...

371100
来自专栏cmazxiaoma的架构师之路

一个Java小白通向数据结构算法之旅(6) - 插入排序

19550

扫码关注云+社区

领取腾讯云代金券