LEETCODE 38. Count and Say 解题思路分析

题目大意:

外观数列

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

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"
解释:当 n = 3 时,序列是 "21",其中我们有 "2" 和 "1" 两组,"2" 可以读作 "12",也就是出现频次 = 1 而 值 = 2;类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起,也就是 "1211"。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=38

解题思路分析:

这是一道简单的递归问题,对于任意一个数字,它的外观数列取决于比他小1的数字,我们可以使用递归方法先求出比当前数字小1数字的外观数列,然后我们将此数列按照连续的相同数字来分组,比如11122112,我们可以分为111,22,11和2这四个部分然后我们将每个部分按照几个几的形式描述出来,即3个1,2个2,2个1,1个2,将它们连起来即是31 22 21 12,这一串数字就是当前数字的外观数列。最后,递归的终止条件是当前数字为1时,返回1即可。

实现代码:

public String countAndSay(int n) {
    if(n==1) return "1"; // n为1时,返回1
    // 先递归求出比n小1数字的外观数列
    String s=countAndSay(n-1);
    // 当前字符
    char num=s.charAt(0);
    // 当前连续相同字符个数
    int count=1;
    // 返回结果
    StringBuilder res=new StringBuilder();
    // 循环每一个字符
    for(int i=1;i<s.length();i++){
        // 如果当前字符等于num
        if(s.charAt(i)==num){
            // 连续相同字符数加一
            count++;
        }else{ // 如果当前字符不等于num
            // 将之前的连续相同字符个数以及该字符加入返回结果
            res.append(count).append(num);
            // 更新当前字符
            num=s.charAt(i);
            // 当前字符连续相同个数为1。
            count=1;
        }
    }
    // 将最后一组加入返回结果
    res.append(count).append(num);
    return res.toString();
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 88.81% of Java online submissions for Count and Say.

Memory Usage: 37.1 MB, less than 38.60% of Java online submissions for Count and Say.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
本文链接: https://leetcode.jp/leetcode-38-count-and-say-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。