# 外观数列

给定一个正整数 n ，输出外观数列的第 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"

 

提示：

给定一个正整数 n ，输出外观数列的第 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"

 

提示：

以下错误的选项是？

## aop ### before ```cpp #include using namespace std; ``` ### after ```cpp int main() { Solution sol; string res; int n = 4; res = sol.countAndSay(n); cout << res; return 0; } ``` ## 答案 ```cpp class Solution { public: string countAndSay(int n) { if (n == 1) return "1"; string last = countAndSay(n - 1); string ans; int length = last.length(), cnt = 1; for (int i = 0; i < length; i++) { if (i + 1 == length || last[i] != last[i + 1]) { ans.push_back(cnt + '0'); ans.push_back(last[i]); cnt++; } } return ans; } }; ``` ## 选项 ### A ```cpp class Solution { public: string countAndSay(int n) { string s = "1"; char num[10] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}; for (int i = 1; i < n; i++) { string news = ""; int l = s.length(), count = 0; char thischar = '*'; for (int j = 0; j < l - 1; j++) { if (s[j] == s[j + 1]) { thischar = s[j]; count++; } else if (s[j] != s[j + 1]) { if (count == 0) { count = 1; thischar = s[j]; news = news + num[count]; news = news + thischar; count = 0; } else if (count != 0) { count++; news = news + num[count]; news = news + thischar; count = 0; } } } if (s[l - 2] == s[l - 1]) { count++; news = news + num[count]; news = news + thischar; } else if (s[l - 2] != s[l - 1]) { count++; news = news + num[count]; news = news + s[l - 1]; } s = news; } return s; } }; ``` ### B ```cpp class Solution { public: string countAndSay(int n) { string ans = "11"; if (n == 1) { return "1"; } else if (n == 2) { return "11"; } else { for (int i = 3; i <= n; i++) { int num = 1, flag = 0; string temp = ans; char last = temp[0]; for (int j = 1; j < temp.size(); j++) { if (last == temp[j]) { num++; } else { if (flag == 0) { ans = to_string(num) + to_string(last - '0'); } else { ans += to_string(num) + to_string(last - '0'); } flag = 1; last = temp[j]; num = 1; } if (j + 1 == temp.size()) { if (flag == 0) { ans = to_string(num) + to_string(last - '0'); } else { ans += to_string(num) + to_string(last - '0'); } } } } } return ans; } }; ``` ### C ```cpp class Solution { public: string countAndSay(int n) { if (n == 1) { return "1"; } string tmp = countAndSay(n - 1); string result; int length = tmp.length(); int m = tmp[0] - '0'; int count = 1; for (int i = 1; i < length; i++) { if (m == (tmp[i] - '0')) { count++; } else { result.push_back(count + '0'); result.push_back(m + '0'); m = tmp[i] - '0'; count = 1; } } result.push_back(count + '0'); result.push_back(m + '0'); return result; } }; ```