外观数列
难度:
标签:
题目描述
给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：
countAndSay(1) = "1"countAndSay(n)是对countAndSay(n-1)的描述，然后转换成另一个数字字符串。
前五项如下：
1. 1 2. 11 3. 21 4. 1211 5. 111221 第一项是数字 1 描述前一项，这个数是1即 “ 一 个 1 ”，记作"11"描述前一项，这个数是11即 “ 二 个 1 ” ，记作"21"描述前一项，这个数是21即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"描述前一项，这个数是1211即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。
例如，数字字符串 "3322251" 的描述如下图：
示例 1：
输入：n = 1 输出："1" 解释：这是一个基本样例。
示例 2：
输入：n = 4 输出："1211" 解释： countAndSay(1) = "1" countAndSay(2) = 读 "1" = 一 个 1 = "11" countAndSay(3) = 读 "11" = 二 个 1 = "21" countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
提示：
1 <= n <= 30
代码结果
运行时间: 48 ms, 内存: 15.1 MB
// Java solution using Stream API for the Count and Say problem
// Similar to the regular Java solution, but we use Streams to manipulate and count the digits.
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class StreamSolution {
public String countAndSay(int n) {
String result = "1";
for (int i = 2; i <= n; i++) {
result = IntStream.range(0, result.length())
.boxed()
.filter(j -> j == 0 || result.charAt(j) != result.charAt(j - 1))
.map(j -> new int[]{j, IntStream.range(j, result.length())
.filter(k -> result.charAt(k) == result.charAt(j)).count()})
.map(arr -> arr[1] + "" + result.charAt(arr[0]))
.collect(Collectors.joining());
}
return result;
}
}解释
方法:
这道题采用递归的思路来解决。对于第n项，它是对第n-1项的描述。在描述时，需要统计连续相同数字的个数，并将个数和数字一起作为描述结果。递归的base case是n等于1时，直接返回字符串'1'。
时间复杂度:
O(2^n)
空间复杂度:
O(2^n)
代码细节讲解
🦆
在算法实现中，为什么选择使用递归而不是迭代方法来构建外观数列？
▷🦆
在递归方法中，你是如何处理连续字符的统计以保证不会遗漏或重复计数？
▷🦆
在处理字符串末尾的字符时，如何确保所有字符都被正确添加到结果字符串中，特别是最后一个字符组？
▷🦆
递归过程中每次调用`countAndSay(n-1)`时，如何避免重复计算导致的性能问题？
▷相关问题
压缩字符串
给你一个字符数组 chars ，请使用下述算法压缩：
从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：
- 如果这一组长度为
1，则将字符追加到s中。 - 否则，需要向
s追加字符，后跟这一组的长度。
压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。
请在 修改完输入数组后 ，返回该数组的新长度。
你必须设计并实现一个只使用常量额外空间的算法来解决此问题。
示例 1：
输入：chars = ["a","a","b","b","c","c","c"] 输出：返回 6 ，输入数组的前 6 个字符应该是：["a","2","b","2","c","3"] 解释："aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。
示例 2：
输入：chars = ["a"] 输出：返回 1 ，输入数组的前 1 个字符应该是：["a"] 解释：唯一的组是“a”，它保持未压缩，因为它是一个字符。
示例 3：
输入：chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"] 输出：返回 4 ，输入数组的前 4 个字符应该是：["a","b","1","2"]。 解释：由于字符 "a" 不重复，所以不会被压缩。"bbbbbbbbbbbb" 被 “b12” 替代。
提示：
1 <= chars.length <= 2000chars[i]可以是小写英文字母、大写英文字母、数字或符号