LeetCode 38： 外观数列 （模拟） —— 题解

👋 欢迎阅读

🎯 欢迎来到「外观数列」题解之旅！本文将带你从"把一串数字依次念出来"这一生活化场景出发，深入理解双指针分组扫描的巧妙运用，并掌握如何统计连续相同字符的个数来逐次生成第 n 项外观数列。

在开始之前，建议你先：

• 了解题目背景：这是 LeetCode 38 题，外观数列第 1 项固定为1，之后每一项都是对前一项"读出来"——连续相同的数字读成"个数 + 数字"。本质上，问题就是反复做一次游程编码（Run-Length Encoding）。

• 明确学习目标：掌握双指针分组扫描技术，理解left = right跳组与内层right < len边界的原因，并熟练处理n = 1与连续相同字符长度等边界情况。

• 准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如n = 4输出"1211"，n = 1输出"1"）。

本文将从规则理解、双指针分组、逐个拼接、迭代生成到代码实现，层层递进。即使你对游程编码还不熟悉，我们也会从"数一数有几个相同的，再把个数和数字念出来"这一直觉出发，让你轻松抓住核心思想——按组统计个数，念出即下一项。现在，让我们一起读出上一项，生成下一项吧！ 🔢🎯

🔥愿旖旎· 个人主页

📘学习专栏：《算法专栏》《LangChain学习》《贪心算法》

🌄 钱塘江上潮信来，今日方知我是我

✨当前学习内容：《模拟》

一.题目

38. 外观数列 - 力扣（LeetCode）

​

二、算法分析

一、问题分析（前置分析）

• 题目要求：返回外观数列的第n项（第 1 项为1，每项都是对前一项的"读数"）。
• 关键约束：n ≥ 1；每一项长度逐项增长；项与项之间只能迭代推导。
• 核心思路：数列没有闭式公式，无法一步算出第 n 项；只能从第 1 项出发，每轮做一次游程编码（把连续相同数字压缩成"个数 + 数字"），迭代n-1次得到答案。

📌 例子：读数规则如何生成数列

n = 1得1；读它"1 个 1"得11（n = 2）；读11为"2 个 1"得21（n = 3）；读21为"1 个 2、1 个 1"得1211（n = 4）。每一项都由上一项唯一确定，且规律无法用公式跳过中间项——这就是必须逐次生成的原因。

二、算法策略（双指针分组扫描 · 迭代生成）

核心步骤：

1. 初始化：ret = "1"（第 1 项）。
2. 迭代n-1次：外层循环i从 1 到n-1，每轮由ret生成新串tmp。
3. 双指针分组：left与right均从 0 出发；内层while (right < len && ret[right] == ret[left])让right一直探到该组末尾。
4. 拼接"个数 + 字符"：len2 = right - left为该组长度，先拼len2再拼ret[left]。
5. 跳组继续：left = right直接跳到下一组开头，重复直到right == len。
6. 更新并返回：ret = tmp作为下一轮输入，最终返回第 n 项。

📊 示例（由"1211"生成"111221"）：

right依次停在 1、2、4（= len）时，恰好切出"1"、"2"、"11"三组，拼得"111221"✅，正是"1211"的下一项。

三、正确性说明（简单版本）

• 分组完备：left始终指向某组起点，right沿相同字符推进到首个不同字符（或串尾），因此[left, right)恰好圈出一整组，不重不漏。
• 拼接语义正确：每组输出"个数 + 字符"两项，与"读数"规则逐字对应；组的先后顺序与原串一致，因此结果唯一且正确。
• 末组不丢：内层循环以right < len为界，right最终可能停在len（而非len-1），此时len2 = len - left仍能正确计算末组长度，最后一组必被输出。
• 迭代次数正确：初始已是第 1 项，再压缩n-1次正好得到第 n 项，n = 1时循环不执行直接返回"1"，不漏不多。

📌 例子：末组为什么不会漏

扫描"111221"（len = 6）：前两组是"111"（left = 0 → right = 3）与"22"（left = 3 → right = 5）；第三组"1"使right推进到6 = len，内层while因right < len不成立而退出，但len2 = 6 - 5 = 1仍被正常追加为"11"，最终得到"312211"✅——边界用right的越界而非right+1判断，末组才不会被吞掉。

四、实现细节（边界防护）

• 初始化：ret = "1"（第 1 项，题目保证n ≥ 1，故ret一定非空）；每轮新建tmp累积结果。
• 边界防护：内层while必须带right < len（否则ret[right]越界）；left = right允许left走到len，但此时外层right < len已为假，不会越界访问；n = 1时循环不进入，直接返回"1"。
• 复杂度：时间 O(n × L)（L 为末项长度，每轮线性扫描；实际 L 增长约 1.3 倍），空间 O(L)（ret与tmp两个字符串）。
• 关键操作：while (right < len && ret[right] == ret[left]) right++;（分组探测）、tmp += len2 + '0'; tmp += ret[left];（拼接个数与字符）、left = right;（跳组）。

📌 例子：初始值与循环次数的配套

