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.
Note: The sequence of integers will be represented as a string.
2- 思路分析
计算第n次输出,需顺序统计第n-1次各个字符出现的次数,然后将字符个数和字符合并。如第3次为'1211',从左到右,1个'1'、1个'2'、2个'1',所以下一个数为'111221'。本题关键即是分离出各相同字符字串。如'1211'——>'1' '2' '11'.
以下Python实现,给出2种实现分离的方法:其中第一种则使用栈从后往左解析,第二种为Kainwen给出,使用生成器(T_T,不懂)。
3- Python实现
# -*- coding: utf-8 -*-
# 方法1 栈 class Solution:
# @param {integer} n
# @return {string}
def countAndSay(self, n):
s = [] # 列表保存第n次结果
s.append('')
if n == 1: return s[0]
for i in range(1, n):
stack = [] # 栈用于存储每次pop的元素
res = [] # 每解析完一组相同字符字串,将str(长度),字符存入
last = list(s[-1]) # 上一次的结果
while True:
try:
end = last.pop() # 取出列表右端元素
except: # 若列表为空,说明已经遍历完,统计栈内元素个数,跳出循环
res.insert(0, str(len(stack)))
res.insert(1, stack[-1])
break
if not stack: # 若栈为空,则取出的元素直接入栈,进入下一次循环
stack.append(end)
continue
if stack[-1] == end: # 若栈不为空,判断取出元素是否和栈内元素相同,相同则入栈
stack.append(end)
else: # 不同,则统计栈内元素,然后清空栈,将新元素入栈
res.insert(0, str(len(stack)))
res.insert(1, stack[-1])
stack = []
stack.append(end)
s.append(''.join(res)) # 拼接长度和字符
return s[n-1]
# -*- coding: utf-8 -*-
# 方法2 生成器
from StringIO import StringIO class Solution:
# @param {integer} n
# @return {string}
def countAndSay(self, n):
s = []
s.append('')
for i in range(1, n):
a = s[-1]
b = StringIO(a)
c = ''
for i in self._tmp(b):
c += str(len(i)) + i[0]
s.append(c)
return s[n-1] def _tmp(self, stream):
tmp_buf = []
while True:
ch = stream.read(1)
if not ch:
yield tmp_buf
break
if not tmp_buf:
tmp_buf.append(ch)
elif ch == tmp_buf[-1]:
tmp_buf.append(ch)
else:
yield tmp_buf
tmp_buf = [ch,]