LeetCode刷题Java版038.外观数列

作者：沉默王二
发布时间：2022-09-07T11:05:24.872+0800

---

038.外观数列

题意

给定一个正整数 n ，输出外观数列的第 n 项。

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

还是不明白「外观数列」是什么鬼？

你可以将其视作是由递归公式定义的数字字符串序列：

• 1 <= n <= 30

还是不明白「外观数列」是什么鬼？

我们用一个例子来说明：

比如数列113334422，我们可以描述成 两个一 三个三 两个四 两个二，然后再把这个描述转化成数字——也就是21334422。

这就是「外观数列」的意义。

难度

中等

示例

下面列出了countAnySay(n)，n = 1-5的情况。

n = 1     countAnySay(n) = "1"

n = 3     countAnySay(n) = "21"n = 4     countAnySay(n) = "1211"n = 5     countAnySay(n) = "111221"

分析

这题最困难的地方就在于读懂题意，其实就是让我们对最开始1描述之后的结果，再描述n - 1次。

也就是一直重复 描述字符串 这个过程，并且记录描述的结果，作为下次要描述的字符串。

那么这样子我们只需要对每个字符统计出一共有多少个连续的即可。

实现方式很多，这里采用两个下标lef和rig的方式来实现，两个下标一开始都在同一个位置，如果一样，则向后移动rig下标，如果不一样，则停止，这时候lef处的字符有多少个，只需要rig - lef即可，然后再将lef下标直接移动到rig的位置即可。

class Solution {

        StringBuilder res = new StringBuilder();        int lef = 0,rig = 0;        while(rig < str.length()){            while(rig < str.length() && str.charAt(rig) == str.charAt(lef))                rig++;            res.append(rig - lef);            res.append(str.charAt(lef));            lef = rig;        }        return res.toString();    }    public String countAndSay(int n) {        if(n == 0)            return "";        String res = "1";        for(int i = 2;i <= n;i++)            res = func(res);        return res;    }}

速度也非常不错

但是还有一种取巧的方法，注意题目给出的数据范围1 <= n <= 30。

那么……

我们其实可以在本地把所有的答案都跑出来，然后 按“需”回答 即可，是的，也就是所谓的——打表。

            "","1",

"21","1211","111221","312211","13112221","1113213211","31131211131221","13211311123113112211","11131221133112132113212221","3113112221232112111312211312113211","1321132132111213122112311311222113111221131221",...

这样子确实可以非常快，但是我们观察一下countAndSay(i)的长度，虽然不是严格的单调递增，但是确实是有着递增的趋势，所以最终的代码长度会比较长，我也就没有再往后贴出来。

总结

本题主要考察对题目的阅读理解，以及对 递归调用 这一重要知识点的应用，只要能理解题意，本题就是一道切切实实的递归入门题。

力扣链接：https://leetcode.cn/problems/count-and-say/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 760 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

038.外观数列

题意

给定一个正整数 n ，输出外观数列的第 n 项。

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

还是不明白「外观数列」是什么鬼？

你可以将其视作是由递归公式定义的数字字符串序列：

• 1 <= n <= 30

还是不明白「外观数列」是什么鬼？

我们用一个例子来说明：

比如数列113334422，我们可以描述成 两个一 三个三 两个四 两个二，然后再把这个描述转化成数字——也就是21334422。

这就是「外观数列」的意义。

难度

中等

示例

下面列出了countAnySay(n)，n = 1-5的情况。

n = 1     countAnySay(n) = "1"

n = 3     countAnySay(n) = "21"n = 4     countAnySay(n) = "1211"n = 5     countAnySay(n) = "111221"

分析

这题最困难的地方就在于读懂题意，其实就是让我们对最开始1描述之后的结果，再描述n - 1次。

也就是一直重复 描述字符串 这个过程，并且记录描述的结果，作为下次要描述的字符串。

那么这样子我们只需要对每个字符统计出一共有多少个连续的即可。

实现方式很多，这里采用两个下标lef和rig的方式来实现，两个下标一开始都在同一个位置，如果一样，则向后移动rig下标，如果不一样，则停止，这时候lef处的字符有多少个，只需要rig - lef即可，然后再将lef下标直接移动到rig的位置即可。

