学步园

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 n^th sequence.

Note: The sequence of integers will be represented as a string.

思路：

依次扫描之前生成的字符串即可。用一个vector来保存之前的结果，便于之后计算。

题解：

class Solution {
public:
    // save previous history for accelerated calculation
    vector<string> history;
    
    Solution()
    {
        history.emplace_back(string("1"));
    }
    
    string generate_seq(const string& in)
    {
        string generated;
        char scratch[64];
        char current = in[0];
        int count = 0;
        
        auto commit = [&]()
        {
            sprintf(scratch, "%d%c", count, current);
            generated += scratch;
        };
        
        for(auto ch : in)
            if (ch != current)
            {
                // we met another character
                commit();

                count = 1;
                current = ch;
            }
            else
                ++count;
        
        commit();   // commit the last continuous char accumulation
        return generated;
    }
    
    string countAndSay(int n) 
    {
        while(n-1 >= history.size())
            // exploit the r-value reference
            history.emplace_back(generate_seq(history.back()));
            
        return history[n-1];
    }
};