[Leetcode] 118. Count and Say

题目

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

解题之法

class Solution {
public:
    string getNext(string s)
    {
        if (s == "") return "1";
        string ans = "";
        int len = s.size(), cnt = 1; // 计数cnt初始为1，因为一旦出现一个数那至少是一次
        for (int i = 0; i < len; i++)
        {
            if (i+1 < len && s[i+1] == s[i])
            {
                cnt++;continue;
            }
            ans += cnt + '0'; // 和下面的s[i]要分开来加，否则会先进行字符串相加再到ans中
            ans += s[i];
            cnt = 1; //记录后记得将cnt恢复为1
        }
        return ans;
    }
    string countAndSay(int n) 
    {
        if (n == 0)
            return "";
        string ans = "";
        for (int i = 0; i < n; ++i) // 重复找n次next的就可以了
            ans = getNext(ans);
        return ans;
    }
};

分析

题目的意思是按照一定的规则出现数字，以字符串的形式。规定第一个是1，接下去就是按照前一个数的读法记录，所以第二个就是1个1，记录为11，那第三个就是对11的读法就是2个1，记录为21，第四个就是对21的读法，一个2一个1，记录为1211，以此类推。