最近看了有道出的几个复赛题,觉得很好玩,现给出Java版的答案。先看看提干部分
如果一个数字十进制表达时,不存在连续两位数字相等,则称之为“不重复数”。例如,105,1234和12121都是“不重复数”,而11,100和 1225不算。给定一个long类型数字A,返回大于A的最小“不重复数”。下面是几个测试用例,我又加了几个
Examples:
0) 54
returns: 56
大于54的最小数字是55,但55不是“不重复数”。下一个数字是56,它满足条件。
1) 10
returns: 12
2) 9
returns: 10
3) 98
returns: 101
99和100都不是“不重复数”, 101是。
4) 21099
returns: 21201
5) 99123
returns: 101010
6) 1134567
returns: 1201010
ok,现在看看解题思路,其实这个题单纯从题本身上看并不复杂,主要是效率问题。估计不会有人一个数一个数地循环查找吧,那样如果给定的long数很大时,可能会进行成千上万次的循环,会很慢很慢。技巧还是有的,现在来看看怎么快速搞定这个问题。
首先来拿一个例子看,就选 21099了。
这个数低两位(99)是重复的。既然要找比21099大的最新不重复数,就需要从这两位开始递增,但不是逐1的递增。比21099大的数是21100,这个数也是个重复的数,有两对重复的(11和00)。从右侧开始处理它们。先处理00。我们现在要做的就是把00变成不重复的,很简单,就成01就可以了。现在21100就变成了21101,这个数还是有两个重复数(11)。现在处理11,把11变成12就不重复的,那么现在21101就变成了21201,ok,现在就得到了最终结果。我们看看,只结果了两步,是很快地,因此,我们可以总结一下算法,步骤如下:
1. 将给定的long数加1。
2. 从这个数开始检测是否为重复数,如果不是,ok,这个数就是最终结果。如果是,那么从数的右侧开始找第1对重复的数,然后将其加1,得到一个新的数。
3. 然后用这个数再从第2步开始。
这个算法首先需要编写一个方法用于将给定数最右侧第一对重复的数找出,并且加1,最后得到一个新的数。如果这个数是不重复的数,那么直接返回0。代码如下: