38. Count and Say

November 15, 2016

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

北邮教务系统评教脚本

Published on September 17, 2017

72.Edit distance

Published on September 17, 2017