大家好，我是练习时长两年半的LeetCode爱好者，喜欢唱跳rap

五分钟学算法

发布于 2019-07-15 11:21:53

5430

发布于 2019-07-15 11:21:53

文章被收录于专栏：五分钟学算法五分钟学算法

今天分享一道很 rap 的算法题目。

题目来源于 LeetCode 上第 38 号问题：报数。题目难度为 Easy，目前通过率为 50.7% 。

题目描述

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1 被读作 "one 1" ("一个一") ，即 11。 11 被读作 "two 1s" ("两个一"），即 21。 21 被读作 "one 2"， "one 1"（"一个二" , "一个一") ，即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。

示例 1:

输入: 1
输出: "1"

示例 2:

输入: 4
输出: "1211"

题目解析

这道题目的难点在于题目的理解。

我看了一下 LeetCode 的评论区，绝大部分人都是在吐槽没看懂题目。题目的确比较绕，读了几篇才看明白。

题目讲的是后续的相应的 输出数字 依据的是它之前的 输出数字：

1：当它是 1 的时候，我们就返回字符串 '1'（1）
2：当它是 2 的时候，我们就对之前的 1 报数，即 1 个 1（11）
3：当它是 3 的时候，我们就对之前的 2 报数，即 2 个 1（21）
4：当它是 4 的时候，我们就对之前的 3 报数，即 1 个 2 、 1 个 1（1211）
5：当它是 5 的时候，我们就对之前的 4 报数，即 1 个 1 、 1 个 2 、 2 个 1（111221）
6：当它是 6 的时候，我们就对之前的 5 报数，即 3 个 1 、 2 个 2 、1 个 1（312211）
以此类推……

看懂了题意，借助递归的概念，这道题的基本上就很好求解了。

动画描述

以报数字 6 为例。

代码实现

// c++
class Solution {
public: string countAndSay(int n) {
        //递归终止的条件
        if(n == 1) return "1";
        string prevResult = countAndSay(n-1);
        int count = 1;//计数
        string nowResult;//存放结果
        for(int i = 0 ; i < prevResult.length();i++){
            //统计有多少个相同数字
            if(prevResult[i] == prevResult[i+1]){
                count++;
                continue;
            }else{
                if( prevResult[i] != prevResult[i + 1]) {
                    nowResult += to_string(count) + prevResult[i];
                    //重置开始统计其他的数字
                    count = 1;
                }
            }
        }
       return nowResult;
    }
};

END

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-07-10，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自五分钟学算法微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度