No.38 外观数列

题目：给定一个正整数，输出外观数列的第项。
注意，整数序列中的每一项将表示为一个字符串。
外观数列是一个整数序列，从数字1开始，序列中的每一项都是对前一项的描述。前五项如下：

1.     1       第一项是数字1
2.     11             描述前一项，1个1，记作11
3.     21             描述前一项，2个1，记作21
4.     1211       描述前一项，1个2和1个1，记作1211
5.     111221     描述前一项，1个1和1个2和2个1，记作111221

例：

输入: 1
输出: "1"
解释：这是一个基本样例。

输入: 4
输出: "1211"
解释：当 n = 3 时，序列是 "21"，其中我们有 "2" 和 "1" 两组，"2" 可以读作 "12"，也就是出现频次 = 1 而 值 = 2；类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起，也就是 "1211"。

题解：
一、暴力法

class Solution:
    def countAndSay(self, n: int) -> str:
        def next_num(tmp):
            res = ""
            i = 0
            tmp_n = len(tmp)
            while i < tmp_n:
                count = 1
                while i < tmp_n - 1 and tmp[i] == tmp[i+1]:
                    count += 1
                    i += 1
                res += (str(count) + tmp[i])
                i += 1
            return res

        res = "1"
        for i in range(1, n):
            res = next_num(res)
        return res

作者：powcai
链接：https://leetcode-cn.com/problems/count-and-say/solution/zhi-jie-tui-mo-ni-guo-cheng-by-powcai/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

模拟了前后字符串的递推过程，没什么好说的。

二、优化暴力法

class Solution:
    def countAndSay(self, n: int) -> str:
        a = ['1']
        for i in range(n-1):
            b = 1
            a.append('')
            aa = []
            for j in range(len(a)-1):
                if a[j] == a[j+1]:
                    b += 1
                else:
                    aa.append(str(b))
                    aa.append(str(a[j]))
                    b = 1
            a = aa
        return ''.join(a)

作者：yi-li-dan-lu-fen
链接：https://leetcode-cn.com/problems/count-and-say/solution/jian-dan-zhi-guan-da-bai-97-by-yi-li-dan-lu-fen/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

三、itertools.groupby()

class Solution:
    def countAndSay(self, n: int) -> str:
        result = '1'
        for i in range(1, n):
            result = ''.join([str(len(list(g))) + k for k, g in groupby(result)])
        return result

知识点：
groupby函数
作用1：数据分组
作用2：分组后进行组内运算

from itertools import groupby
x='111112222111'
for i,num in groupby(x):
    print(i,len(list(num)))

输出：
1 5
2 4
1 3

from itertools import groupby
x='111112222111'
for _,num in groupby(x):
    print(list(num))

输出：
['1', '1', '1', '1', '1']
['2', '2', '2', '2']
['1', '1', '1']

没什么好说的，自行体会即可。注意groupby返回的是一个iterable对象，需要迭代访问。