Day35代码随想录(1刷)贪心

2024-04-09 21:04
文章标签 随想录 代码 贪心 day35

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

435. 无重叠区间

给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后,剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

提示:

  • 1 <= intervals.length <= 105
  • intervals[i].length == 2
  • -5 * 104 <= starti < endi <= 5 * 104

 状态:没做出来,没想明白最少次数是什么意思

思路:只要有重叠的肯定要有元素是被移除的,所以这题的解法就是求出所有的重叠区间出来就可以完成题目。在这题中我们采用的是根据start升序的的数组,用minLen记录前一个的end值,如果现在start比end小则说明发生重叠了,如果发生重叠则可以把count++找到重叠的区间了,然后再比较现在的end跟minLen哪个更小目的是哪个更小我们就去删除哪一个,如果不重叠就把现在的minLen记为现在的end。最后返回count就可以了。

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(i,j)->{return i[0]-j[0];});int minLen=intervals[0][1];int count=0;for(int i=1;i<intervals.length;i++){if(intervals[i][0]<minLen){minLen=Math.min(intervals[i][1],minLen);count++;}else{minLen=intervals[i][1];            }   }return count;}
}

763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。

注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1:
输入:s = "ababcbacadefegdehijhklij"
输出:[9,7,8]
解释:
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的,因为划分的片段数较少。 

示例 2:

输入:s = "eccbbbbdec"
输出:[10]

提示:

  • 1 <= s.length <= 500
  • s 仅由小写英文字母组成

状态:完成,wa了几次主要是maxlen的取值

思路:这题跟上面已经昨天的题都很像,都是在划分区间,这题划分最多的区间意思就是反正只要一个元素只一个区间里出现就可以了,我们只要先记录每个字母的start以及end就可以了,然后我们再遍历字符串s,只要到达了maxlen就可以了,maxlen代表区间中字母最后一个出现的。

class Solution {public List<Integer> partitionLabels(String s) {int[][] arr=new int[26][2];for(int i=0;i<s.length();i++){int index=s.charAt(i)-'a';if(arr[index][0]==0&&arr[index][1]==0){arr[index][0]=i;arr[index][1]=i;}else{arr[index][1]=i;}}List<Integer> list=new ArrayList<>();int maxlen=0;int count=0;for(int i=0;i<s.length();i++){maxlen=Math.max(arr[s.charAt(i)-'a'][1],maxlen);if(i==maxlen){list.add(count+1);count=0;maxlen=0;}else{if(arr[s.charAt(i)-'a'][1]>maxlen) maxlen=arr[s.charAt(i)-'a'][1];count++;}}return list;}
}

 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] 可被视为重叠区间。

提示:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

 状态:完成

思路:这题也跟前面几题很像,就是把无重叠区间变成有几个重叠区间。

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals,(i,j)->{return i[0]-j[0];});LinkedList<int[]> list=new LinkedList<>();int start=intervals[0][0];int end=intervals[0][1];for(int i=1;i<intervals.length;i++){if(intervals[i][0]>end){list.add(new int[]{start,end});start=intervals[i][0];end=intervals[i][1];}else{end=Math.max(intervals[i][1],end);}}list.add(new int[]{start,end});return list.toArray(new int[0][0]);}
}

感想:明天解决贪心算法,后天开始动态规划,今天的贪心算法感觉有点难度,其实今天的题目加上昨天的打气球都是一个类型的贪心算法类型都是划分区间的题目,所以今天做了第一个无重叠区间之后其他的题目做起来都比较简单了。

这篇关于Day35代码随想录(1刷)贪心的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,

Python如何去除图片干扰代码示例

《Python如何去除图片干扰代码示例》图片降噪是一个广泛应用于图像处理的技术,可以提高图像质量和相关应用的效果,:本文主要介绍Python如何去除图片干扰的相关资料,文中通过代码介绍的非常详细,... 目录一、噪声去除1. 高斯噪声(像素值正态分布扰动)2. 椒盐噪声(随机黑白像素点)3. 复杂噪声(如伪

Java Spring ApplicationEvent 代码示例解析

《JavaSpringApplicationEvent代码示例解析》本文解析了Spring事件机制,涵盖核心概念(发布-订阅/观察者模式)、代码实现(事件定义、发布、监听)及高级应用(异步处理、... 目录一、Spring 事件机制核心概念1. 事件驱动架构模型2. 核心组件二、代码示例解析1. 事件定义

Python实例题之pygame开发打飞机游戏实例代码

《Python实例题之pygame开发打飞机游戏实例代码》对于python的学习者,能够写出一个飞机大战的程序代码,是不是感觉到非常的开心,:本文主要介绍Python实例题之pygame开发打飞机... 目录题目pygame-aircraft-game使用 Pygame 开发的打飞机游戏脚本代码解释初始化部