Count and Say [LeetCode 38]

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 n^th 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实现

 1 # -*- coding: utf-8 -*-
 2 # 方法1 栈
 3 
 4 class Solution:
 5     # @param {integer} n
 6     # @return {string}
 7     def countAndSay(self, n):
 8         s = []    # 列表保存第n次结果
 9         s.append('1')
10         if n == 1: return s[0]
11         for i in range(1, n):
12             stack = []    # 栈用于存储每次pop的元素
13             res = []    # 每解析完一组相同字符字串，将str(长度)，字符存入
14             last = list(s[-1])    # 上一次的结果
15             while True:
16                 try:
17                     end = last.pop()    # 取出列表右端元素
18                 except:    # 若列表为空，说明已经遍历完，统计栈内元素个数，跳出循环
19                     res.insert(0, str(len(stack)))    
20                     res.insert(1, stack[-1])
21                     break
22                 if not stack:    # 若栈为空，则取出的元素直接入栈，进入下一次循环
23                     stack.append(end)
24                     continue
25                 if stack[-1] == end:    # 若栈不为空，判断取出元素是否和栈内元素相同，相同则入栈
26                     stack.append(end)
27                 else:    # 不同，则统计栈内元素，然后清空栈，将新元素入栈
28                     res.insert(0, str(len(stack)))
29                     res.insert(1, stack[-1])
30                     stack = []
31                     stack.append(end)
32             s.append(''.join(res))    # 拼接长度和字符
33         return s[n-1]

 1 # -*- coding: utf-8 -*-
 2 #  方法2 生成器
 3 from StringIO import StringIO
 4 
 5 class Solution:
 6     # @param {integer} n
 7     # @return {string}
 8     def countAndSay(self, n):
 9         s = []
10         s.append('1')
11         for i in range(1, n):
12             a = s[-1]
13             b = StringIO(a)
14             c = ''
15             for i in self._tmp(b):
16                 c += str(len(i)) + i[0]
17             s.append(c)
18         return s[n-1]
19             
20     def _tmp(self, stream):
21         tmp_buf = []
22         while True:
23             ch = stream.read(1)
24             if not ch:
25                 yield tmp_buf
26                 break
27             if not tmp_buf:
28                 tmp_buf.append(ch)
29             elif ch == tmp_buf[-1]:
30                 tmp_buf.append(ch)
31             else:
32                 yield tmp_buf
33                 tmp_buf = [ch,]