您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

LeetCode 38 Count and Say：遞歸生成「讀法」序列的兩種 C++ 實現

編輯：關於C++

題目理解

「報數序列」按規則遞增：

1
11      (1 個 1)
21      (2 個 1)
1211    (1 個 2, 1 個 1)
111221  (1 個 1, 1 個 2, 2 個 1)
...

給定 n（1 ≤ n ≤ 30），返回第 n 項字符串。本質是對上一項進行「行程長度編碼」（RLE）。

迭代法（推薦：清晰、無棧溢出風險）

class Solution {
public:
    string countAndSay(int n) {
        string cur = "1";
        for (int i = 1; i < n; ++i) {
            cur = next(cur);
        }
        return cur;
    }
    
private:
    string next(const string& s) {
        string res;
        int cnt = 1;
        for (int i = 1; i <= s.size(); ++i) {
            if (i < s.size() && s[i] == s[i-1]) {
                ++cnt;
            } else {
                res += to_string(cnt);
                res += s[i-1];
                cnt = 1;
            }
        }
        return res;
    }
};

遞歸法（直觀但深度受限）

class Solution {
public:
    string countAndSay(int n) {
        if (n == 1) return "1";
        string prev = countAndSay(n - 1);
        string res;
        int i = 0;
        while (i < prev.size()) {
            char c = prev[i];
            int j = i;
            while (j < prev.size() && prev[j] == c) ++j;
            res += to_string(j - i);
            res += c;
            i = j;
        }
        return res;
    }
};

關鍵點對比

方面	迭代法	遞歸法
空間複雜度	O(1) 額外空間（不計輸出）	O(n) 調用棧
字符串拼接	單次遍歷構建結果	同
邊界處理	循環條件 `i <= size()` 統一處理最後一組	雙指針 `i, j` 更直觀
性能	略快（無函數調用開銷）	n≤30 可接受