玄魂工作室秘书 [玄魂工作室]
昨天发的算法有一处情况没考虑到, 比如加一后有进位, 导致又出现重复数字的情况, 修正后今天重新发一次.
比如输入 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 输出是: 12 ;1098 输出是: 1201
来源: https://juejin.im/post/5b839fbaf265da436a076576