標簽： C++ 算法 LeetCode 字符串 遞歸

每日算法——leetcode系列

問題 Count and Say

Difficulty: Easy

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" or21.
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 countAndSay(int n) {
        
    }
};

翻譯

數(shù)數(shù)并報數(shù)

難度系數(shù)：容易

數(shù)數(shù)并報數(shù)順序按如下規(guī)律開始遞增：
1，11，21，1211，111221，……

1 讀作“1個1”得11
11 讀作“2個1”得21
21 讀作“1個2、1個1”得1211

給定一個整數(shù)n，生成第n個序列。

注意：數(shù)字序列應(yīng)該用字符串表示。

思路

此題我覺得英文的表面意思跟實際要的不一樣。
題意：數(shù)上次字符串中的連續(xù)出現(xiàn)數(shù)值的個數(shù), 將這些字符串拼接起來

• n=1時，輸出字符串1；
• n=2時，因為上次字符串1，1連續(xù)出現(xiàn)1次，就是1個1，所以輸出11；
• n=3時，由于上次字符串11，其中1連續(xù)出現(xiàn)兩次，就是2個1，所以輸出21；
• n=4時，由于上次字符串是21，其中2出現(xiàn)1次，1出現(xiàn)1次，所以輸出1211；
• n=5時，由于上次字符串1211，第個1連續(xù)出現(xiàn)1次為11，第二個2連續(xù)出現(xiàn)1次為12，第三個1跟第四個1連續(xù)出現(xiàn)了2次，為21，所以輸出111221

代碼

#include <iostream>
#include <sstream>
using namespace std;

class Solution {

public:
     string countAndSay(int n) {
        if(n == 1){
            return "1";
        }
        //遞歸調(diào)用
         string str = countAndSay(n-1);
        int len = static_cast<int>(str.length());
        int count = 1;
        stringstream s;
        for(int i = 0; i < len; ++i){
            if(str[i] == str[i+1]){
                count++;
            } else {
                s << count << str[i];

                count = 1;
            }
        }
        return s.str();
    }
};