[leetcode]: 38. Count and Say

[leetcode]: 38. Count and Say

1.题目

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.
一个读数的序列1, 11, 21, 1211, 111221,…给定n求这个序列第n个string是什么。
Note: The sequence of integers will be represented as a string.

2.分析

读数的规律：从前往后读
一个数字x如果后面没有相邻的相同数字，则读作 1x
例如 1–》11，21–》12 11
一个数字x如果后面有相邻相同数字，一共有n个，则读作nx
例如 11–》21， 111221（3个1，2个2，1个1）–》312211

找到规律后遍历一遍字符串即可。注意序列从第1个开始，不是从第0个开始。

3.代码

def countAndSay(self, n):if n<1:return elif n==1:return "1"cur="11"next=""for t in range(n-2):i=0while i<len(cur):count=1while i+count<len(cur) and cur[i]==cur[i+count]:count+=1next+=str(count)+cur[i]i+=countcur=nextnext=""return cur