leetcode筆記：Count and Say

leetcode筆記：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.

二.題目分析

題目的內容很多，其實就是根據一個數的讀法，組合出下一個數，比如11，讀作2(個)1，因此下個數是21；同理，21讀作1(個)2、1(個)1，因此下個數是1211…

根據題意，發現該題沒有什麼高級的技巧，代碼中主要使用了string和stringstream，需要加入頭文件#include ，#include ，關於string和stringstream的用法，可參考：http://blog.csdn.net/xw20084898/article/details/21939811 。該程序只是實現了對題目要求的模擬，然後輸出結果。

三.示例代碼

#include 
#include 
using namespace std;

class Solution
{
public:
    string CountAndSay(int n)
    {
        string result = 1;

        while (--n)
            result = theNextStr(result);
        return result;
    }

private:
    string theNextStr(const string& str)
    {
        if (str.empty())
            return string();
        stringstream result;
        int strSize = str.size();
        int count = 1; // 計數

        for (int Index = 0; Index < strSize - 1; Index++)
        {
            if (str[Index] == str[Index + 1])
                count++;
            else
            {
                result << count << str[Index];
                count = 1;
            }
        }
        result << count << str[strSize - 1]; // 最後一位
        return result.str();
    }
};

四.小結

需要好好學習一下string和stringstream的用法。