一道趣题的Java解法

发表于:2010-7-23 10:32

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:未知    来源:51Testing软件测试网采编

#
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步开始。

  这个算法首先需要编写一个方法用于将给定数最右侧第一对重复的数找出,并且加1,最后得到一个新的数。如果这个数是不重复的数,那么直接返回0。代码如下:

21/212>
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号