随笔 - 312, 文章 - 14, 评论 - 1393, 引用 - 0
数据加载中……

有道难题2009复赛题解答(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。代码如下:

    // sb表示指定的数,以StringBuilder对象表示
    public static long getNextNum(StringBuilder sb)
    {
        String result 
= "";
        
char c = 'a'// c表示数字中待检测位中高位的字符
        int i = 0;
        
for (i = sb.length() - 1; i >= 0; i--)
        {
            
// 如果相邻的两个数字不相同,那么将当前字符保存在c中
            if (sb.charAt(i) != c)
            {
                c 
= sb.charAt(i);
            }
            
// 如果相邻的两个数字相同,那进行下一步地处理
            else
            {
                
// 将相同的两个数字组成的数加1
                long n = Long.parseLong(String.valueOf(c) + String.valueOf(c)) + 1;
                
// 先将这两个相同的数字的位置的值设为0,以便进行相加

                
// 计算数字后面要补的0的数,如21443中重复的数字是44,加1后是45,那么首先将44设成00,
                
// 也就是21003,然后将45后面补0,就是450,最后用21003和450相加,就变成了21453
                int m = sb.length() - i - 2;
                sb.setCharAt(i, 
'0');
                sb.setCharAt(i 
+ 1'0');
                
for (int k = 0; k < m; k++)
                    n 
*= 10;
                
long num = Long.parseLong(sb.toString()) + n;
                sb 
= new StringBuilder(String.valueOf(num));
               
// 开始将重复数后面的数变成最小的
                m = i + 2;
                
for (int x = m; x < sb.length(); x++)
                {
                    
for (int y = 0; y < 10; y++)
                    {
                        
                        
if (sb.charAt(x - 1!= (y + 48))
                        {
                            sb.setCharAt(x, (
char) (y + 48));
                            
break;
                        }
                    }
                }

                
return Long.parseLong(sb.toString());
            }
        }
        
return 0;
    }
    要注意的是,虽然把每一对重复的数都变成了不重复的,但仍然不是最小的数,需要将当前重复数后面的数变成最小的,例如,99123将99变成不重复的数,也就是100,原来的数变成了100123,但100123还需要继续变成100101,再查找重复数,把到了00,再变成101101,然后再变成101010,就ok了。
    最后调用getNextNum方法来返回最终结果,代码如下:
    public static long getMinNoRepetitionNum(long num)
    {
        String s 
= String.valueOf(num + 1);

        
long n = 0;
        
long result = 0;
        
while ((n = getNextNum(new StringBuilder(s))) != 0)
        {
            s 
= String.valueOf(n);
            result 
= n;
        }
        
if (result == 0)
            
return num + 1;
        
else
            
return result;
    }

    现在可以使用下面的代码来测试一下:
System.out.println(getMinNoRepetitionNum(1999));




Android开发完全讲义(第2版)(本书版权已输出到台湾)

http://product.dangdang.com/product.aspx?product_id=22741502



Android高薪之路:Android程序员面试宝典 http://book.360buy.com/10970314.html


新浪微博:http://t.sina.com.cn/androidguy   昵称:李宁_Lining

posted on 2010-05-11 16:23 银河使者 阅读(3554) 评论(21)  编辑  收藏 所属分类: javaalgorithm 原创

评论

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

算法错了,20097怎么办?
按你算法是20198
实际应该是20101
2010-05-12 09:32 | zack

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数1  回复  更多评论   

@zack
少加了些代码,现在ok了。
2010-05-12 09:53 | 银河使者

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

这个题如果给我做的话我不会从左往右检查,相反我会从右往左检查
1.将数字+1
2. 从左往右(从高位到低位)判断是否有重复数字,没有的话进入4检查到第一组重复数字进入3
2. 将两个重复数字的以前的(包括重复数字取出来)并且+1,将结果*(10^n) + 01序列
3. 输出结果
例 21001224321
1.加1 = 21001224322
2. 是重复数字进入3
3. 2100 *10^7 + 1* 10^7 + 1* 10^5 + 1* 10^3 + 1* 10^1 =
21010101010
4. 输出 21010101010
2010-05-12 18:24 | Zhjiang

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

@Zhjiang
你写的算术公式真的能算出这21010101010个数???

我都不知道你怎么算出来的。
2010-05-13 14:29 | Lancelot

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

@Lancelot
试试不用知道了,计算机会告诉你的。
2010-05-13 15:29 | 银河使者

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

@银河使者
你知道10^7等于多少吗???
你把
2100 *10^7 + 1* 10^7 + 1* 10^5 + 1* 10^3 + 1* 10^1
算出来,你能等于21010101010吗???

拜托别说不负责任的话,只会让自己献丑。
2010-05-13 16:33 | Lancelot

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

@银河使者
而且这个算式也与他上面写的:
2. 将两个重复数字的以前的(包括重复数字取出来)并且+1,将结果*(10^n) + 01序列
这句不符,明显算式里没有出现括号,那到底是先乘再取余(结果:21003)还是先取余再乘(结果:27348)?

拜托你帮我算算是多少。
在线等,谢谢。
2010-05-13 16:41 | Lancelot

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

额 我想你们理解错我的意思了

10^n 我表示的是10的n次方

不好意思啊
2010-05-13 17:24 | Zhjiang

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

各位如果要有更好的算法,把代码贴出来,不要光说一些理论。
2010-05-13 18:28 | 银河使者

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

什么都不说 粗略写的java 代码 大家研究下

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Test {

/**
* @param args
*/
public static void main(String[] args)
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String numStr =null;
long num = -1;
long tempnum = 0;
long bitvalue = -1;
int numbit1 = -1;
int numbit2 = -1;
int flag = -1;
int size = 0;
boolean isrepeater = false;

try
{
numStr = br.readLine();
num = Long.parseLong(numStr);

} catch (NumberFormatException e)
{
return;
} catch (IOException e)
{
return;
}
//只解析自然数
if(num <= -1)
return;

size = (int)Math.log10(num);

//1. 先将数字+1
num ++;
tempnum = num;

//2. 判断是否为重复数字
if(tempnum / Math.pow(10, size) >= 1)
size ++;

bitvalue = (long)Math.pow(10, size - 1);

for(flag = size - 1; flag >= 1; flag --){

numbit1 = (int)(tempnum / bitvalue);

tempnum = tempnum % bitvalue;

bitvalue = (long)Math.pow(10, flag - 1);
numbit2 = (int)(tempnum / bitvalue);

if(numbit1 == numbit2){
isrepeater = true;
break;
}
}
//2. 如果是重复数
if(isrepeater){
flag --;
num -= tempnum % Math.pow(10, flag);

//以下三行是由于考虑的遗漏,解决了以99开头数字(例 9998)的问题
//按照我以前的算法99123 得到的结果是100010
num += (long)Math.pow(10, flag);
if(Math.log10(num) >= size)
num += (long)Math.pow(10, flag);

flag -= 2;
for(; flag >= 0; flag -=2){
num += (long)Math.pow(10, flag);
}
}

//4.输出结果
System.out.println(num);

}

}
2010-05-13 18:30 | Zhjiang

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

我也只是刚刚写的,遗漏之处和我说一下,谢谢了!
在我看来这个题目纯粹是一个计算的问题,不需要过多的循环的,当然 仅争对本题,另外解释一点,我上面的代码没有把负数考虑进去,只要稍微改进一下就可以把负数也包括进去,当然这点还需要商榷,我只是一个猜想,因为准备写代码的时候已经下班了,不想在公司继续熬了,所以代码写得很粗糙,没有优化,另外也没有过多检查BUG和遗漏的情况,往谅解下!
2010-05-13 18:34 | Zhjiang

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

@Lancelot
哈哈,上机测一下程序不就知道了。你不知道,可计算机知道哦。
2010-05-14 08:23 | 银河使者

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

看到你在Csdn上写的,看来不止是我觉得扩展01序列是一个不错的方法!~~
很庆幸
2010-05-14 09:10 | Zhjiang

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

@银河使者
拜托你告诉我你用的什么计算机???
你的计算机会把10^7算成3还是10000000???
搞笑


我都懒的理你了,这是最后一次回复你。
2010-05-17 17:23 | Lancelot

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

@Lancelot
什么意思,我的算法没10^7,估计是你看到别人的回复算到我头上了吧。如果认为哪个具体的数无法通过算法,请指出,谢谢。

对了,忘了说了,上星期我刚从某个外星种族那得到一台先进的计算机,好象10^7既不等于3,也不等于10000000,等于^&%$&*^&*。 :)
2010-05-17 19:33 | 银河使者

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

