leetcode38.外观数列

发布于 2021-04-17 05:25 ，所属分类：知识学习综合资讯

题目描述

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

可以将其视作是由递归公式定义的数字字符串序列：

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

前五项如下：

1.     12.     113.     214.     12115.     111221第一项是数字 1 描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

（左右滑动查看完整内容）

要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多相同字符组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 "3322251" 的描述如下图：

（点击查看大图）

示例

输入：n = 1输出："1"解释：这是一个基本样例。
输入：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 <= n <= 30

难度：简单
标签：字符串

分析和题解

方法一

通过递归，逐步获取前一项的描述。最后通过前一项的描述获取当前描述。

遍历前一项描述的每个字符，从第一个和第二个字符开始形成一个滑块，比较滑块的首尾字符是否相同，如果相同，滑块尾部向后移动一位；如果不相同，记录滑块除去尾部的长度和首部字符，并且滑块首部变为从尾部开始，尾部向后移动一位。每移动完成后再比较一次首尾字符，以此循环。

如果滑块尾部超过前一项描述的长度时，再记录一次滑块除去尾部的长度和首部字符，循环结束。

class Solution:  def countAndSay(self, n: int) -> str:    if n == 1:      return '1'    s = self.countAndSay(n-1) # 递归获取前一项的描述    p, q = 0, 1 # 滑块的首尾    res = []    while q <= len(s): # 遍历前一项描述的每个字符      if q == len(s): # 尾超过最后一个字符时，进行记录        res.extend([str(q-p), s[p]])      elif s[p] != s[q]: # 首尾字符不同时,进行记录        res.extend([str(q-p), s[p]]) # 几个（q-p）首字符        p = q # 首到尾的位置      q += 1 # 尾向后移动一位    return ''.join(res)

（左右滑动查看完整代码）

方法二

方法二与方法一类似，只是不用递归，用循环（for循环或while循环都可以）求出每一项的描述。输入正整数 n，就循环n-1次，最终得到第n项的描述。

class Solution:    def countAndSay(self, n: int) -> str:        res = ['1']  # 存放前一项描述，默认第一项        for _ in range(n-1):            p, q = 0, 1  # 滑块的首尾            tmp = []            while q <= len(res):  # 遍历前一项描述的每个字符                if q == len(res):  # 尾超过最后一个字符时，进行记录                    tmp.extend([str(q-p), res[p]])                elif res[p] != res[q]:  # 首尾字符不同时,进行记录                    tmp.extend([str(q-p), res[p]])  # 几个（q-p）首字符                    p = q  # 首到尾的位置                q += 1  # 尾向后移动一位            res = tmp        return ''.join(res)