代码随想录-Day37

2024-06-24 04:20
文章标签 随想录 代码 day37

本文主要是介绍代码随想录-Day37,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

56. 合并区间

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
示例 1:

输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:

输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
在这里插入图片描述

方法一:

/**
时间复杂度 : O(NlogN) 排序需要O(NlogN)
空间复杂度 : O(logN)  java 的内置排序是快速排序 需要 O(logN)空间*/
class Solution {public int[][] merge(int[][] intervals) {List<int[]> res = new LinkedList<>();//按照左边界排序Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));//initial start 是最小左边界int start = intervals[0][0];int rightmostRightBound = intervals[0][1];for (int i = 1; i < intervals.length; i++) {//如果左边界大于最大右边界if (intervals[i][0] > rightmostRightBound) {//加入区间 并且更新startres.add(new int[]{start, rightmostRightBound});start = intervals[i][0];rightmostRightBound = intervals[i][1];} else {//更新最大右边界rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);}}res.add(new int[]{start, rightmostRightBound});return res.toArray(new int[res.size()][]);}
}

这段Java代码实现了一个函数 merge,用于合并一系列有重叠的区间。给定一个二维数组 intervals,其中每个 intervals[i] 是一个长度为2的数组,表示一个区间 [start, end],该函数的目标是将这些区间合并成一个新的区间数组,使得在新数组中任意两个区间没有交集,并且覆盖所有原始区间。以下是代码的详细解析:

时间复杂度和空间复杂度说明

  • 时间复杂度:O(NlogN),主要来自对区间按左边界排序的操作,其中N是区间数量。
  • 空间复杂度:O(logN),这是由于Java内置排序方法(快速排序)的递归调用栈空间。

代码解析

  1. 初始化:创建一个名为 resLinkedList 用于存储不重叠的合并后的区间。同时,初始化 start 为数组中第一个区间的起始位置,rightmostRightBound 为当前已知的最远的右边界。

  2. 排序:使用 Arrays.sort() 方法按区间的左边界升序排序整个 intervals 数组。排序是本算法的关键步骤,它确保了后续遍历过程中的合并逻辑简单且有效。

  3. 遍历并合并

    • 遍历排序后的区间数组。对于每个区间,如果当前区间的起始位置大于已知的最远右边界,说明当前区间与之前处理过的所有区间都不重叠,可以将前一个区间的结束位置与 start 组成的区间加入结果列表 res,并更新 start 为当前区间的起始位置,同时更新 rightmostRightBound 为当前区间的结束位置。
    • 如果当前区间起始位置不大于最远右边界,说明当前区间与前一个区间有重叠,此时只需要更新 rightmostRightBound 为当前区间和已知最远右边界中的较大值,以覆盖更大的范围。
  4. 添加最后一个区间:遍历结束后,别忘了将最后一个有效区间 [start, rightmostRightBound] 添加到结果列表 res 中。

  5. 转换并返回结果:最后,将 res 中的数据转换成数组类型并返回。

示例说明

假设输入区间为 [[1,3],[2,6],[8,10],[15,18]],经过排序、遍历合并后,最终的不重叠区间数组将是 [[1,6],[8,10],[15,18]],这正是函数预期输出的结果。

// 版本2
class Solution {public int[][] merge(int[][] intervals) {LinkedList<int[]> res = new LinkedList<>();Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));res.add(intervals[0]);for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] <= res.getLast()[1]) {int start = res.getLast()[0];int end = Math.max(intervals[i][1], res.getLast()[1]);res.removeLast();res.add(new int[]{start, end});}else {res.add(intervals[i]);}         }return res.toArray(new int[res.size()][]);}
}

这个Java代码是用于解决“合并区间”问题的另一个版本实现。给定一个二维数组 intervals,其中每个 intervals[i] 为一个长度为2的数组,表示一个区间 [start, end],该函数的目标是将所有重叠的区间合并成一个新的区间数组,并且在新数组中任意两个区间不会有重叠部分。下面是该代码的详细解析:

