鲁迅曾说，我以前很讨厌刷题，但在二哥这里我找到了刷题的快乐，他写的每一个题解我都能轻松掌握，这可太棒了。

题意

「外观数列」是一个数位字符串序列，由递归公式定义：

• countAndSay(1) = "1"
• countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。

行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。

例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。

给定一个整数 n ，返回外观数列的第 n 项。

难度

中等

示例 1

• 输入：n = 4
• 输出："1211"

解释：

• countAndSay(1) = "1"
• countAndSay(2) = "1" 的行程长度编码 = "11"
• countAndSay(3) = "11" 的行程长度编码 = "21"
• countAndSay(4) = "21" 的行程长度编码 = "1211"

示例2

• 输入：n = 1
• 输出："1"

解释：这是基本情况。

分析

首先，我们需要理解题目的意思。尤其是这个「外观数列」是什么鬼？

说实话题目上信息这么多，我就看懂了“例如”那一段：2222，那么就是4个2， 可以压缩为 42。

好，我们来给【外观数列】下一个定义：

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

好像还是不太懂。什么是对前一项的描述？

不着急，我们先用一个例子来带入一下：

比如数列113334422，我们可以描述成 两个一 三个三 两个四 两个二，然后再把这个描述转化成数字——21332422。

这是「外观数列」，能理解吧。

理解什么是【外观数列】后，我们需要再搞清楚题目中的 n 是什么意思？“序列中的每一项都是对前一项的描述”又是什么意思？

好，说句废话，n 是指第 n 项，那第一项是什么呢？

第一项是 1，因为题目中给出了 countAndSay(1) = "1"。

那么第二项呢？

第二项是对第一项的描述，也就是 1 的描述，那么 1 的描述是什么呢？

1 的描述是 1 个 1，所以第二项是 11。

第三项呢？第四项呢？第五项呢？

1. 1
2. 11 （一个 1）