1. 題目鏈接

LeetCode 38. 外觀數列

---

2. 題目描述

給定一個正整數 n，生成外觀數列的第 n 項。外觀數列的定義如下：

• 第 1 項為 "1"。
• 第 n 項是對第 n-1 項的描述。例如，第 2 項描述第 1 項（"1"）為 "11"（即“1個1”），第 3 項描述第 2 項（"11"）為 "21"（即“2個1”），依次類推。

示例：

• 輸入：n = 4 → 輸出："1211"
• 輸入：n = 5 → 輸出："111221"

---

3. 示例分析

1. 基礎案例：

   • n=1 → "1"
   • n=2 → "11"
   • n=3 → "21"
   • n=4 → "1211"（描述 "21" 為“1個2，1個1”）
   • n=5 → "111221"（描述 "1211" 為“1個1，1個2，2個1”）

2. 復雜案例：

   • n=6 → "312211"（描述 "111221" 為“3個1，2個2，1個1”）

---

4. 算法思路

核心思想：迭代生成 + 雙指針統計

1. 初始化：從第 1 項 "1" 開始迭代。
2. 迭代生成：對當前項從左到右掃描，統計連續相同字符的數量。
3. 雙指針統計：
   • left 指針標記當前字符的起始位置。
   • right 指針向右移動，直到遇到不同字符。
   • 統計長度 right - left，拼接成新字符串的 "數量+字符"。
4. 循環遞推：重復上述過程 n-1 次，生成第 n 項。

時間復雜度：

• 外層循環 n-1 次，內層遍歷字符串長度，總時間復雜度為 O(n·m)，其中 m 為字符串的平均長度。

---

5. 邊界條件與注意事項

1. 輸入范圍：
   • n ≥ 1，需處理 n=1 直接返回 "1"。
2. 字符串拼接優化：
   • 使用 string 的 += 操作拼接字符，避免頻繁創建新對象。
3. 指針越界檢查：
   • 內層循環需確保 left 和 right 不超過字符串長度。
4. 大數問題：
   • 當 n 較大時（如 n=30），生成的字符串長度可能超過 1e5，需注意內存限制。

---

6. 代碼實現

class Solution {
public:string countAndSay(int n) {string ret = "1";for (int i = 1; i < n; i++) { // 迭代生成前n-1項string tmp; // 臨時存儲當前項的下一項描述int len = ret.size();for (int left = 0, right = 0; right < len;) {// 移動right指針，統計連續相同字符的數量while (right < len && ret[right] == ret[left]) right++;// 拼接"數量+字符"tmp += to_string(right - left) + ret[left];left = right; // 更新left指針到下一個字符的起始位置}ret = tmp; // 更新當前項}return ret;}
};

---

關鍵代碼解析

1. 外層循環控制迭代次數：

   for (int i = 1; i < n; i++)
   

   • 從第 1 項開始，生成到第 n 項需要迭代 n-1 次。

2. 雙指針統計連續字符：

   while (right < len && ret[right] == ret[left]) right++;
   

   • right 指針右移，直到遇到不同字符或越界。此時 right - left 即為連續字符的數量。

3. 拼接描述字符串：

   tmp += to_string(right - left) + ret[left];
   

   • 將數量轉換為字符串，并與當前字符拼接。例如，連續 2 個 '1' 拼接為 "21"。

4. 更新指針位置：

   left = right;
   

   • 將 left 移動到下一個待統計字符的起始位置。

---

與其他解法的對比

方法	時間復雜度	空間復雜度	核心思想
遞歸法	O(n·m)	O(n·m)	遞歸生成前一項，再描述
迭代法	O(n·m)	O(m)	雙指針遍歷，直接構造
動態規劃法	O(n·m)	O(m)	存儲中間結果，避免重復計算

---

總結

迭代法通過雙指針高效統計連續字符，避免了遞歸的棧空間開銷，是本題的最優解。其核心在于 逐層遞推 和 雙指針滑動窗口，以線性時間復雜度生成外觀數列。

適用場景：

• 需要快速生成較大 n 值的結果（如 n ≤ 30）。
• 內存敏感場景，避免遞歸棧溢出。

關鍵點：

• 理解雙指針在統計連續字符中的應用。
• 掌握字符串拼接的優化技巧。