Q38 Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.   1
2.   11
3.   21
4.   1211
5.   111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

解题思路：

说实话，第一次看到题目没读懂意思。后来在网上看有人解释才明白。

举个例子就明白了，比如输入6，6的上一个数是5，对应的字符串为 111221，这个111221读作 3个1,2个2,1个1，因此6对应的字符为312211。

观察了一下没有什么规律，因此简单方法就是从1一直找到要求的数字，不断的更新上一个字符串，然后生成当前的字符串。

因为要数多少个1、2，因此要有变量统计相同字符个数。

Python实现：

class Solution:
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n == 1:
            return '1'
        i = 1          # 从1开始构造
        lastStr = '1'  # 上一个字符串随着迭代次数更新
        while n > i:
            temp = ''  # 临时子串
            count = 0  # 统计相同字符的个数
            for j in range(len(lastStr)):  # 找出上一个字符串的特点，如 5 -> 111221
                if j > 0 and lastStr[j] != lastStr[j-1]:
                    temp += str(count) + lastStr[j-1] 
                    count = 1  # 重置count
                else:
                    count += 1              
            lastStr = temp + str(count) + lastStr[j]  # 构造当前字符串，如 6 -> 312211
            i += 1
        return lastStr

a = 7
b = Solution()
print(b.countAndSay(a))  # 13112221，因为6对应的字符串为312211