LeetCode 题解工作台
外观数列
「外观数列」是一个数位字符串序列，由递归公式定义： countAndSay(1) = "1" countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。 行程长度编码 （RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行…
1
题型
9
代码语言
3
相关题
当前训练重点
中等 · String-driven solution strategy
答案摘要
class Solution: def countAndSay(self, n: int) -> str:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 String-driven solution strategy 题型思路
题目描述
「外观数列」是一个数位字符串序列，由递归公式定义：
countAndSay(1) = "1"countAndSay(n)是countAndSay(n-1)的行程长度编码。
行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。
给定一个整数 n ，返回 外观数列 的第 n 个元素。
示例 1：
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = "1" 的行程长度编码 = "11"
countAndSay(3) = "11" 的行程长度编码 = "21"
countAndSay(4) = "21" 的行程长度编码 = "1211"
示例 2：
输入：n = 1
输出："1"
解释：
这是基本情况。
提示：
1 <= n <= 30
进阶：你能迭代解决该问题吗？
解题思路
方法一
class Solution:
def countAndSay(self, n: int) -> str:
s = '1'
for _ in range(n - 1):
i = 0
t = []
while i < len(s):
j = i
while j < len(s) and s[j] == s[i]:
j += 1
t.append(str(j - i))
t.append(str(s[i]))
i = j
s = ''.join(t)
return s
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of digits generated for each term, which grows roughly exponentially, leading to O(2^n) in the worst case. Space complexity is dominated by the size of the string for the nth term, also O(2^n). |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask candidates how to generate terms iteratively instead of recursively to prevent stack overflow.
- question_mark
Probe understanding of run-length encoding for string sequences and handling consecutive duplicates.
- question_mark
Check if candidate considers memory efficiency when building strings for higher n.
常见陷阱
外企场景- error
Attempting direct recursion without memoization can lead to stack overflow or repeated work.
- error
Neglecting edge cases like n=1 or strings with only one character.
- error
Incorrectly counting consecutive digits or misplacing the count before the digit.
进阶变体
外企场景- arrow_right_alt
Generate a custom count-and-say sequence using letters instead of digits.
- arrow_right_alt
Return the sequence up to nth term as a list instead of a single string.
- arrow_right_alt
Implement the sequence using recursion with memoization for optimization.