Leetcode 外观数列

外观数列

给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 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:

输入: 1
输出: "1"
解释：这是一个基本样例。

示例 2:

输入: 4
输出: "1211"
解释：当 n = 3 时，序列是 "21"，其中我们有 "2" 和 "1" 两组，"2" 可以读作 "12"，也就是出现频次 = 1 而 值 = 2；类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起，也就是 "1211"。

解题思路

定义变量res=“1”, 当n=1时, 返回res
定义lst=[], 保存过程数据
从2-n开始循环, 每次循环 对res逐一位判断
当lst为空时, lst数组保存[1, 当前位数字]
当lst不为空时, 如果当前位数字和lst最后一个元素相等, 则lst倒数第二位+1, 不相等则 lst扩展[1, 当前位数字]
最后lst中所有元素转为字符, 并连接到一起返回

Answer

 1#
 2# @lc app=leetcode.cn id=38 lang=python3
 3#
 4# [38] 外观数列
 5#
 6
 7# @lc code=start
 8class Solution:
 9    def countAndSay(self, n: int) -> str:
10        res = "1"
11        if n == 1:
12            return res
13        for i in range(2, n+1):
14            lst = []
15            for m in res:
16                if not lst:
17                    lst.extend([1, m])
18                else:
19                    if m == lst[-1]:
20                        lst[-2] = lst[-2] + 1
21                    else:
22                        lst.extend([1, m])
23            res = ''.join([str(r) for r in lst])
24        return res
25# @lc code=end

Accepted

18/18 cases passed (36 ms)
Your runtime beats 97.67 % of python3 submissions
Your memory usage beats 6.67 % of python3 submissions (13.7 MB)

• ←上一页
• 下一页→