38-count-and-say.md

38. Count and Say - 报数

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 被读作  "one 1"  ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2",  "one 1" （"一个二" ,  "一个一") , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。

 

示例 1:

输入: 1
输出: "1"

示例 2:

输入: 4
输出: "1211"

---

题目标签：String

题目链接：LeetCode / LeetCode中国

题解

这题用到了字符串压缩的思想，即把aaabb压缩成3a2b这种由数量与字符构成的字符串。基本做法是：pre保存前一个字符，cnt保存字符计数，遇到和pre相同就把cnt=1，不同就拼接到结果字符串，然后把pre设为当前字符，cnt=1，如此遍历；循环结束再做一次拼接到结果字符串。

Language	Runtime	Memory
python3	60 ms	N/A

class Solution:
    dp = {1: '1'}
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n in self.__class__.dp:
            return self.__class__.dp[n]
        else:
            for i in range(int(max(self.__class__.dp)), n+1):
                cnt, pre = 1, self.__class__.dp[i][0]
                tmp = ''
                for ii in self.__class__.dp[i][1:]:
                    if pre:
                        if pre == ii:
                            cnt += 1
                        else:
                            tmp += str(cnt) + pre
                            pre = ii
                            cnt = 1
                tmp += str(cnt) + pre
                self.__class__.dp[i+1] = tmp
            return self.__class__.dp[n]