一. 题目信息

1. 描述

给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
题目链接：https://leetcode-cn.com/problems/count-and-say/

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"

二. 解法

1. 模拟

①. 复杂度分析

时间复杂度：O(n^2)
空间复杂度：O(n^2)

②. c++解法

class Solution {
public:
    string countAndSay(int n) {
        vector<string> ans;
        ans.resize(n);
        ans[0] = "1";
        for (int i = 1; i < n; i++) {
            char ch = ans[i - 1][0];
            int num = 0;
            for (int j = 0; j < ans[i - 1].size(); j++) {
                if (j == ans[i - 1].size() - 1) {
                    num++;
                    string s = to_string(num) + ch;
                    ans[i] += s;
                    break;
                }
                if (ans[i - 1][j] != ans[i - 1][j + 1]) {
                    num++;
                    string s = to_string(num) + ch;
                    ans[i] += s;
                    ch = ans[i - 1][j + 1];
                    num = 0;
                } else {
                    num++;
                }
            }
        }
        return ans[n - 1];
    }
};