列表

详情

38. 外观数列

给定一个正整数 n ，输出外观数列的第 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"

 

提示：

相似题目

字符串的编码与解码

压缩字符串

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: string countAndSay(int n) { } };

java 解法, 执行用时: 9 ms, 内存消耗: N/A, 提交时间: 2018-08-29 17:33:26 

class Solution {
    public String countAndSay(int n) {
        String start = "1";
        int num = 0, count = 0,i = 0;
        char tmp;
        while(n-- > 1) {
            char chars[] = start.toCharArray();
            StringBuilder sb = new StringBuilder();
            i = 0;
            while(i < chars.length) {
                count = 0;
                tmp = chars[i];
                while(i < chars.length && chars[i] == tmp) {
                    count++;
                    i++;
                }
                sb.append(count + "" + tmp);  
            }
            start = sb.toString();
        }
        return start;
    }
}

python3 解法, 执行用时: 52 ms, 内存消耗: N/A, 提交时间: 2018-08-29 16:41:36 

class Solution:
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n == 1:
            return '1'
        if n == 2:
            return '11'
        
        #进行i=3时的循环时，它的上一项为'11'
        pre = '11'
        
        #用for循环不断去计算逼近最后一次
        for i in range(3, n+1):  
            res = ''  #结果，每次报数都要初始化  
            cnt = 1   #计数变量
            
            length = len(pre)  #遍历我们的上一项，所以记录它的长度
            for j in range(1, length):
                if pre[j-1] == pre[j]: #相等则加一  
                    cnt += 1
                else:
                    #一旦遇到不同的变量，就更新结果
                    res += str(cnt) + pre[j-1]  
                    cnt = 1  #重置为1
            #把最后一项及它的数量加上
            res += str(cnt) + pre[j]  
            pre = res#保存上一次的结果
        return res

上一题

© 2024 leetcode.cn