題目來源：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)，如果大家有更好的解法，歡迎交流一下！ ^_^

• 如果你用 C＃ 可以利用我的 測試程式 來驗證
• 如果你用 Java or Python or C++ 可上 LeetCode Online Judge 驗證