【LeetCode】 38. Count and Say

Description

The count-and-say sequence is the sequence of integers with the first five terms as following:

1. ​​​​​​​1
   

2. ​​​​​​​11
   

3. ​​​​​​​21
   

4. ​​​​​​​1211
   

5. ​​​​​​​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 where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

"數說數列"是一個數列，它的的前五項為：

1. ​​​​​​​1
   

2. ​​​​​​​11
   

3. ​​​​​​​21
   

4. ​​​​​​​1211
   

5. ​​​​​​​111221
   

1 讀作"一個一"，所以表示為 11
11 讀作"兩個一"，所以表示為 21
21 讀作"一個二然後一個一"，所以表示為 1211

給予一個整數n，且1 ≤ n ≤ 30，請產生第n個數說數列的項。

注意：每一項回傳的型態請轉為字串。

Example:

Example 1:

Input: 1
Output: "1"


Example 2:

Input: 4
Output: "1211"

Solution

• 這一題難在要看懂題目…
• 去做字串分析，觀察連續相同的字元有幾個，然後拼接成新的字串即可。

Code

class Solution {
public:
    
    string nextStr(string s)
    {
        string ans = "";
        char c = s.front();
        int count=1;
        for(int i=1;i<s.size();i++)
        {
            if(c==s[i])
                count++;
            else
            {
                ans+=(char)(count+'0');
                ans+=c;
                
                c=s[i];
                count = 1;
            }
        }
        ans+=(char)(count+'0');
        ans+=c;
        return ans;
    }
    
    string countAndSay(int n) {
        string ans="1";
        for(int i=1;i<n;i++)
            ans=nextStr(ans);
        return ans;
    }
};

tags: LeetCode C++