设为首页 加入收藏

TOP

一个趣题的Java解法
2014-11-16 14:40:36 来源: 作者: 【 】 浏览:19
Tags:一个 Java 解法

  最近看了有道出的几个复赛题,觉得很好玩,现给出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步开始。


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇Java数组之初始化及实例代码 下一篇怎样用Jvm处理Java数组

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: