38. 外观数列

目录

一、问题描述

二、解题思路

三、代码

四、复杂度分析

---

一、问题描述

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

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

行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。

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

二、解题思路

“外观数列”是一个通过递归生成的序列，序列中的每一项是对前一项的描述。具体的描述方式类似于行程长度编码（RLE），即按字符连续重复的次数来描述每一位。

为了生成第 n 个元素，我们需要从第 1 项开始，逐步构造后续项。第 1 项为 "1"，后续每一项由对前一项进行“描述”得到。

例如：

• countAndSay(1) = "1"
• countAndSay(2) = "11" （“1”被描述为“一个1”）
• countAndSay(3) = "21" （“11”被描述为“两个1”）
• countAndSay(4) = "1211" （“21”被描述为“一个2、一个1”）
• countAndSay(5) = "111221" （“1211”被描述为“一个1、一个2、两个1”）

实现步骤：

1. 从第 1 项开始，递归或迭代生成第 n 项。
2. 使用双指针或计数来对字符串进行“描述”，即按连续字符的次数和字符本身生成新的字符串。

三、代码

class Solution {public String countAndSay(int n) {// 从第1项 "1" 开始构造，逐步生成第n项String result = "1";// 从第二项开始循环，直到第n项for (int i = 2; i <= n; i++) {StringBuilder current = new StringBuilder(); // 存储当前项int count = 1; // 用于计数相同数字的次数// 遍历上一个字符串result，描述该字符串for (int j = 1; j < result.length(); j++) {if (result.charAt(j) == result.charAt(j - 1)) {// 如果当前字符与前一个字符相同，计数加1count++;} else {// 如果不同，生成描述，并重置计数current.append(count).append(result.charAt(j - 1));count = 1;}}// 处理最后一段字符的描述current.append(count).append(result.charAt(result.length() - 1));// 更新result为当前描述的字符串result = current.toString();}return result; // 返回最终生成的第n项}
}

四、复杂度分析

• 时间复杂度：O(n * L)，L 是字符串的平均长度。由于每一项的长度逐渐增长，复杂度接近 O(n²)。
• 空间复杂度：O(L)，其中 L 是当前生成的字符串的长度。我们只需要存储当前项和前一项，因此空间使用较为高效。