n = 1时循环条件i = 1 < 1为假，一次都不执行，直接返回"1"✅；n = 4时循环执行i = 1, 2, 3共 3 次，依次得到"11"、"21"、"1211"✅。"初始值 = 第 1 项"与"循环 n-1 次"严格配套，若把初始值设为空串或循环写成 n 次，结果就会错位一项。

五、返回值（目标映射）

• 返回ret：外观数列的第 n 项，对应题目"返回外观数列的第 n 项"。

三.代码

class Solution { public: string countAndSay(int n) { string ret = "1"; // 第 1 项固定为 "1"（题目保证 n >= 1，故一定非空） // 1. 迭代生成：再压缩 n-1 次，即得到第 n 项 for (int i = 1; i < n; i++) { string tmp = ""; // 本轮生成的新一项 int len = ret.size(); // 当前项的长度 // 2. 双指针分组：left 指向组起点，right 向后探测该组末尾 for (int left = 0, right = 0; right < len;) { // 3. 探测：right 一直前进到首个不同字符（或串尾） while (right < len && ret[right] == ret[left]) { right++; } int len2 = right - left; // 该组连续相同字符的个数 tmp += len2 + '0'; // 先拼“个数”（0~9 转字符） tmp += ret[left]; // 再拼“字符”本身 left = right; // 跳到下一组开头（不能 left++） } ret = tmp; // 4. 本轮结果作为下一轮的输入 } return ret; // 5. 返回第 n 项 } };

四、易错点分析

难点1：tmp += len2 + '0'的整数转字符陷阱

int len2 = right - left; tmp += len2 + '0'; // 只对 0~9 成立 tmp += ret[left];

len2 + '0'是把单个数字转成对应字符的常用写法，但它只对 0~9 有效：若某组长度达到 10，10 + '0'会得到字符':'，既不是数字，也丢失了"10"的两位语义（正确做法应追加字符串"10"或先转to_string）。本数列的已知性质是连续相同数字长度不超过 3（如1113213211中的111），故n ≤ 30时不会触发；但依赖这一性质是脆弱的——把"个数"当单字符处理属于不严谨写法。

难点2：left = right跳组，而不是left++

left = right; // 直接跳到下一组开头

while结束时right已指向该组之后的第一个位置，即下一组的起点，所以left应直接跳到right（一次跨过整组）。若写成left++，left只会前移一格，随后会重复扫描同一组内部，把"11"读成两次"1 个 1"而非"2 个 1"，结果完全错误——"跳组"是双指针分组扫描的关键动作。

难点3：内层while必须带right < len

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

right会一路推进到len（串尾之后一位）。若漏掉right < len，当right == len时ret[right]会越界访问（UB），轻则读到垃圾字符导致分组错乱，重则崩溃。同时注意条件的顺序：right < len必须写在前面，靠&&的短路避免越界访问。

难点4：循环次数n-1与初始值的配套

string ret = "1"; for (int i = 1; i < n; i++) // 恰好 n-1 次

初始ret已是第 1 项，故只需再生成n-1次。若误写成i = 1; i <= n（多一次）会返回第n+1项；若写成i = 0（多一次）同理。反之若把初始值改成""并循环n次，则第一轮的输入是空串、无法产生 "1"。"初始值 = 第 1 项"与"循环 n-1 次"是一套固定搭配，改任何一半都要同步调整另一半。

五、流程图

🎯 闭幕

🎉 恭喜你完成了「外观数列」问题的学习！

为了巩固知识并进一步拓展，建议你：

🚀动手实践
在 LeetCode 上提交代码，尝试不同的测试用例。

💡深入思考

• 代码中ret初始为"1"，循环i = 1; i < n共执行n-1 次，得到第n项。为什么第 1 项固定是"1"？当n = 1时，代码直接返回什么？

• 内层使用双指针：left指向当前组的起点，right向后探测相同字符直到不同或结尾。right探测结束后，tmp += len2 + '0'和tmp += ret[left]分别表示什么？为什么必须先拼个数再拼字符？

• 代码用len2 + '0'把连续个数转成字符。如果某组连续相同字符个数超过 9（例如 10 个'1'），len2 + '0'会变成什么？这会导致结果错误吗？题目n的范围是否可能触发这种情况？

• 处理完一组后执行left = right，而不是left++。为什么必须直接跳到下一组开头？如果写成left++，会对同一组内的字符重复处理吗？请举例说明。

如果你觉得本文对你有所帮助，欢迎：

👍点赞 / 收藏
👤关注作者，获取更多题解
💬留言交流你的疑问或优化思路

📌深入思考答案

• 第 1 项固定为"1"是外观数列的定义起点；n = 1时循环不执行，直接返回"1"，正确。

• len2是当前组连续相同字符的个数，ret[left]是该字符本身。报数规则是“几个几”，所以先个数后字符，例如"21"表示“2 个 1”。

• len2 + '0'只适用于0~9的个数。若len2 = 10，'0' + 10会得到':'，结果错误。但 LeetCode 中n ≤ 30，外观数列的连续相同字符个数不会超过 9（通常最多 3），因此安全；若n更大，应改用to_string(len2)。

• left = right是因为[left, right)这一组已经处理完毕，right正好指向下一组的第一个字符。若写成left++，会从组内第二个字符开始再次统计，导致重复报数和错误结果。

祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