題目來源:Count and Say
問題:
這個「數數字」的數列的格式為: 1, 11, 21, 1211, 111221, ... 其中
1 要念 一個1,所以是 11
11 要念 兩個1,所以是 21
21 要念 一個2和一個1,所以是 1211
給一個數字 n,請針對這個數數字格式產生第 n 個數字
註:這數列回傳時要以字串的格式表示
例子
題目給 1, 則答案就是 1
題目給 2, 則答案就是 11
題目給 3, 則答案就是 21
題目給 4, 則答案就是 1211
以此類推~~
想法
如果你有看懂這個題目,這題目其實滿簡單的!就真的事數數字而已!但是如果你沒看懂,可能想破頭也做不出來。一開始我的想法是根據那個「數數字」數列去猜測下一個會是什麼?想了許久都想不出來。後來發現,原來題目已經告訴你下一個數字是什麼了,根本不用自己去推敲他的 下一個數字邏輯。
他的下一個數字就是看前面的數字是什麼,把重複的數字前面加個單位數字就是答案了。也就是說,假設目前的數字是 333211555 ,那這個數字可以讀成「三個3、一個2、兩個1、三個5」,因此下一個數字必定是「**3312213**5」。
夠簡單了吧!所以一開始我就說,如果有看懂題目,這題真的很簡單。當一個數字進來,只要去計算相同的數字,前面在加個 單位數字 就是答案了。 (突然覺得這個好像是以前學過的某種壓縮的演算法喔~)
只是這樣做的一個缺點就是時間複雜度很高,因為每次都要從頭開始往下算!
不過沒關係!我們先就上面的分析得到下面這個程式碼:
取得下一個數列
private string calculateNextSequence(string inputString)
{
StringBuilder builder = new StringBuilder();
char number = inputString[0];
int count = 1;
for (int i = 1; i < inputString.Count(); i++)
{
// 計算目前的數字是否與前一個相同,若相同就+1
if (number == inputString[i])
count += 1;
else // 當數字已經不相同時
{
// 數字的單位量
builder.Append(count.ToString());
// 數字本身
builder.Append(number);
// 新數字重新在計算
count = 1;
number = inputString[i];
}
}
// 將 count 加入
builder.Append(count.ToString());
// 將 數字 加入
builder.Append(number);
return builder.ToString();
}
有了取得下一個序列的程式之後,我們的主程式就更加容易了,如下:
數數字
public string count_and_say(int inputNumber)
{
string result = "1";
for(int i=0; i < inputNumber-1; i++) // 因為 1 不用計算,所以算的次數要減一
result = calculateNextSequence(result);
return result;
}
說真的,我這題的解法是有一點暴力啦!效能不算是很好 O(N^2),如果大家有更好的解法,歡迎交流一下! ^_^