4.1 外观数列（报数）
题目描述（第38题）
外观数列是一个整数序列，从数字1开始，序列中的每一项都是对前一项的描述。前5项如下。
1 被读作“one 1”(一个一)，即11。
11 被读作“two 1s”（两个一），即21。
21 被读作“one 2，one 1”（一个二，一个一)，即1211。
给定一个正整数n（1≤n≤30），输出外观数列的第n项。
注意：整数序列中的每一项将表示为一个字符串。
示例1
输入：1
输出："1"
解释：这是一个基本样例。
示例2
输入：4
输出："1211"
解释：当n=3时，序列是“21”，其中有“2”和“1”两组，“2”可以读作“12”，也就是出现频次为1，而值为2；类似于“1”可以读作“11”，所以答案是“12”和“11”组合在一起，也就是“1211”。
解法一 迭代法
思路
这道题目的英文标题为count and say，直译过来是计算并报数，与外观数列的描述相比，作者认为前者要形象许多。这是一种并不复杂的报数游戏，根据题意，11被读作“two 1s”(两个一），即21；21被读作“one 2，one 1”（一个二，一个一)，即1211，每次报数产生的新的字符串由原字符串的每个字符及其计数拼接构成。
从1到n的过程需要逐次报数，每次报数又需要从头到尾遍历上一次报数的结果，因此在这里使用双重循环是顺理成章的。
● 内层循环实现报数，即字符拼接过程。遍历数列，使用变量current_char和char_count记录正在报数的数字和出现次数。
➢ 如果当前数字和正在记录的数字一致，增加计数。
➢ 否则就进行一次报数，即将被记录数字和出现次数拼接在临时结果序列tmp中，同时将记录的数字替换为当前数字，将计数设置为1。
● 外层循环负责为下一次报数提供新的数列，并进行中间变量的初始化。
➢ 初始化tmp、current_char、char_count，并在内层循环结束时为末尾的数字进行一次报数。
➢ 将结果记录到ans中。
➢ 循环的最后一轮，被保存的结果就是我们需要的答案。
代码
复杂度分析
● 时间复杂度：计算规模随着迭代次数n及每次计算得到的字符串长度的变大而变大，因此时间复杂度为O(mn)，m为最后一次计算时的字符串长度。
● 空间复杂度：O(m)，m为最后一次计算时的字符串长度。
解法二 递归法
下面换一种思路，先不考虑具体如何报数，从1到n的数列产生逻辑很好地体现了递归思想。假设报数，即字符的拼接过程为函数do_string，我们可以很快得到递归解法的雏形。
剩下要做的无非是实现字符拼接逻辑do_string：依照题意遍历字符串，以当前记录中的字符为基准，遇到相同字符时记录字符个数；遇到不同的字符时打印计数和字符，并替换记录的字符；继续遍历直至末尾。
与前面已经列出的递归框架结合，我们可以很快地完成这道题目的解答。
代码
复杂度分析
● 递归次数随着输入值n的增加而增加，每次计算的规模随着字符串previous_string的变长而变大，因此时间复杂度为O(mn)，m为最后一次计算的字符串长度。
● 空间复杂度：由于使用了递归，递归函数的参数n每次减少1，因此空间复杂度为O(n+m)，m为最后一次计算时的字符串长度。