前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 图解 | 38. 外观数列

LeetCode 图解 | 38. 外观数列

作者头像
五分钟学算法
发布2020-05-19 17:21:20
5360
发布2020-05-19 17:21:20
举报
文章被收录于专栏:五分钟学算法

作者:孤磊

题目来源于 LeetCode 上第 38 号问题:外观数列。题目难度为 Easy。

题目描述

「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。前五项如下:

代码语言:javascript
复制
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:

代码语言:javascript
复制
输入: 1
输出: "1"
解释:这是一个基本样例。

示例 2:

代码语言:javascript
复制
输入: 4
输出: "1211"
解释:当 n = 3 时,序列是 "21",其中我们有 "2" 和 "1" 两组,"2" 可以读作 "12",也就是出现频次 = 1 而 值 = 2;类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起,也就是 "1211"。

题目解析

送迭法:当 n = 1 的时候序列为 1,n = 2的时候为 11,每一个数字对应的都是固定的,都是根据上个数字计算而来的结果。

那这样就可以利用送迭法来进行每一轮的计算,完成后将结果传递到下一轮计算过程。直到符合 n 的条件为止。

动画描述

http://mpvideo.qpic.cn/0bf2r4aakaaawaajcxvw5zpfbd6dawhqabia.f10002.mp4?dis_k=309f97173d747be12baaaceb4e616428&dis_t=1589880033

代码实现

代码语言:javascript
复制
// 38. 外观数列
// https://leetcode-cn.com/problems/count-and-say
// 时间复杂度:O(n)
// 空间复杂度:O(1)
class Solution {
    public String countAndSay(int n) {
        String re;
        re=digui(2,n,"1");
        return re;
    }
    private String digui(int i  ,int n,String str){
        if (i>n){
            return str;
        }
        StringBuilder stringBuilder=new StringBuilder();
        char c=0;
        int num=0;
        for (char ch:str.toCharArray()) {
            if (ch!=c){
                char t= (char) (num+'0');
                stringBuilder.append(t);
                num=0;
                stringBuilder.append(c);
            }
            c=ch;
            num++;
        }
        stringBuilder.append((char)(num+'0'));
        stringBuilder.append(c);
        stringBuilder.delete(0,2);
        String s=digui(i+1,n,stringBuilder.toString());
        return s;
    }
}

复杂度分析

  • 空间复杂度:O(1)
  • 时间复杂度:O(1)
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-05-10,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 题目解析
  • 动画描述
  • 代码实现
  • 复杂度分析
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档