Leetcode 报数

题目：

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

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( ):
    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）。