38. Count and Say

Description

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.

Analysis

这是一道在leetcode上有较大争议的一道题，原因在于它的描述方式确实不够准确，以至于我在开始读这道题时不知所云。

此外，这道题的generate the nth sequence.也造成了一定的困惑，这个n到底是从哪里开始算的呢？

实际上，这道题的题意是，最初有一个字符串"1",我们将其读作“one 1”，也就是”一个1”的意思。对于“11”,当然就是“两个1”啦，以此类推就可以得出n取其他值时应该由我们的函数生成的字符串了。

很显然，这是一个不断迭代的过程，我们只需要从第一个数字开始不断计数，如果之后的数字等于第一个数字，那么计数变量应该+1，否则，就应该将统计结果转换为字符串，使之成为结果的一部分，并且，在下一轮计数开始之前，切记将计数变量初始化为0.

迭代版的代码如下:

class Solution {
public:
    string countAndSay(int n) {
        if(n==1)
            return "1";
        string res="1";
        int count=0;
        while(--n){
            string tmp="";
            for(int i=0;i<res.size();++i){
                int count=1;
                while(i+1<res.size()&&res[i]==res[i+1]){
                    ++i;
                    ++count;
                }
                tmp+=to_string(count)+res[i];
            }
            res=tmp;
        }
        return res;
    }
};

关于n的计数问题，根据题目的意思，n==1时应该返回“1”,而不是“11”.

另外，也可以通过递归来解决这个问题。

最后，附上leetcode讨论区中关于此题的说明。

https://discuss.leetcode.com/topic/2068/how-to-proof-the-count-is-always-less-than-10

https://discuss.leetcode.com/topic/2264/examples-of-nth-sequence