周末在線做網(wǎng)易有道難題的挑戰(zhàn)賽，三個(gè)題目分值分別為350，500，1000分，第一道題理解并寫出來，但被別人cha掉；
第二題理解題意，算法模模糊糊，不知道怎么寫。最后時(shí)間來不及寫完。 第三題沒來得及看。
第一題被cha的概率很高，說明大家對(duì)算法都存在同樣的問題，看著差不多，其實(shí)有很多邏輯的混亂。至少我的第一題后來發(fā)現(xiàn)的確存在思路上的問題。 教訓(xùn)：寫代碼之前算法一定要想清楚，邏輯完備很重要。
看了AcRush的算法，不得不佩服。另一個(gè)感受就是：當(dāng)數(shù)據(jù)或者數(shù)據(jù)量發(fā)生質(zhì)變時(shí)，特別注意一下兩個(gè)問題：
１、暴力還能否解決問題
２、很多時(shí)候都有更好的算法來解決。
下面是350分的題目和根據(jù)AcRush的代碼改寫的Java版。
網(wǎng)易有道難題TopCoder
在線挑戰(zhàn)賽 350
分題
Problem Statement
如果一個(gè)數(shù)字十進(jìn)制表達(dá)時(shí)，不存在連續(xù)兩位相同，則稱之為“不重復(fù)數(shù)”。例如，105
、1234
和12121
都是“不重復(fù)數(shù)”，而11
、100
和1225
不是。
給定一個(gè)long
類型數(shù)字A
，返回大于A
的最小“不重復(fù)數(shù)”。
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]
，注意是閉區(qū)間。
Examples
0)
54
Returns: 56
大于54
的最小數(shù)字是55
，但55
不是“不重復(fù)數(shù)”。下一個(gè)數(shù)字是56
，它滿足條件。
1)
10
Returns: 12
2)
9
Returns: 10
3)
98
Returns: 101
99
和100
都不是“不重復(fù)數(shù)”，但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;
}
}
希望對(duì)大家有幫助。算法的本質(zhì)在于效率。