Leetcode 038报数题目分析 +python实现

怼烎@ 2022-05-14 03:35 112阅读 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，从左往右开始读是1个1.，因此第二项为11.
 *  第二项是11，从左往右开始读是2个1，因此第三项为21.
 *  第三项是21，从左往右开始读是1个2，1个1，因此第四项为1211。
 *  第四项是1211，从左往右开始读是1个1,1个2,2个1，因此第五项为111221
 *  第五项是111221,从左往右开始读是3个1,2个2,1个1,因此第六项为312211.

# 答案 #

class Solution:
        def countAndSay(self, n):
            """ :type n: int :rtype: str """
    
            ans_seq='1'                                 #初始化序列
            for _ in range(n-1):                        #进行n-1次循环，求得第n项的内容
                pre_char,temp,cnt=ans_seq[0],'',0       #pre_char定义每次重复的字符是哪个，temp暂存结果，cnt存储字符出现次数。
                for char in ans_seq:                   #遍历上一项的序列
                    if char == pre_char:
                        cnt+=1
                    else:                                #如果当前字符与上一个字符不同的话，就将当前的内容进行一定的调整。
                        temp+=str(cnt)+str(pre_char)
                        pre_char=char
                        cnt=1                           #初始化计数器为1。当前遍历位置是第一个新字符
                temp+=str(cnt)+str(pre_char)            #遍历完整个序列后，将结果复制给temp
                ans_seq=temp                            #更新当前项的序列
            return ans_seq