Count and Say（外觀數列）生成算法詳解

題目：外觀數列定義：
1
11 (一個 1)
21 (兩個 1)
1211 (一個 2，一個 1)
111221 (一個 1，一個 2，兩個 1)
...
給定 n，返回第 n 項字符串。

核心邏輯：讀取上一項生成下一項

對字符串 s，從左到右掃描，統計連續相同字符個數 cnt，輸出 cnt + char。
例："1211" → 1個1, 1個2, 2個1 → "111221"。

迭代實現 (C++ / Python / Java)

// C++
class Solution {
public:
    string countAndSay(int n) {
        string cur = "1";
        for (int i = 2; i <= n; ++i) {
            string nxt;
            for (int j = 0; j < cur.size(); ) {
                int k = j;
                while (k < cur.size() && cur[k] == cur[j]) ++k;
                nxt += to_string(k - j);
                nxt += cur[j];
                j = k;
            }
            cur = move(nxt);
        }
        return cur;
    }
};

# Python
class Solution:
    def countAndSay(self, n: int) -> str:
        cur = "1"
        for _ in range(n - 1):
            nxt = []
            i = 0
            while i < len(cur):
                j = i
                while j < len(cur) and cur[j] == cur[i]:
                    j += 1
                nxt.append(str(j - i))
                nxt.append(cur[i])
                i = j
            cur = "".join(nxt)
        return cur

// Java
class Solution {
    public String countAndSay(int n) {
        String cur = "1";
        for (int i = 2; i <= n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < cur.length(); ) {
                int k = j;
                while (k < cur.length() && cur.charAt(k) == cur.charAt(j)) k++;
                sb.append(k - j).append(cur.charAt(j));
                j = k;
            }
            cur = sb.toString();
        }
        return cur;
    }
}

關鍵觀察

• 長度增長：近似指數增長（康威常數 ≈ 1.30357），n=30 時長度 ~44 萬，記憶體可承受。
• 數字只含 1,2,3：證明不會出現 ≥4 的連續相同字符。
• StringBuilder / list+join：避免字符串頻繁拷貝，關鍵優化。

複雜度分析

總結

Count and Say 是字符串模式生成的基礎題。核心邏輯簡單：掃描統計連續字符，輸出計數+字符。面試中關鍵在於代碼簡潔正確、邊界處理（n=1 返回 "1"）、效能優化（用 StringBuilder）。此題常作為熱身題，考察基本編碼能力與對字符串操作的熟練度。