[Leetcode] Count And Say 外观序列

Towers 发布于2019-08-14 12:44 / 2694人阅读

摘要：递归解法复杂度时间空间递归栈思路该序列又叫做外观序列，无论如何我们都得将前一个序列元素算出来，才能计算后一个序列元素。当递归至的时候返回初始数字。另外，比如初始数字，第一次变成了，我们可以发现大于的数都只会一个一个出现了。

Count And Say

The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

递归解法 复杂度

时间 O(N!) 空间 O(N) 递归栈

思路

该序列又叫做外观序列，无论如何我们都得将前一个序列元素算出来，才能计算后一个序列元素。当递归至0的时候返回初始数字1。

代码

public class Solution {
    public String countAndSay(int n) {
        // 递归尽头返回空或者1
        if(n == 0) return "";
        if(n == 1) return "1";
        // 计算出上一个字符串
        String s = countAndSay(n - 1);
        StringBuilder sb = new StringBuilder();
        // 通过记录上次的字符来判断是否重复
        char last = s.charAt(0);
        int cnt = 1;
        for(int i = 1; i < s.length(); i++){
            // 如果重复则计数器加1
            if(s.charAt(i) == last){
                cnt++;
            } else {
            // 否则添加上一个字符，并重置计数器为1
                sb.append(cnt);
                sb.append(last);
                last = s.charAt(i);
                cnt = 1;
            }
        }
        // 最后记得把最后一个字符加上
        sb.append(cnt);
        sb.append(last);
        return sb.toString();
    }
}

迭代解法 复杂度

时间 O(N!) 空间 O(N) 字符长度

思路

将递归换成了循环而已。

代码

public class Solution {
    public String countAndSay(int n) {
        if(n == 0) return "";
        String s = "1";
        for(int j = 1; j < n; j++){
            StringBuilder sb = new StringBuilder();
            char last = s.charAt(0);
            int cnt = 1;
            for(int i = 1; i < s.length(); i++){
                if(s.charAt(i) == last){
                    cnt++;
                } else {
                    sb.append(cnt);
                    sb.append(last);
                    last = s.charAt(i);
                    cnt = 1;
                }
            }
            sb.append(cnt);
            sb.append(last);
            s = sb.toString();
        }
        return s;
    }
}

后续 Follow Up

Q：该序列有什么特点？
A：该序列最大的数不超过3，除非初始的数字大于3

Q: 对于101这种数字如何解读？
A：因为10后面只有1个（奇数）数字，所以不可能是1个0，肯定是10个1.

Q: 如果有三位数，比如200个1，表示成2001时怎么办？
A: 其实我们可以发现，除了第一次生成的数以外，以后再也不可能有200个连续的同一个数，所以这种情况只可能发生在第一次count and say，特殊处理一下就好了。另外，比如初始数字9991999，第一次变成了391139，我们可以发现大于3的数都只会一个一个出现了。

GPU云服务器云服务器 Say LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64675.html

[Leetcode] Count and Say 数个数

摘要：反转字符法复杂度时间空间思路因为数字不好从前向后遍历每一位要先统计一共有多少位，比较麻烦，所以我们直接从后向前计数，最后把结果倒置就行了。 Count Consecutive Digits in Integer Count consecutive digits and say it. For example, return 132341 if input is 1112224. The...

whjin 2019-08-14 12:30 评论0 收藏0
leetcode 38 count and say

摘要：而读起来是两个，所以第三个字符串就应当是。同理第四个字符串是一个一个，因此是。依次类推而我们的目的是，对于输入的正整数，我们要给出第个字符串是什么。这里采用了是为了减少内存的开销。解法设置初始字符串将重新赋值当前字符字符计数题目详情 The count-and-say sequence is the sequence of integers with the first five t...

不知名网友 2019-08-16 10:31 评论0 收藏0
leetcode38 count and say 数数游戏

摘要：题目要求英文的题目有点绕口，所以去网上找了一下题目的意思。题目的核心逻辑在于将口语化的数数字转化为字符串。题目要求 The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ... 1 is read off as one 1 or 11...

dabai 2019-08-14 18:04 评论0 收藏0
[LeetCode] 398. Random Pick Index (Reservoir Sampl

Problem Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array. Note:The array siz...

edagarli 2019-08-16 13:46 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0