Leetcode 报数

男娘i 2022-04-03 03:54 205阅读 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*（1 ≤ *n* ≤ 30），输出报数序列的第 *n* 项。

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

先上代码：

class Solution(object):  
    def countAndSay(self, n):  
        num = '1'  
        for i in range(n-1):  
            \#times记录相同元素出现的次数  
            times,m = 1,len(num)  
            \#ans记录每一次迭代得到的新字串  
            ans = ''  
            for i in range(m-1):  
                if num\[i\] == num\[i+1\]:  
                    times += 1  
                    continue  
                \#当前字符只出现一次  
                elif times == 1:  
                    ans += '1'+num\[i\]  
                \#从下一项开始不是连续的相同字符   
                else:  
                    ans += str(times) +num\[i-1\]  
                    times = 1  
            \#把没有遍历到的最后一项补上  
            ans += str(times)+num\[-1\]  
            num = ans  
            i += 1  
        return num

思路：

要求报数序列的第n项，由于我们已经有第一项了，只需要迭代 n-1 次，每次迭代后更新字串，作为下次迭代的参数，这是外层的for循环。

内层循环是迭代的主体，要干的事就是，给定一个字符串，求它的报数序列。

怎么求呢？我们用一个变量 times 记录相同的元素出现了几次，遍历当前的字串num，比较当前字符和下一个字符是否相同，这里有三种情况：

1 ）num \[ i \] == num \[ i + 1 \]，此时累积times，然后进入下一次循环；

2 ）num \[ i \] != num \[ i + 1 \]，而且计数器不为0，说明从前面某个字符直到当前字符都是连续相同的，从下一项开始出现了新字符。要做的是把连续字符累加到 ans 里，重置计数器 times ；

3 ）num \[ i \] != num \[ i + 1 \]，且计数器为1。这说明计数器刚被重置了，当前字符和它前后的字符都不相同，说明只有一个字符，把它加入 ans 即可。

时间复杂度显然为O （n^2）。