LeetCode程序员面试金典：外观数列

　　题目：

　　给定一个正整数 n ，输出外观数列第一 n 项。

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

　　您可以将其视为递归公式定义的数字字符串序列：

　　countAndSay(1) = "1"

　　countAndSay(n) 是对 countAndSay(n-1) 描述，然后转换为另一个数字字符串。

　　前五项如下：

　　1. 1

　　2. 11

　　3. 21

　　4. 1211

　　5. 111221

　　第一项是数字 1

　　描述前一项，这个数字是 1 即 “ 一 个 1 ”，记作 "11"

　　描述前一项，这个数字是 11 即 “ 二 个 1 ” ，记作 "21"

　　描述前一项，这个数字是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"

　　描述前一项，这个数字是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

　　要 描述 一个数字字符串，首先要把字符串分成 最小 数量组，每个组都是最连续的 相同字符 组成。然后，对于每个组，首先描述字符的数量，然后描述字符，形成一个描述组。将描述转换为数字字符串，用数字替换每组中的字符数量，然后连接所有描述组。

　　例如，数字字符串 "3322251" 如下图所示：

　　示例 1：

　　输入：n = 1

　　输出："1"

　　解释:这是一个基本的例子。

　　示例 2：

　　输入：n = 4

　　输出："1211"

　　解释：

　　countAndSay(1) = "1"

　　countAndSay(2) = 读 "1" = 一 个 1 = "11"

　　countAndSay(3) = 读 "11" = 二 个 1 = "21"

　　countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

　　代码实现：class Solution { public String countAndSay(int n) { String str = "1"; for (int i = 2; i <= n; ++i) { StringBuilder sb = new StringBuilder(); int start = 0; int pos = 0; while (pos < str.length()) { while (pos < str.length() && str.charAt(pos) == str.charAt(start)) { pos++; } sb.append(Integer.toString(pos - start)).append(str.charAt(start)); start = pos; } str = sb.toString(); } return str; }}