寻找比任意正整数大的最小“不重复数”
给定任意一个正整数,求比这个数大且最小的“不重复数”,“不重复数”的含义是相邻两位不相同,例如1101是重复数,而1201是不重复数。(题目来源:July博客)
思路:
1.得到比该正整数大一的数n;
2.将n转换为字符串,从最高位向下比较,如碰到连续的两位数相同,则将首位至低位所组成的数加1,后面各位置0,得到新的数值字符串(如18823,有连续的8,则新串为18900);
3.重复执行操作2,直到不是重复数为止。
需要考虑的地方:
1.进位问题,如99801。如果使用字符串可能会有位数变化的问题,此处应使用数字操作。
2.可能包含多组重复的数,如1223455。应取最高一组。
3.C语言中对数字与字符串转化的处理可能较复杂,下面的代码使用Python来实现,如果有时间会增加C的版本。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# -*- coding: utf-8 -*- def get_min_norepeat_num(num): num = str(num + 1) while True: length = len(num) for i in range(0, length - 1): if num[i] == num[i + 1]: num = str((int(num[0: i + 2]) + 1) * (10 ** (length - i - 2))) break else: return int(num) if __name__ == "__main__": nums = [12343, 12345, 12287, 12288, 199, 1992, 19923, 8989899, 99123] print [get_min_norepeat_num(num) for num in nums] |
Python实现的代码不长,只有十几行,测试了我能想到的一些边界条件,结果如下:
[12345, 12346, 12301, 12301, 201, 2010, 20101, 9010101, 101010]
上述代码需要注意的是else和for同级,表示如果for循环中没有被执行break(即没有找到重复数)时,执行else中的语句。这个语法糖要比走完一边循环,再去if一下是否是走完的,省去几行代码,看起来更加简洁。
本文内容遵从CC3.0版权协议,转载请注明:转自Pythoner
本文链接地址:寻找比任意正整数大的最小“不重复数”
暂无评论