38. Count and Say

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 the nth 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

解题方法
解法一：循环
两重循环的思路是：

外层循环 i ii 负责递增 1.. n 1 .. n1..n；
内存循环负责求当取值为 i ii 时的外观数列。
​

Java 代码如下：

public class Solution {
public String countAndSay(int n) {
StringBuilder ans = new StringBuilder(“1”);
StringBuilder prev;
int count;
char say;
for(int i = 1; i < n; i++){
prev = ans;
ans = new StringBuilder();
count = 1;
say = prev.charAt(0);
for(int j = 1; j < prev.length(); j++){
if(say != prev.charAt(j)){
ans.append(count).append(say);
count = 1;
say = prev.charAt(j);
}else{
count++;
}
}
ans.append(count).append(say);
}
return ans.toString();
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
python 代码如下：

class Solution(object):
def countAndSay(self, n):
“””
:type n: int
:rtype: str
“””
res = “1”
for i in range(n – 1):
prev = res[0]
count = 1
ans = “”
for j in range(1, len(res)):
cur = res[j]
if prev != cur:
ans = ans + str(count) + str(prev)
prev = cur
count = 0
count += 1
res = ans + str(count) + str(prev)
return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
时间复杂度：O ( n ∗ m ) O(n * m)O(n∗m)，n nn 是输入的数字，m mm 是「外观数列」的最大长度；
空间复杂度：O ( m ) O(m)O(m)。
​

解法二：递归
其实，按照题目描述的话，我们最容易想到的应该就是递归解法。
​

题目描述是：

countAndSay(1) = “1”
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
这个意思就是想求 countAndSay(n) 的话，必须先求 countAndSay(n-1)，这就是标准的递归。
​

使用递归求解，一定不要用大脑去模拟递归的过程。大脑能压几个栈？
​

正确的做法是：记住递归函数的定义。比如本题中的递归函数 countAndSay(int n)含义是当取值为 n nn 时的外观数列。
​

那么，必须先求出取值为 n − 1 n – 1n−1 时的外观数列，怎么求？根据递归函数的定义，就是 countAndSay(n – 1)。至于 countAndSay(n – 1) 怎么算的，我们不用管。只要知道这个函数能给我们正确的结果就行。
​

我在下面的代码把 countAndSay(n – 1) 的结果即为 before，然后统计了 before 中各个数字出现的次数，就是取值为 n nn 时的外观数列。
​

C++ 代码如下：

class Solution {
public:
string countAndSay(int n) {
if (n == 1) {
return “1”;
}
string before = countAndSay(n – 1);
string res;
char cur = before[0];
int count = 1;
for (int i = 1; i < before.size(); ++i) {
if (before[i] != cur) {
res += to_string(count) + cur;
cur = before[i];
count = 0;
}
count ++;
}
res += to_string(count) + cur;
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
时间复杂度：O ( n ∗ m ) O(n * m)O(n∗m)，n nn 是输入的数字，m mm 是「外观数列」的最大长度；
空间复杂度：O ( m ) O(m)O(m)。
刷题心得
递归是最贴合本题意的解法。
递归的时间复杂度和遍历是一样的，因为 1.. n 1..n1..n 中的每个数字都被计算了一次。
原文链接：https://blog.csdn.net/fuxuemingzhu/article/details/71618640