38.外观数列

题目描述

给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：
countAndSay(1) = “1”
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：

```
1
```
```
11
```
```
21
```
```
1211
```
```
111221
```
第一项是数字 1
描述前一项，这个数是 1 即 “ 一个 1 ”，记作 “11”
描述前一项，这个数是 11 即 “ 二个 1 ” ，记作 “21”
描述前一项，这个数是 21 即 “ 一个 2 + 一个 1 ” ，记作 “1211”
描述前一项，这个数是 1211 即 “ 一个 1 + 一个 2 + 二个 1 ” ，记作 “111221”
要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多相同字符组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

思路

1.递归
递归出口为n == 1时，返回”1”；
当n > 1时，我们只需要计算countAndSay(n - 1)中每个数字的个数：
对于计算字符串中每个数字出现的个数，使用双指针i, j，其中i表示当前字符，j则是计数指针，向后移动判断；
以求n = 5，lastStr = countAndSay(4) = “1211”为例，answer = “”，一开始让i = 0, j = 1，此时’1’ != ‘2’，
故answer += (j - i) + lastStr.charAt(i)，ans = “11”；然后让i = j（第二个不同字符起始位置），
然后j++往后移动；此时i = j = 1，j = j + 1 = 2，又’2’ != ‘1’，
所以answer += (j - i) + lastStr.charAt(i),ans = “1112”,重复i = j = 2， j = ++j = 3；此时’1’ = ‘1’；
故直接j = ++j = 4 == lastStr.length()，所以跳出循环，然后把最后一次的字符个数字符加上，即执行：
answer += (j - i) + lastStr.charAt(i),ans = “111221”，即countAndSay(5) = “111221”。
2.正则表达式
用正则表达式匹配一个数字的重复序列和数字本身，然后将匹配的序列的长度加上数字本身替换原字符串中重复序列，…，以此类推。

代码

class Solution:
    def countAndSay(self, n: int) -> str:
        """
        递归法
        :param n:
        :return:
        """
        if n == 1:  # 递归出口
            return "1"
        else:
            lastStr = self.countAndSay(n - 1)
            ans = ""
            i = 0
            j = 1

            while j < len(lastStr):
                if lastStr[i] != lastStr[j]:
                    ans += str(j-i)
                    ans += str(lastStr[i])
                    i = j  # 下一个不同字符的起始位置

                j += 1

            ans += str(j - i)
            ans += str(lastStr[i])

            return str(ans)

    def countAndSay1(self, n):
        """
        :type n: int
        :rtype: str
        """
        import re

        s = '1'
        for _ in range(n - 1):
            s = re.sub(r'(.)\1*', lambda a: str(len(a.group(0))) + a.group(1), s)  # sub(pattern, repl, string)
            # r'(.)\1*' (.)匹配一个任意字符作为一个分组 \1*匹配与第一个分组相同内容0次/多次
        return s


if __name__ == '__main__':
    s = Solution()
    res = s.countAndSay1(5)
    print(res)

victory的博客

leetcode | 38.外观数列

38.外观数列

题目描述

思路

代码