[LeetCode]37. 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.

解法1：n=1时结果为“1”；n>=2时，后一个string由前一个string的连续相同字符和其数目组成。因此可以先记录下前一个string的组成情况，然后据此设置好当前string即可。

class Solution {
public:
    string countAndSay(int n) {
        string sf = "1";
        for (int i = 2; i <= n; ++i)
        {
            vector< pair<char, int> > vp = getDistrib(sf);
            string sn = "";
            for (vector< pair<char, int> >::iterator iter = vp.begin(); iter != vp.end(); ++iter)
            {
                sn += (char)(iter->second + '0');
                sn += iter->first;
            }
            sf = sn;
        }
        return sf;
    }
private:
    vector < pair<char, int> > getDistrib(const string& str)
    {
        vector< pair<char, int> > res;
        int s = str.size();
        if (s != 0)
        {
            res.push_back(make_pair(str[0], 1));
            for (int i = 1; i < s; ++i)
            {
                if (str[i] == str[i - 1])
                    res.back().second++;
                else
                    res.push_back(make_pair(str[i], 1));
            }
        }
        return res;
    }
};

解法2：可以在遍历前一个string时即可获得其组成情况，同时设置当前string，这样不需要额外的vector来存储。

class Solution {
public:
    string countAndSay(int n) {
        string sf = "1"; //前一个string
        for (int i = 2; i <= n; ++i)
        {
            string sn = ""; //当前string
            int count = 1, j = 1;
            for (; j < sf.size(); j++)
            {
                if (sf[j] == sf[j - 1])
                    ++count;
                else
                {
                    sn += (char)(count + '0');
                    sn += sf[j - 1];
                    count = 1; //注意此时新的字符开始，初始化count
                }
            }
            sn += (char)(count + '0'); //将最后一组连续字符加入到当前string的末尾
            sn += sf[j - 1];
            sf = sn;
        }
        return sf;
    }
};

我们可以发现字符串中永远只会出现1,2,3这三个字符，假设第k个字符串中出现了4，那么第k-1个字符串必定有四个相同的字符连续出现，假设这个字符为1，则第k-1个字符串为x1111y。第k-1个字符串是第k-2个字符串的读法，即第k-2个字符串可以读为“x个1,1个1,1个y” 或者“*个x,1个1,1个1,y个*”，这两种读法分别可以合并成“x+1个1,1个y” 和 “*个x，2个1，y个*”，代表的字符串分别是“(x+1)11y” 和 "x21y"，即k-1个字符串为“(x+1)11y” 或 "x21y"，不可能为“x1111y”。