[Leetcode] Count and Say 数个数

whjin 发布于2019-08-14 12:30 / 1981人阅读

摘要：反转字符法复杂度时间空间思路因为数字不好从前向后遍历每一位要先统计一共有多少位，比较麻烦，所以我们直接从后向前计数，最后把结果倒置就行了。

Count Consecutive Digits in Integer

Count consecutive digits and say it. For example, return 132341 if input is 1112224. There are three 1s, three 2s and one 4.

反转字符法 复杂度

时间 O(N) 空间 O(1)

思路

因为数字不好从前向后遍历每一位（要先统计一共有多少位，比较麻烦），所以我们直接从后向前计数，最后把结果倒置就行了。

注意

退出循环后还要额外执行一次append，将最后的连续数字补齐

代码

public String countAndSay(int n) {
    if(n <= 0) return "";
    int last = n % 10, cnt = 1;
    n = n / 10;
    StringBuilder sb = new StringBuilder();
    while(n > 0){
        int digit = n % 10;
        if(digit == last){
            cnt++;
        } else {
            sb.append(cnt);
            sb.append(last);
            cnt = 1;
            last = digit;
        }
        n = n / 10;
    }
    sb.append(cnt);
    sb.append(last);
    sb.reverse();
    return sb.toString();
}

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) 递归栈空间

思路

因为第n个数count and say的结果是基于第n-1个数的，我们可以用递归解决这个问题。

代码

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

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

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

[Leetcode] Count And Say 外观序列

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

Towers 2019-08-14 12:44 评论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

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

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论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