38. 外观数列

🟠   🔖  字符串  🔗 LeetCode

题目

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

• countAndSay(1) = "1"
• countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string.

To determine how you "say" a digit string, split it into the minimal number of substrings such that each substring contains exactly one unique digit. Then for each substring, say the number of digits, then say the digit. Finally, concatenate every said digit.

For example, the saying and conversion for digit string "3322251":

Given a positive integer n, return thenth term of the count-and-say sequence.

Example 1:

Input: n = 1

Output: "1"

Explanation: This is the base case.

Example 2:

Input: n = 4

Output: "1211"

Explanation:

countAndSay(1) = "1"

countAndSay(2) = say "1" = one 1 = "11"

countAndSay(3) = say "11" = two 1's = "21"

countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"

Constraints:

• 1 <= n <= 30

Follow up: Could you solve it iteratively?

题目大意

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

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

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

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

进阶：你能迭代解决该问题吗？

解题思路

这个题的核心思路是模拟生成报数序列。我们需要从第 1 项开始，逐步生成后面的每一项，直到生成第 n 项为止。

1. 初始化：第 1 项是固定的，直接设置为 "1"。
2. 迭代生成：从第 2 项开始，每次根据前一项生成新的一项。我们通过遍历前一项的字符，统计连续相同字符的个数，然后将其转化为描述性的字符串。
3. 遍历字符串：对于每一项的生成，我们遍历当前项的字符串，对于每一组连续相同的数字，记录下它们的数量和数字本身，形成新的项。
4. 循环直到 n：我们从第 1 项逐步生成到第 n 项。

复杂度分析

• 时间复杂度：O(m * n)，其中 n 是给定的项数，m 是报数序列中最长的字符串的长度。对于每一项，我们需要遍历前一项的字符串生成新的一项，字符串的长度随着 n 逐渐增长。
• 空间复杂度：O(m)，m 是最长的字符串长度，因为我们只需要存储当前项和下一项的字符串。

代码

/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function (n) {
	// 初始项是 "1"
	let res = '1';

	// 迭代生成从第2项到第n项
	for (let i = 2; i <= n; i++) {
		let temp = '', // 存储当前生成的项
			count = 1; // 计数相同字符的数量

		// 遍历上一个结果的字符
		for (let j = 1; j < res.length; j++) {
			if (res[j] == res[j - 1]) {
				// 如果当前字符与前一个相同，计数增加
				count++;
			} else {
				// 否则，将前面的数字和计数添加到结果字符串中
				temp += count + res[j - 1];
				count = 1; // 重置计数
			}
		}

		// 处理最后一个数字
		temp += count + res[res.length - 1];

		// 更新当前项
		res = temp;
	}

	// 返回第n项
	return res;
};

相关题目

题号	标题	题解	标签	难度
271	字符串的编码与解码		设计 数组 字符串
443	压缩字符串		双指针 字符串