代码解析

  1. 初始化:定义一个 LinkedList<int[]> res 作为结果容器来存储合并后的区间。使用 Arrays.sort() 方法对输入区间按起始位置升序排序,便于后续处理。

  2. 添加首个区间:将排序后的首个区间直接加入结果列表 res

  3. 遍历合并:从第二个区间开始遍历整个 intervals 数组。对于每个区间,执行以下操作:

    • 判断重叠:如果当前区间的起始位置 intervals[i][0] 小于等于结果列表中最后一个区间的结束位置 res.getLast()[1],说明这两个区间有重叠。
    • 合并区间:当发现重叠时,合并这两个区间。新的起始位置取两者中较小的(在这里直接取了 res.getLast()[0],因为当前区间起始位置肯定不会小于已加入的区间的起始位置),新的结束位置取两者结束位置的较大值。然后从 res 中移除旧的最后一个区间,添加合并后的新区间。
    • 无重叠则直接添加:如果当前区间与结果列表最后一个区间无重叠,则直接将当前区间加入到结果列表 res 中。
  4. 转换并返回结果:遍历结束后,将 LinkedList 类型的结果列表转换为数组类型并返回。

时间复杂度和空间复杂度

  • 时间复杂度:O(NlogN),其中N为区间数量。排序操作占主导地位。
  • 空间复杂度:O(N),res 用于存储不重叠的合并区间,最坏情况下需要与输入区间相同的空间。

示例说明

例如,给定输入区间 [[1,3],[2,6],[8,10],[15,18]],经过处理后,合并后的区间应为 [[1,6],[8,10],[15,18]],这正是该函数预期返回的结果。

738. 单调递增的数字

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。

给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。

示例 1:

输入: n = 10
输出: 9
示例 2:

输入: n = 1234
输出: 1234
示例 3:

输入: n = 332
输出: 299

方法一:

版本1
class Solution {public int monotoneIncreasingDigits(int N) {String[] strings = (N + "").split("");int start = strings.length;for (int i = strings.length - 1; i > 0; i--) {if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])) {strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";start = i;}}for (int i = start; i < strings.length; i++) {strings[i] = "9";}return Integer.parseInt(String.join("",strings));}
}

这段Java代码是为了解决一个问题:给定一个非负整数N,找到具有单调递增数字的最大的数,其数字重新排列后小于或等于N。单调递增数字是指每个位置上的数字都不小于其左侧的数字(从左到右)。

代码解析

  1. 字符串转换:首先,将整数N转换成字符串数组strings,方便单独处理每一位数字。

  2. 从右向左扫描:使用一个外层循环从字符串的末尾开始向前遍历(索引istrings.length - 10),目的是检测数字是否递减。如果当前位的数字小于前一位的数字(strings[i] < strings[i - 1]),则:

    • 将前一位的数字减一((Integer.parseInt(strings[i - 1]) - 1)),并将其转换回字符串形式。
    • 记录这个位置start = i,作为后续处理的起点,因为start右侧的所有数字都需要变成9以确保结果是最大的单调递增数字。
  3. 填充9:使用一个内层循环,从位置start到字符串的末尾,将所有这些位置的数字替换为"9",以确保生成的数字尽可能大。

  4. 转换回整数并返回:最后,使用String.join("", strings)将修改后的字符串数组连接成一个字符串,再通过Integer.parseInt(...)将其转换回整数并返回。

示例

例如,如果N = 332,经过处理后的字符串数组变为["3", "2", "9"],重新组合并转换回整数得到329,这是小于等于332的最大单调递增数字。

注意:这个解法在处理边界情况(如当N本身就是单调递增或需要大幅度减少首位数字时)表现良好,但在某些情况下可能不是最高效的算法,特别是在N非常大,且大部分数字都需要减少时。

方法二:

版本2
class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] chars = s.toCharArray();int start = s.length();for (int i = s.length() - 2; i >= 0; i--) {if (chars[i] > chars[i + 1]) {chars[i]--;start = i+1;}}for (int i = start; i < s.length(); i++) {chars[i] = '9';}return Integer.parseInt(String.valueOf(chars));}
}

这个版本的代码实现与第一个版本非常相似,主要的不同在于细节处理和变量命名上,逻辑本质上是一致的。下面是这个版本的解析:

代码解析

  1. 转换为字符数组:首先,将整数n转换为字符串s,然后进一步转换成字符数组chars。这样可以直接操作每一位数字,无需频繁地在数字和字符串之间转换。

  2. 从右向左扫描:外层循环的起始点调整为i = s.length() - 2,这是因为现在是从倒数第二位开始比较(避免数组越界,同时正确定位需要检查的相邻数字对)。如果发现chars[i]大于chars[i + 1],说明违反了递增顺序:

    • chars[i]减一,表示这一位不能保持原值,需要生成更小的递增序列。
    • 更新start = i + 1,记录接下来应该全部填充为9的起始位置。
  3. 填充9:与之前版本相同,从位置start到字符串的末尾,所有这些位置的字符都被替换为字符’9’。

  4. 转换回整数并返回:最后,使用String.valueOf(chars)将字符数组转换回字符串,然后通过Integer.parseInt(...)转换为整数并返回结果。

优化点

  • 直接在字符数组上操作减少了字符串到数字、数字到字符串的转换次数,这可能在处理大数值时略微提高效率。
  • 循环起始点的调整去掉了对数组长度的减一操作,使得逻辑更直观。

示例

假设n = 332,处理过程与第一个版本相同,最终得到的字符数组表示的数字为329,转换为整数后返回。

此算法同样适用于寻找给定整数N下,最大的单调不减(即递增)整数。

这篇关于代码随想录-Day37的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1089157

相关文章

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

D4代码AC集

贪心问题解决的步骤: (局部贪心能导致全局贪心)    1.确定贪心策略    2.验证贪心策略是否正确 排队接水 #include<bits/stdc++.h>using namespace std;int main(){int w,n,a[32000];cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int i=1

html css jquery选项卡 代码练习小项目

在学习 html 和 css jquery 结合使用的时候 做好是能尝试做一些简单的小功能,来提高自己的 逻辑能力,熟悉代码的编写语法 下面分享一段代码 使用html css jquery选项卡 代码练习 <div class="box"><dl class="tab"><dd class="active">手机</dd><dd>家电</dd><dd>服装</dd><dd>数码</dd><dd

生信代码入门:从零开始掌握生物信息学编程技能

少走弯路,高效分析;了解生信云,访问 【生信圆桌x生信专用云服务器】 : www.tebteb.cc 介绍 生物信息学是一个高度跨学科的领域,结合了生物学、计算机科学和统计学。随着高通量测序技术的发展,海量的生物数据需要通过编程来进行处理和分析。因此,掌握生信编程技能,成为每一个生物信息学研究者的必备能力。 生信代码入门,旨在帮助初学者从零开始学习生物信息学中的编程基础。通过学习常用

husky 工具配置代码检查工作流:提交代码至仓库前做代码检查

提示:这篇博客以我前两篇博客作为先修知识,请大家先去看看我前两篇博客 博客指路:前端 ESlint 代码规范及修复代码规范错误-CSDN博客前端 Vue3 项目开发—— ESLint & prettier 配置代码风格-CSDN博客 husky 工具配置代码检查工作流的作用 在工作中,我们经常需要将写好的代码提交至代码仓库 但是由于程序员疏忽而将不规范的代码提交至仓库,显然是不合理的 所

Unity3D自带Mouse Look鼠标视角代码解析。

Unity3D自带Mouse Look鼠标视角代码解析。 代码块 代码块语法遵循标准markdown代码,例如: using UnityEngine;using System.Collections;/// MouseLook rotates the transform based on the mouse delta./// Minimum and Maximum values can