leetcode - 报数

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(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        s = "1"
        for i in range(2, n+1):
            count = 0
            a = s[0]
            temp = ""
            for j in s:
                if a == j:
                    count += 1
                else:
                    temp += str(count) + a
                    count = 1
                    a = j
            temp += str(count) + a
            s = temp

        return s

中规中矩，循环通过，时间复杂度为一个n^2 ? 这个复杂度可能不止，但是有一个我万万没想到的方法就是看到了n的范围，那么把从1 到 30都列一遍时间复杂度就是 1 ！！！？？？

虽然没必要但是确实很屌= =

今天也是一条咸鱼呢，快乐咸鱼每一天！