Just for i0'

Love i0

网易暨Topcoder之有道难题,解题和一点体会

周末在线做网易有道难题的挑战赛,三个题目分值分别为350,500,1000分,第一道题理解并写出来,但被别人cha掉;

第二题理解题意,算法模模糊糊,不知道怎么写。最后时间来不及写完。 第三题没来得及看。

 

第一题被cha的概率很高,说明大家对算法都存在同样的问题,看着差不多,其实有很多逻辑的混乱。至少我的第一题后来发现的确存在思路上的问题。 教训:写代码之前算法一定要想清楚,逻辑完备很重要。

 

看了AcRush的算法,不得不佩服。另一个感受就是:当数据或者数据量发生质变时,特别注意一下两个问题:

1、暴力还能否解决问题 

2、很多时候都有更好的算法来解决。

 

下面是350分的题目和根据AcRush的代码改写的Java版。

 

网易有道难题TopCoder 在线挑战赛 350 分题

Problem Statement   

如果一个数字十进制表达时,不存在连续两位相同,则称之为“不重复数”。例如,105123412121 都是“不重复数”,而111001225 不是。

给定一个long 类型数字A ,返回大于A 的最小“不重复数”。

Definition   

Class:UnrepeatingNumbers

Method:getNext

Parameters: long

Returns:long

Method signature: long getNext(long A)

(be sure your method is public)

Constraints-

A 取值范围是[0, 10^17] ,注意是闭区间。

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

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

 

 一种解法:

import java.util.Scanner;

public class UnrepeatingNumbers {
    
    
public static void main(String[] args) {
     
        UnrepeatingNumbers un
=new UnrepeatingNumbers();
        Scanner cin
=new Scanner(System.in);
        
while(true)
        {
         System.out.println(un.getNext(cin.nextLong()));
        }
    }    
    
public  long checkAndIterate (long n)
    {
        StringBuffer s
=new StringBuffer(String.valueOf(n));    
        
for(int i=0; i+1<s.length();i++)
        {
            
if(s.charAt(i)==s.charAt(i+1))
            {
                  
long p10=1;
                  
for(int j=i+2; j<s.length(); j++)                  
                  {    
                      s.setCharAt(j,
'0');    
                      p10
*=10;    
                  }                     
                  n
=Long.parseLong(s.toString())+p10;    
                 
return n;
            }
        }
         
return -1;
    }
    
long getNext(long A)
    {
        A
++;
        
long     temp=1;
        
while(temp>0)
            { 
            temp
=checkAndIterate(A);
            
if(temp>0) A=temp;
            }         
        
return A;
    }

}


希望对大家有帮助。算法的本质在于效率。

posted on 2009-06-24 17:21 for_I0 阅读(920) 评论(1)  编辑 收藏 引用 所属分类: JavaACM、Topcoder 算法

Feedback

# re: 网易暨Topcoder之有道难题,解题和一点体会 2013-03-19 12:33 黄建

估计与跟下40最接近的两个整数是多少  回复  更多评论   



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理