iT邦幫忙

DAY 19
1

連續30天,挑戰演算法系列 第 19

[Day19] 30 天挑戰演算法 - 數數字

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


上一篇
[Day18] 30 天挑戰演算法 - 尋找最大(乘)積
下一篇
[Day20] 30 天挑戰演算法 - 迴文數字
系列文
連續30天,挑戰演算法30

尚未有邦友留言

立即登入留言