C++算法：報數

leetcode相關C++算法解答: https://github.com/Nereus-Minos/C_plus_plus-leetcode

題目：

報數序列是一個整數序列，按照其中的整數的順序進行報數，得到下一個數。其前五項如下：

1. 1

2. 11

3. 21

4. 1211

5. 111221

解釋：

1 被讀作 “one 1” (“一個一”) , 即 11。

11 被讀作 “two 1s” (“兩個一”）, 即 21。

21 被讀作 “one 2”, “one 1” （“一個二” , “一個一”) , 即 1211。

給定一個正整數 n（1 ≤ n ≤ 30），輸出報數序列的第 n 項。注意：整數順序将表示為一個字元串。

思路：

使用一個vecotrtemp1存儲每次報數的數，如第一次存1，第二次存的是11，…，每次通過vecotrtemp2來更新,當報數到n時，停止，并将temp1中數字轉換為字元串；

//求取下一次報數的數:每次判斷temp1[j]是否等于temp1[j+1]，等于則将計數器加1；不等于說明同一個數結束，此時将count和temp1[j]壓入temp2中。

代碼：

//思路：使用一個vecotr<int>temp1存儲每次報數的數，如第一次存1，第二次存的是11，....，每次通過vecotr<int>temp2來更新,當報數到n時，停止，并将temp1中數字轉換為字元串；
//求取下一次報數的數:每次判斷temp1[j]是否等于temp1[j+1]，等于則将計數器加1；不等于說明同一個數結束，此時将count和temp1[j]壓入temp2中。

class Solution {
public:
    string countAndSay(int n) {
        
        if(n == 1)
            return "1";
        
        vector<int> temp1, temp2;
        temp1.push_back(1);
        int count = 1;
        
        for(int i = 2; i<=n;i++)
        {
            for(int j = 0; j < temp1.size(); j++)
            {
               if((j+1 == temp1.size()) || ((j+1 < temp1.size()) && (temp1[j] != temp1[j+1])))
               {
                   temp2.push_back(count);
                   temp2.push_back(temp1[j]);
                   count = 1;
               }
               else if((j+1 < temp1.size()) && (temp1[j] == temp1[j+1]))
               {
                   count++;
               }
            }
            temp1 = temp2;
            temp2.clear();
        }
        
        //将數字轉為字元串
        string ret;
        for(int i = 0; i < temp1.size(); i++)
            ret.append(1, (temp1[i]+48));
        
        return ret;
    }
};