[LeetCode] 38. 报数

38. 报数
报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串。

解法1:

class Solution(object):
    def countAndSay(self, n):
        char = "1"
        for i in range(n-1):  #第一层循环记录每一次的字符串
            res = ""
            j = 0
            while j < len(char):  #第二层循环读入前一次的字符串
                count = 1
                while j < len(char)-1 and char[j] == char[j+1]:  #第三层循环记录字符串中的字符
                    j += 1
                    count += 1
                j += 1
                res = res + str(count) + char[j-1]
            char = res
        return char

解法2

求出从0到n+1的字符串, 取出n对应的字符.

class Solution(object):
    def countAndSay(self, n):
        ans = ["1"]  #保存每次的结果, 1对应的是"1"
        for i in range(1, n):  #最外层循环从1开始(对应数字2)求解每一次的字符串
            pre = ans[i-1]  #取出前一个结果
            tmp = pre[0]  #记录临时字符
            count = 0  #用于字符计数
            str_new = "" #n+1对应的字符串结果
            for j in range(len(pre)):  #读前一个结果
                if pre[j] == tmp:
                    count += 1
                else:
                    str_new += str(count) 
                    str_new += str(pre[j-1])
                    tmp = pre[j]
                    count = 1
            str_new += str(count)
            str_new += str(tmp)
            ans.append(str_new)
        return ans[-1]