【LeetCode每日一题】——38.外观数列

一【题目类别】

• 字符串

二【题目难度】

• 中等

三【题目编号】

• 38.外观数列

四【题目描述】

• 给定一个正整数 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"
1
2
3
4
5
6
7
8
9
10

• 要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。
• 例如，数字字符串 “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”这个字符串开始，统计每个字符出现的次数，将次数和此字符保存在一个新的字符串中
• 然后将新的字符串赋值给原来的字符串
• 之后就是遍历到题目要求的长度就行
• 只是不同语言实现起来不太一样，具体可以参考下面的代码
• 最后返回结果即可

七【题目提示】

• $1<=n<=30$

八【时间频度】

• 时间复杂度：$O(mn)$，其中$m$为生成的字符串的最大长度，$n$为给定的正整数
• 空间复杂度：$O(m)$，其中$m$为生成的字符串的最大长度

九【代码实现】

1. Java语言版

package String;

/**
 * @Author: IronmanJay
 * @Description: 38.外观数列
 * @CreateTime: 2022-12-02  09:53
 */
public class p38_CountAndSay {

    public static void main(String[] args) {
        int n = 4;
        String res = countAndSay(n);
        System.out.println("res = " + res);
    }

    public static String countAndSay(int n) {
        String str = "1";
        for (int i = 2; i <= n; i++) {
            StringBuffer sb = new StringBuffer();
            int start = 0;
            int pos = 0;
            while (pos < str.length()) {
                while (pos < str.length() && str.charAt(start) == str.charAt(pos)) {
                    pos++;
                }
                sb.append(Integer.toString(pos - start));
                sb.append(str.charAt(start));
                start = pos;
            }
            str = sb.toString();
        }
        return str;
    }

}
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
27
28
29
30
31
32
33
34
35

2. C语言版

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include

char * countAndSay(int n)
{
	char* str = (char*)malloc(sizeof(char) * 5001);
	str[0] = '1';
	str[1] = '\0';
	for (int i = 2; i <= n; i++)
	{
		char* temp = (char*)malloc(sizeof(char) * 5001);
		int pos = 0;
		for (int j = 0; j < strlen(str); j++)
		{
			int count = 1;
			while (str[j + 1] && str[j] == str[j + 1])
			{
				count++;
				j++;
			}
			temp[pos++] = count + 48;
			temp[pos++] = str[j];
			temp[pos] = '\0';
		}
		strcpy(str, temp);
	}
	return str;
}

/*主函数省略*/
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
27
28
29
30
31
32

十【提交结果】

1. Java语言版
   

2. C语言版