# 38. Count and Say 外观数列

• 作者： 负雪明烛
• id： fuxuemingzhu
• 公众号：负雪明烛
• 本文关键词：LeetCode，力扣，算法，算法题，外观数列，Count and Say，刷题群

@TOC

## # 题目描述

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221


1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"


Example 2:

Input: 4
Output: "1211"


## # 解题方法

### # 解法一：循环

• 外层循环 负责递增
• 内存循环负责求当取值为 时的外观数列。

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();
}
}



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


• 时间复杂度： 是输入的数字， 是「外观数列」的最大长度；
• 空间复杂度：

### # 解法二：递归

• countAndSay(1) = "1"
• countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

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;
}
};

• 时间复杂度： 是输入的数字， 是「外观数列」的最大长度；
• 空间复杂度：

## # 刷题心得

• 递归是最贴合本题意的解法。
• 递归的时间复杂度和遍历是一样的，因为 中的每个数字都被计算了一次。

## # 日期

2017 年 5 月 11 日 2018 年 11 月 22 日 —— 感恩节快乐～ 2021 年 10 月 15 日