Zhjiang的算法思路不错, 不过还是有一些缺陷的.对于中间含有多个9的数字,处理不对。如99,1990,999...
2010-05-17 23:42 | 晓风待语

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

本人blog中有对该题的详细解法,希望给予意见
2010-05-17 23:45 | 晓风待语

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数[未登录]  回复  更多评论   

确实觉得从左至右是合理的,
比如说一个数字,567899882201
首先+1,然后执行如下步骤:
步骤一:从左至右查找第一对重复的是99,操作:(567899 + 1)*10^6 =
567900 000000
其实这样的操作会使任何一个数字都带有0到n个0。如55 的话
(55+1)*10^0 ,78662为:(7866+1)*10^1;
步骤二:从左至右查找第一对重复的数字,如果重复的数字为0,即为00,执
行步骤三,否则执行步骤一;
步骤三:从左至右查找连续的两个数字,此时连续的两个数字只有可能是00了,
如果有两个连续的0,这时按照00+1,如:(567900+1)*10^6;

只是写了一个大致的实现思路,这个只是针对>=0的数字,^的意思是Math.pow(10, n);只是一个表现形式,大家也不用太纠结
2010-06-25 10:56 | lj

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数[未登录]  回复  更多评论   

假如上个月(5月)总销售额是39980,而本月(6月)总销售额是59863,问:本月销售同比上月销售增长多少百分比,反比增长多少百分比?
2010-07-03 13:35 | 小李

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

看了一下大伙的讨论 觉得蛮有意思
转走了
http://www.wangdacuo.com/archives/solve-question-use-java
2010-07-13 19:26 | 特立独行

# re: 有道难题2009复赛题解答(Java版):求大于给定数的最小不重复数  回复  更多评论   

我感觉这题好简单啊……
1.从高到低位扫描,遇到与高一位数相同的数,就在该位置上加1,把该为后的全置0,
2.重复1直到你扫描到个位且它与十位不同
就搞定了……
2011-04-28 22:41 | 乔磊

只有注册用户登录后才能发表评论。


网站导航: