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

点击蓝色“五分钟学算法”关注我哟

加个“星标”,一起学算法

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

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

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

题目描述

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

1. 1
2. 11
3. 21
4. 1211
5. 111221

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 报数,即 1111

  • 3:当它是 3 的时候,我们就对之前的 2 报数,即 2121

  • 4:当它是 4 的时候,我们就对之前的 3 报数,即 12111211

  • 5:当它是 5 的时候,我们就对之前的 4 报数,即 111221111221

  • 6:当它是 6 的时候,我们就对之前的 5 报数,即 312211312211

  • 以此类推……

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

动画描述

以报数字 6 为例。

代码实现

// c++
class Solution {
publicstring countAndSay(int n) {
        //递归终止的条件
        if(n == 1return "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

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

 原 创 热 文 推 荐 


毕业十年后,我忍不住出了一份程序员的高考试卷

一道腾讯面试题:厉害了我的杯

十大经典排序算法动画与解析,看我就够了!(配代码完全版)

这或许是东半球分析十大排序算法最好的一篇文章

面试官,我会写二分查找法!对,没有 bug 的那种!


大家好,我是练习时长两年半的LeetCode爱好者,喜欢唱跳rap
你点的每个“在看”,我都认真当成了喜欢


本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 大家好,我是练习时长两年半的LeetCode爱好者,喜欢唱跳rap

我还会在以下平台发布内容

GitHub 哔哩哔哩