LeetCode 38中等字符串
外观数列 图解题解
这道题到底在问什么
数列从 "1" 开始,每一项是对上一项的「读法」:把连续相同的数字读成「几个几」。求第 n 项。
- 第1项
- "1"
- 第2项
- "11"(读法:1个1)
- 第3项
- "21"(读法:2个1)
- n=5
- "111221"
最优解：一步一步想明白
- 3关键动作是分段:把一串数字切成「一段段连续相同的块」,每块念成「几个几」。下面用指针演示怎么扫出这些段。
- 4cur 落在第 0 格从第 1 项 "1" 开始念。cur 指针停在第 0 格,看它指的是什么数字。
- 51 个 1高亮的这一段都是数字 1,数一数:只有 1 个。所以这段念作「1 个 1」。
- 6追加「1」「1」把「个数 1」和「数字 1」依次写下来,就得到第 2 项 "11"。这一段处理完(变灰)。
- 7新一项,cur 回到第 0 格现在念第 2 项 "11"。指针 cur 回到最左边,重新从头分段。
- 8段起点 = 第 0 格cur 停在第 0 格,数字是 1,先把它收进当前段(高亮一格)。再看右边还是不是 1。
- 9第 1 格也是 1cur 往右走一格,第 1 格还是 1,和前面同一段,一起算进来——这段连续的 1 一共 2 个。
- 10追加「2」「1」「2 个 1」写下来就是「2」「1」→ 第 3 项 "21"。注意:是「2个1」念出 21,不是 1+1=2!
- 11新一项,cur 回到第 0 格念第 3 项 "21"。cur 回到第 0 格,这串里 2 和 1 不一样,会被切成两段。
- 121 个 2第一段从 2 开始,右边是 1 不一样,段到此为止——只有 1 个 2。念「1 个 2」。
- 13追加「1」「2」写下「1」「2」,下一项现在是 "12"。第一段处理完变灰,cur 跳到第二段的开头。
- 141 个 1cur 来到第二段,数字是 1,后面到头了——这段只有 1 个 1。
- 15追加「1」「1」再写「1」「1」,接到刚才的 "12" 后面 → 第 4 项 "1211"。两段拼完,整串处理完。
- 16新一项,cur 回到第 0 格念第 4 项 "1211"。这串会切成三段:1 | 2 | 11。cur 从头开始。
- 171 个 1第一段:1,右边 2 不一样,段结束 → 1 个 1,写下「1」「1」。下一项 = "11"。
- 181 个 2cur 跳到第二段:2,右边 1 不一样 → 1 个 2,写下「1」「2」。下一项变 "1112"。
- 19第 2、3 格都是 1cur 来到第三段:第 2 格是 1,第 3 格还是 1,连成一段——一共 2 个 1。
- 20追加「2」「1」第三段念「2 个 1」→ 写「2」「1」,接到 "1112" 后面 → 第 5 项 "111221"!三段全部处理完。
- 21111 | 22 | 1反过来验证一下第 5 项 111221:它也能继续被念——前三格连续 3 个 1(高亮),后面 2 个 2、1 个 1。规律一直成立。
- 221 → 11 → 21 → 1211 → 111221回头看这条链:每一项都是上一项的读法。绿色这串就是第 5 项 111221——盯住它和上一项 1211 的关系就全懂了。
- 23核心循环:i 标记段的起点,j 往右走到不同字符为止,(j−i) 就是个数,s[i] 就是数字。把这两个写进下一项,i 跳到 j。
- 27把 "21" 错算成 2+1=3 ✗如果把 "21" 当数值相加得到 3,就彻底错了。它要的是读法:1 个 2、1 个 1 → "1211"。记住:外观 = 念出来。
⚠️ 容易写错的地方
✗ 错：把 "11" 当成 1+1=2 去算
✓ 对：是「念出来」:1个1→11、2个1→21
这是「外观」数列,按读法生成,不是数值运算
✗ 错：内层 while 忘了判 j<len 越界
✓ 对：先判 j<len 再比 s[j]==s[i]
扫到结尾还往右比会数组越界
完整代码（Python / C++ / Java）
Python
class Solution:
def countAndSay(self, n):
s = "1"
for _ in range(n - 1): # 从第1项滚到第n项
res = []
i = 0
while i < len(s):
j = i
while j < len(s) and s[j] == s[i]: # 数同一段
j += 1
res.append(str(j - i)) # 个数
res.append(s[i]) # 数字
i = j # 跳到下一段
s = "".join(res)
return sC++
class Solution {
public:
string countAndSay(int n) {
string s = "1";
for (int t = 0; t < n - 1; t++) {
string res;
int i = 0;
while (i < (int)s.size()) {
int j = i;
while (j < (int)s.size() && s[j] == s[i]) j++;
res += to_string(j - i);
res += s[i];
i = j;
}
s = res;
}
return s;
}
};Java
class Solution {
public String countAndSay(int n) {
String s = "1";
for (int t = 0; t < n - 1; t++) {
StringBuilder res = new StringBuilder();
int i = 0;
while (i < s.length()) {
int j = i;
while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
res.append(j - i);
res.append(s.charAt(i));
i = j;
}
s = res.toString();
}
return s;
}
}复杂度
时间复杂度
O(n · L)
外层生成 n 项,每项要扫一遍当前串(长度 L)。串长随项数增长(约 1.3 倍/项),所以总量由最长串主导
空间复杂度
O(L)
只需保存当前项和正在构建的下一项两个串,L 为最长串长度
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 外观数列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么不能用公式直接算第 n 项?+
外观数列没有简单闭式,每一项必须靠上一项「念」出来,只能迭代生成。
内层为什么用双指针而不是计数器?+
都行。双指针 i/j 让「段的起止」很直观,(j−i) 即个数,代码也短;用计数器记录连续个数也等价。
能优化时间吗?+
本质上必须生成每一项,最长串长度决定下界,常规实现已是最优;实际优化多在字符串拼接(用 StringBuilder/res 数组避免反复 + )。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 外观数列 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。