最近看了有道出的幾個(gè)復(fù)賽題，覺得很好玩，現(xiàn)給出Java版的答案。先看看提干部分
如果一個(gè)數(shù)字十進(jìn)制表達(dá)時(shí)，不存在連續(xù)兩位數(shù)字相等，則稱之為“不重復(fù)數(shù)”。例如，105，1234和12121都是“不重復(fù)數(shù)”，而11，100和 1225不算。給定一個(gè)long類型數(shù)字A，返回大于A的最小“不重復(fù)數(shù)”。下面是幾個(gè)測(cè)試用例，我又加了幾個(gè)
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
5) 99123
returns： 101010
6) 1134567
returns： 1201010
ok，現(xiàn)在看看解題思路，其實(shí)這個(gè)題單純從題本身上看并不復(fù)雜，主要是效率問題。估計(jì)不會(huì)有人一個(gè)數(shù)一個(gè)數(shù)地循環(huán)查找吧，那樣如果給定的long數(shù)很大時(shí)，可能會(huì)進(jìn)行成千上萬次的循環(huán)，會(huì)很慢很慢。技巧還是有的，現(xiàn)在來看看怎么快速搞定這個(gè)問題。
首先來拿一個(gè)例子看，就選 21099了。
這個(gè)數(shù)低兩位(99)是重復(fù)的。既然要找比21099大的最新不重復(fù)數(shù)，就需要從這兩位開始遞增，但不是逐1的遞增。比21099大的數(shù)是 21100，這個(gè)數(shù)也是個(gè)重復(fù)的數(shù)，有兩對(duì)重復(fù)的(11和00)。從右側(cè)開始處理它們。先處理00。我們現(xiàn)在要做的就是把00變成不重復(fù)的，很簡單，就成 01就可以了。現(xiàn)在21100就變成了21101，這個(gè)數(shù)還是有兩個(gè)重復(fù)數(shù)(11)。現(xiàn)在處理11，把11變成12就不重復(fù)的，那么現(xiàn)在21101就變成了21201，ok，現(xiàn)在就得到了最終結(jié)果。我們看看，只結(jié)果了兩步，是很快地，因此，我們可以總結(jié)一下算法，步驟如下：
1. 將給定的long數(shù)加1。
2. 從這個(gè)數(shù)開始檢測(cè)是否為重復(fù)數(shù)，如果不是，ok，這個(gè)數(shù)就是最終結(jié)果。如果是，那么從數(shù)的右側(cè)開始找第1對(duì)重復(fù)的數(shù)，然后將其加1，得到一個(gè)新的數(shù)。
3. 然后用這個(gè)數(shù)再從第2步開始。
這個(gè)算法首先需要編寫一個(gè)方法用于將給定數(shù)最右側(cè)第一對(duì)重復(fù)的數(shù)找出，并且加1，最后得到一個(gè)新的數(shù)。如果這個(gè)數(shù)是不重復(fù)的數(shù)，那么直接返回0。代碼如下：
// sb表示指定的數(shù)，以StringBuilder對(duì)象表示
public static long getNextNum(StringBuilder sb)
{
String result = ”“;
char c = ’a‘; // c表示數(shù)字中待檢測(cè)位中高位的字符
int i = 0;
for (i = sb.length() - 1; i 》= 0; i–)
{
// 如果相鄰的兩個(gè)數(shù)字不相同，那么將當(dāng)前字符保存在c中
if (sb.charAt(i) != c)
{
c = sb.charAt(i);
}
// 如果相鄰的兩個(gè)數(shù)字相同，那進(jìn)行下一步地處理
else
{
// 將相同的兩個(gè)數(shù)字組成的數(shù)加1
long n = Long.parseLong(String.valueOf(c) + String.valueOf(c)) + 1;
// 先將這兩個(gè)相同的數(shù)字的位置的值設(shè)為0，以便進(jìn)行相加
// 計(jì)算數(shù)字后面要補(bǔ)的0的數(shù)，如21443中重復(fù)的數(shù)字是44，加1后是45，那么首先將44設(shè)成00，
// 也就是21003，然后將45后面補(bǔ)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));
// 開始將重復(fù)數(shù)后面的數(shù)變成最小的
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;
}
要注意的是，雖然把每一對(duì)重復(fù)的數(shù)都變成了不重復(fù)的，但仍然不是最小的數(shù)，需要將當(dāng)前重復(fù)數(shù)后面的數(shù)變成最小的，例如，99123將99變成不重復(fù)的數(shù)，也就是100，原來的數(shù)變成了100123，但100123還需要繼續(xù)變成100101，再查找重復(fù)數(shù)，把到了00，再變成101101，然后再變成101010，就ok了。
最后調(diào)用getNextNum方法來返回最終結(jié)果，代碼如下：
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;
}
現(xiàn)在可以使用下面的代碼來測(cè)試一下：
System.out.println(getMinNoRepetitionNum(1999));