LeetCode 38. Count and Say：外觀數列生成演算法

問題描述

外觀數列從 "1" 開始，每一項描述前一項：1 → 11 → 21 → 1211 → 111221...。給定 n，生成第 n 項字符串。

核心演算法

迭代構建：對當前字符串掃描，統計連續相同字符個數，輸出 個數+字符 形成下一項：

public String countAndSay(int n) {
    String str = "1";
    for (int i = 1; i < n; i++) {
        int count = 1;
        StringBuilder sb = new StringBuilder();
        for (int j = 1; j < str.length(); j++) {
            if (str.charAt(j) == str.charAt(j-1)) count++;
            else { sb.append(count).append(str.charAt(j-1)); count = 1; }
        }
        sb.append(count).append(str.charAt(str.length()-1));
        str = sb.toString();
    }
    return str;
}

關鍵點分析

• 單次掃描：線性遍歷字符串，O(len) 時間
• StringBuilder：高效字符串構建，避免頻繁拷貝
• 邊界處理：循環結束後需處理最後一組字符
• 空間複雜度：僅需存儲當前與下一項字符串

範例演示

n=5 過程：
"1" → "11" → "21" → "1211" → "111221"

本題考察字符串處理與模擬能力，代碼簡潔高效。