LeetCode【0038】外观数列

1 中文题目

外观数列是一个数位字符串序列，由递归公式定义：

• countAndSay(1) = "1"
• countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。

行程长度编码（RLE） 是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。

例如，要压缩字符串 “3322251” ，将 “33” 用 “23” 替换，将 “222” 用 “32” 替换，将 “5” 用 "15"替换，并将 “1” 用 “11” 替换。因此压缩后字符串变为 “23321511”。

给定一个整数 n ，返回 外观数列 的第 n 个元素。

示例：

输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = "1" 的行程长度编码 = "11"
countAndSay(3) = "11" 的行程长度编码 = "21"
countAndSay(4) = "21" 的行程长度编码 = "1211"

输入：n = 1
输出："1"
解释：
这是基本情况。

提示：

• $1\le n\le 30$

---

2 求解方法：递归

2.1 方法思路

方法核心

• 使用递归方式生成外观数列
• 采用双指针思想统计连续相同数字
• 使用列表而非字符串拼接提高效率

实现步骤

使用递归获取前一个数的字符串表示，对获取的字符串进行计数和描述，将计数结果转换为新的字符串，递归终止条件是n=1时返回"1"。

具体过程：

• 首先判断是否为第一项
• 递归获取前一项的结果
• 初始化计数器和结果列表
• 遍历字符串统计连续数字
• 拼接最终结果

方法示例

例如，对于n=4的计算过程：

n=1 返回 "1"
n=2 处理过程：
    输入："1"
    计数：一个1
    输出："11"

n=3 处理过程：
    输入："11"
    计数：两个1
    输出："21"

n=4 处理过程：
    输入："21"
    计数：一个2，一个1
    输出："1211"

详细执行步骤（以n=4为例）：

1. countAndSay(4)调用countAndSay(3)
2. countAndSay(3)调用countAndSay(2)
3. countAndSay(2)调用countAndSay(1)
4. countAndSay(1)返回"1"

然后逐级返回处理：

countAndSay(2)处理"1"：
- cur_digit = '1'
- count = 1
- 结果："11"

countAndSay(3)处理"11"：
- cur_digit = '1', count = 2
- 结果："21"

countAndSay(4)处理"21"：
- cur_digit = '2', count = 1
- cur_digit = '1', count = 1
- 结果："1211"

2.2 Python代码

class Solution:
    def countAndSay(self, n: int) -> str:
        # 如果n为1，直接返回"1"
        if n == 1:
            return "1"
        
        # 递归获取前一个数的外观数列字符串
        prev = self.countAndSay(n - 1)
        
        # 初始化结果字符串和计数器
        result = []        # 使用列表存储结果（比字符串拼接效率高）
        count = 1         # 当前数字的计数
        cur_digit = prev[0]  # 当前正在统计的数字
        
        # 遍历前一个数，从第二个字符开始
        for i in range(1, len(prev)):
            # 如果当前数字与前一个相同，计数加1
            if prev[i] == cur_digit:
                count += 1
            else:
                # 如果不同，将前一个数字的统计结果添加到结果中
                result.extend([str(count), cur_digit])
                # 重置计数器和当前数字
                count = 1
                cur_digit = prev[i]
        
        # 处理最后一组数字
        result.extend([str(count), cur_digit])
        
        # 将结果列表转换为字符串
        return ''.join(result)

2.3 复杂度分析

• 时间复杂度：O(n·m)，n是给定的数字，m是生成的字符串的平均长度
  • 每个递归级别需要遍历前一个字符串
• 空间复杂度：O(n)
  • 递归调用栈深度为n
  • 每层递归中的临时存储是常数级别

---

3 题目总结

题目难度：中等
数据类型：字符串
应用算法：递归

原文地址：https://blog.csdn.net/qq_32882309/article/details/143741974

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！