class Solution {

        StringBuilder res = new StringBuilder();        int lef = 0,rig = 0;        while(rig < str.length()){            while(rig < str.length() && str.charAt(rig) == str.charAt(lef))                rig++;            res.append(rig - lef);            res.append(str.charAt(lef));            lef = rig;        }        return res.toString();    }    public String countAndSay(int n) {        if(n == 0)            return "";        String res = "1";        for(int i = 2;i <= n;i++)            res = func(res);        return res;    }}

速度也非常不错

但是还有一种取巧的方法，注意题目给出的数据范围1 <= n <= 30。

那么……

我们其实可以在本地把所有的答案都跑出来，然后 按“需”回答 即可，是的，也就是所谓的——打表。

            "","1",

"21","1211","111221","312211","13112221","1113213211","31131211131221","13211311123113112211","11131221133112132113212221","3113112221232112111312211312113211","1321132132111213122112311311222113111221131221",...

这样子确实可以非常快，但是我们观察一下countAndSay(i)的长度，虽然不是严格的单调递增，但是确实是有着递增的趋势，所以最终的代码长度会比较长，我也就没有再往后贴出来。

总结

本题主要考察对题目的阅读理解，以及对 递归调用 这一重要知识点的应用，只要能理解题意，本题就是一道切切实实的递归入门题。

力扣链接：https://leetcode.cn/problems/count-and-say/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 760 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

038.外观数列

题意

给定一个正整数 n ，输出外观数列的第 n 项。

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

还是不明白「外观数列」是什么鬼？

你可以将其视作是由递归公式定义的数字字符串序列：

• 1 <= n <= 30

还是不明白「外观数列」是什么鬼？

我们用一个例子来说明：

比如数列113334422，我们可以描述成 两个一 三个三 两个四 两个二，然后再把这个描述转化成数字——也就是21334422。

这就是「外观数列」的意义。

难度

中等

示例

下面列出了countAnySay(n)，n = 1-5的情况。

n = 1     countAnySay(n) = "1"

n = 3     countAnySay(n) = "21"n = 4     countAnySay(n) = "1211"n = 5     countAnySay(n) = "111221"

分析

这题最困难的地方就在于读懂题意，其实就是让我们对最开始1描述之后的结果，再描述n - 1次。

也就是一直重复 描述字符串 这个过程，并且记录描述的结果，作为下次要描述的字符串。

那么这样子我们只需要对每个字符统计出一共有多少个连续的即可。

实现方式很多，这里采用两个下标lef和rig的方式来实现，两个下标一开始都在同一个位置，如果一样，则向后移动rig下标，如果不一样，则停止，这时候lef处的字符有多少个，只需要rig - lef即可，然后再将lef下标直接移动到rig的位置即可。

class Solution {

        StringBuilder res = new StringBuilder();        int lef = 0,rig = 0;        while(rig < str.length()){            while(rig < str.length() && str.charAt(rig) == str.charAt(lef))                rig++;            res.append(rig - lef);            res.append(str.charAt(lef));            lef = rig;        }        return res.toString();    }    public String countAndSay(int n) {        if(n == 0)            return "";        String res = "1";        for(int i = 2;i <= n;i++)            res = func(res);        return res;    }}

速度也非常不错

但是还有一种取巧的方法，注意题目给出的数据范围1 <= n <= 30。

那么……

我们其实可以在本地把所有的答案都跑出来，然后 按“需”回答 即可，是的，也就是所谓的——打表。

            "","1",

"21","1211","111221","312211","13112221","1113213211","31131211131221","13211311123113112211","11131221133112132113212221","3113112221232112111312211312113211","1321132132111213122112311311222113111221131221",...

这样子确实可以非常快，但是我们观察一下countAndSay(i)的长度，虽然不是严格的单调递增，但是确实是有着递增的趋势，所以最终的代码长度会比较长，我也就没有再往后贴出来。

总结

本题主要考察对题目的阅读理解，以及对 递归调用 这一重要知识点的应用，只要能理解题意，本题就是一道切切实实的递归入门题。

力扣链接：https://leetcode.cn/problems/count-and-say/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 760 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412