目录
一、问题描述
二、解题思路
三、代码
四、复杂度分析
一、问题描述
「外观数列」是一个数位字符串序列,由递归公式定义:
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 项开始,递归或迭代生成第 n 项。
- 使用双指针或计数来对字符串进行“描述”,即按连续字符的次数和字符本身生成新的字符串。
三、代码
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 是当前生成的字符串的长度。我们只需要存储当前项和前一项,因此空间使用较为高效。