Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Count and Say

Leetcode algorithms 第 38 题: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次新序列。从一个序列产生下一个序列时,逐个遍历该序列的每个元素,如果跟前面的元素相等,则计数值加一,否则添加到结果中,并初始化新的计数值和数值。

这里使用c++的stringstream把数字输入到字符串中,利用其str()函数得到最终的字符串。

具体代码如下:

class Solution
{
public:
    string next(string s)
    {
        stringstream ss;
        int count = 1;
        char cur = s[0];
        
        for (int i = 1; i < s.length(); i++)
            if(s[i] == cur)
                count ++;
            else
            {
                ss << count << cur;
                count = 1, cur = s[i];
            }
        ss << count << cur;
        return ss.str();
    }
    
    string countAndSay(int n)
    {
        string s = "1";
        while (--n) s = next(s); //重复n-1次
        return s;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论