LeetCode——报数（ Count and Say）

分手后的思念是犯贱 2022-05-14 02:38 225阅读 0赞

**题目**：

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

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* ，输出报数序列的第 *n* 项。

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

**示例 1:**

输入: 1
    输出: "1"

**示例 2:**

输入: 4
    输出: "1211"

**思路**：

这里首先鄙视那些写博客，就贴个题目和代码，并且代码不写注释的人，不知道这种博客写出来有什么意义。因为本体题目简单，但是题意较难理解，所以我当初去查找了相关博客，很多都没有思路或者思路不明的，最后终于找到了一篇较好的。

这道题就如同题目一样就是报“数”，报数的数量，不过这个数量，要从1开始报数计算。这里简单捋一捋：

当n=1的时候，默认是“1”，这里不用管了

当n=2的时候，我们首先要遍历1的报数结果，因为“1”只有1个1，所以n=2的结果就是“11”，就是1个1的意思。

当n=3的时候，这里遍历n=2的报数结果，因为“11”用循环遍历的话就会有1个1，2个1，跳出循环，所以n=3的结果就是“21”，就是2个1的意思。

当n=4的时候，这里遍历n=3的报数结果，因为“21”用循环遍历的话就会有1个2,1个1，跳出循环，所以n=4的结果就是“1211”，就是1个2和1个1的意思。

下面弄个复杂的，给还没有看懂的人提示：

如果n = x的报数结果是“123456”，那么n=x+1就要遍历n=x的报数结果，遍历结果就是1个1,1个2,1个3,1个4，1个5,1个6，合在一起就变成“111213141516”。

理解了题目之后，就说下思路，首先从1到n开始循环，这里是外层循环。默认n=1的时候，结果为“1”。根据前面的分析，我们得到当前n的报数结果是基于n-1的报数结果，所以内层循环就是 遍历n-1的报数结果。外层循环的一次循环需要保存一次当前n的报数结果，这样n+1才能用n的报数结果。

**代码**：

class Solution:
        def countAndSay(self, n):
            """
            :type n: int
            :rtype: str
            """
            if n < 1:
                return ""
            resultStr = "" #保存返回结果
            cnt = 0 #记录重复数字数量
            i = 1
            j = 0
            while i <= n:
                if i == 1:
                    resultStr = "1"
                else:
                    j = 0
                    tempStr = ""
                    tempNum = resultStr[0]
                    cnt = 0
                    while j < len(resultStr):
                        if tempNum == resultStr[j]:#如果前一个数和当前数相等，则cnt+1
                            cnt += 1
                        else:#如果不想等
                            tempStr += (str(cnt)+str(tempNum)) #记录前面统计的结果
                            tempNum = resultStr[j] #把当前的数字当成要报的数
                            cnt = 1 #统计数量为1，因为下一次循环，肯定跳过了当前的数，所以这里cnt =1
                        j += 1
                    tempStr += (str(cnt) + str(tempNum))#不管相等还是不想等，在循环里，我们都无法记录最后一次统计，所以在循环结束后，手动记录
                    resultStr = tempStr #把临时记录的统计信息放在结果中，作为当前报数的成果
                i += 1
            return resultStr
    if __name__ =="__main__":
        res = Solution()
        print(res.countAndSay(5))
        pass