The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 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 sequence.
?
Note: The sequence of integers will be represented as a string.
?
?
?
Code:
?
复制代码
class Solution:
? ? # @return a string
? ? def countAndSay(self, n):
? ? ? ? #思路：遍历，每次对前面的string进行分析，输出
? ? ? ? s= '1'
? ? ? ? for i in range(n-1):
? ? ? ? ? ? prev = newS =''
? ? ? ? ? ? num = 0
? ? ? ? ? ? for curr in s:
? ? ? ? ? ? ? ? if prev !='' and prev != curr:
? ? ? ? ? ? ? ? ? ? newS += str(num) + prev ?# how many times the value "prev" appears
? ? ? ? ? ? ? ? ? ? num = 1
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? num += 1
? ? ? ? ? ? ? ? prev = curr
? ? ? ? ? ? newS += str(num) + prev
? ? ? ? ? ? s = newS
? ? ? ? return s