LeetCode38——Count and Say-蒲公英云

LeetCode38——Count and Say

青旅半醒 2022-08-09 09:21 282阅读 0赞

LeetCode38——Count and Say

上一题对我来说实在太凶残了，所以我还是缓缓先做38题好了。。。

题意：

可以理解为求一个数组的第n项，而这个数组的通项公式可以这样理解：

第1项：1

第2项：11

第3项：21

第4项：1211

第5项：111221

第6项：312211

…

第n项：第n-1项的数字串从左到右读出来。

怎么说呢？比如说第2项是11，因为第1项是1，读起来就是1个1，所以第2项的11前一个1表示后一个1的计数，以此类推。

那么我们求第n项，就要知道第n-1项，要知道n-1项就要知道第n-2项……

反过来说，我们设计一个函数可以求出某数字串的下一个数字串，只要调用该函数n-1次就能得到我们想要的结果。

代码：

class Solution {
private:
    string Count(string s)//计算下一个序列
    {
        string result;
        int i=0;
        int count ;
        while (i < s.size())
        {
            count = 1;
            char temp;
            if (s[i] == s[i + 1])
            {
                while (s[i] == s[i + 1])
                {
                    count++;
                    i++;
                }
                temp = count + '0';
                result = result + temp + s[i];
                i++;
            }
            else
            {
                temp = '1';
                result = result + temp + s[i];
                i++;
            }
        }
        return result;
    }
public:
    string countAndSay(int n) {
        if (n == 1)
            return "1";
        string s = "1";
        while (--n)
        {
            s = Count(s);
        }
        return s;
    }
};