欢迎阅读 欢迎来到「外观数列」题解之旅本文将带你从把一串数字依次念出来这一生活化场景出发深入理解双指针分组扫描的巧妙运用并掌握如何统计连续相同字符的个数来逐次生成第 n 项外观数列。在开始之前建议你先了解题目背景这是 LeetCode 38 题外观数列第 1 项固定为1之后每一项都是对前一项读出来——连续相同的数字读成个数 数字。本质上问题就是反复做一次游程编码Run-Length Encoding。明确学习目标掌握双指针分组扫描技术理解left right跳组与内层right len边界的原因并熟练处理n 1与连续相同字符长度等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如n 4输出1211n 1输出1。本文将从规则理解、双指针分组、逐个拼接、迭代生成到代码实现层层递进。即使你对游程编码还不熟悉我们也会从数一数有几个相同的再把个数和数字念出来这一直觉出发让你轻松抓住核心思想——按组统计个数念出即下一项。现在让我们一起读出上一项生成下一项吧 愿旖旎· 个人主页学习专栏《算法专栏》《LangChain学习》《贪心算法》 钱塘江上潮信来今日方知我是我✨当前学习内容《模拟》一.题目38. 外观数列 - 力扣LeetCode​二、算法分析一、问题分析前置分析题目要求返回外观数列的第n项第 1 项为1每项都是对前一项的读数。关键约束n ≥ 1每一项长度逐项增长项与项之间只能迭代推导。核心思路数列没有闭式公式无法一步算出第 n 项只能从第 1 项出发每轮做一次游程编码把连续相同数字压缩成个数 数字迭代n-1次得到答案。 例子读数规则如何生成数列n 1得1读它1 个 1得11n 2读11为2 个 1得21n 3读21为1 个 2、1 个 1得1211n 4。每一项都由上一项唯一确定且规律无法用公式跳过中间项——这就是必须逐次生成的原因。二、算法策略双指针分组扫描 · 迭代生成核心步骤初始化ret 1第 1 项。迭代n-1次外层循环i从 1 到n-1每轮由ret生成新串tmp。双指针分组left与right均从 0 出发内层while (right len ret[right] ret[left])让right一直探到该组末尾。拼接个数 字符len2 right - left为该组长度先拼len2再拼ret[left]。跳组继续left right直接跳到下一组开头重复直到right len。更新并返回ret tmp作为下一轮输入最终返回第 n 项。 示例由1211生成111221步骤leftright扫描到的组len2个数追加内容tmp初始00———第 1 组01111111第 2 组1221121112第 3 组2411221111221right依次停在 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不漏不多。 例子末组为什么不会漏扫描111221len 6前两组是111left 0 → right 3与22left 3 → right 5第三组1使right推进到6 len内层while因right len不成立而退出但len2 6 - 5 1仍被正常追加为11最终得到312211✅——边界用right的越界而非right1判断末组才不会被吞掉。四、实现细节边界防护初始化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 项 } };四、易错点分析难点1tmp len2 0的整数转字符陷阱int len2 right - left; tmp len2 0; // 只对 0~9 成立 tmp ret[left];len2 0是把单个数字转成对应字符的常用写法但它只对 0~9 有效若某组长度达到 1010 0会得到字符:既不是数字也丢失了10的两位语义正确做法应追加字符串10或先转to_string。本数列的已知性质是连续相同数字长度不超过 3如1113213211中的111故n ≤ 30时不会触发但依赖这一性质是脆弱的——把个数当单字符处理属于不严谨写法。难点2left right跳组而不是leftleft right; // 直接跳到下一组开头while结束时right已指向该组之后的第一个位置即下一组的起点所以left应直接跳到right一次跨过整组。若写成leftleft只会前移一格随后会重复扫描同一组内部把11读成两次1 个 1而非2 个 1结果完全错误——跳组是双指针分组扫描的关键动作。难点3内层while必须带right lenwhile (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多一次会返回第n1项若写成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 个1len2 0会变成什么这会导致结果错误吗题目n的范围是否可能触发这种情况处理完一组后执行left right而不是left。为什么必须直接跳到下一组开头如果写成left会对同一组内的字符重复处理吗请举例说明。如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案第 1 项固定为1是外观数列的定义起点n 1时循环不执行直接返回1正确。len2是当前组连续相同字符的个数ret[left]是该字符本身。报数规则是“几个几”所以先个数后字符例如21表示“2 个 1”。len2 0只适用于0~9的个数。若len2 100 10会得到:结果错误。但 LeetCode 中n ≤ 30外观数列的连续相同字符个数不会超过 9通常最多 3因此安全若n更大应改用to_string(len2)。left right是因为[left, right)这一组已经处理完毕right正好指向下一组的第一个字符。若写成left会从组内第二个字符开始再次统计导致重复报数和错误结果。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