首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【小Y学算法】⚡️每日LeetCode打卡⚡️——49.汇总区间

【小Y学算法】⚡️每日LeetCode打卡⚡️——49.汇总区间

作者头像
呆呆敲代码的小Y
发布2021-10-08 15:41:37
3870
发布2021-10-08 15:41:37
举报

请添加图片描述
请添加图片描述

前言

算法

  • 每天打卡一道算法题,既是一个学习过程,又是一个分享的过程
  • 提示:本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
  • 要保持一个每天都在学习的状态,让我们一起努力成为算法大神吧!
  • 今天是力扣算法题持续打卡第49天!

算法题


原题样例:汇总区间

给定一个无重复元素的有序整数数组 nums

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说,nums的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出:

  • “a->b” ,如果 a != b
  • “a” ,如果 a == b

示例 1:

输入:nums = [0,1,2,4,5,7]
输出:["0->2","4->5","7"]
解释:区间范围是:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/summary-ranges
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

示例 2:

输入:nums = [0,2,3,4,6,8,9]
输出:["0","2->4","6","8->9"]
解释:区间范围是:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

示例 3:

输入:nums = []
输出:[]

示例 4:

输入:nums = [-1]
输出:["-1"]

示例 5:

输入:nums = [0]
输出:["0"]

提示:

  • 0 <= nums.length <= 20
  • -231 <= nums[i] <= 231 - 1
  • nums 中的所有值都 互不相同
  • nums 按升序排列

C#方法:深度优先搜索

  1. 本质上就是循环数组,判断当前位置和上一位置(或者是当前位置和下一位置)相比,是不是相差1,是的话继续,不是的话就加入的list中
  2. 往list中添加,也有两种情况。 a. 连续值超过1 超过1 用 x->y 格式 b. 连续值等于1 不超过1 用 x 格式

代码:

public class Solution {
    public IList<string> SummaryRanges(int[] nums) {
        List<string> res = new List<string>();
        int i=0,j=0;

        while(j<nums.Length){
            //j==nums.Length-1 这个判断比较重要,可以考虑到数组到最后的情况
            if(j==nums.Length-1 || nums[j+1]-nums[j]!=1){
                if(i==j) res.Add($"{nums[i]}");
                else res.Add($"{nums[i]}->{nums[j]}");
                i = j+1;
            }
            ++j;
        }
        return res;
    }
}

执行结果

通过
执行用时:232 ms,在所有 C# 提交中击败了69.77%的用户
内存消耗:30 MB,在所有 C# 提交中击败了74.42%的用户

Java 方法一:一次遍历

思路解析

我们从数组的位置 00 出发,向右遍历。每次遇到相邻元素之间的差值大于 11 时,我们就找到了一个区间。遍历完数组之后,就能得到一系列的区间的列表。

在遍历过程中,维护下标low 和 high 分别记录区间的起点和终点,对于任何区间都有 low≤high。当得到一个区间时,根据low 和 high 的值生成区间的字符串表示。

  • 当 low
  • 当 low=high 时,区间的字符串表示为 ‘‘low"。

代码:

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ret = new ArrayList<String>();
        int i = 0;
        int n = nums.length;
        while (i < n) {
            int low = i;
            i++;
            while (i < n && nums[i] == nums[i - 1] + 1) {
                i++;
            }
            int high = i - 1;
            StringBuffer temp = new StringBuffer(Integer.toString(nums[low]));
            if (low < high) {
                temp.append("->");
                temp.append(Integer.toString(nums[high]));
            }
            ret.add(temp.toString());
        }
        return ret;
    }
}

执行结果

通过
执行用时:0 ms,在所有 Java  提交中击败了100.00%的用户
内存消耗:36.5 MB,在所有 Java 提交中击败了65.23%的用户

复杂度分析

时间复杂度:O( n )
空间复杂度:O( 1 )

总结

  • 今天是力扣算法题打卡的第四十九天!
  • 文章采用 C#Java 两种编程语言进行解题
  • 一些方法也是参考力扣大神写的,也是边学习边分享,再次感谢算法大佬们
  • 那今天的算法题分享到此结束啦,明天再见!
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2021-10-05 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 原题样例:汇总区间
    • C#方法:深度优先搜索
      • Java 方法一:一次遍历
      • 总结
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档