代码随想录算法训练营Day36|LC435 无重叠区间LC763 划分字母区间LC56 合并区间

本文主要是介绍代码随想录算法训练营Day36|LC435 无重叠区间LC763 划分字母区间LC56 合并区间,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一句话总结:都是和昨天的用最少箭引爆气球类似的题。

原题链接:435 无重叠区间

计数不重叠的区间的个数,然后用总长度减去这个值即可。

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));int n = intervals.length;int cnt = 1;int right = intervals[0][1];for (int i = 1; i < n; ++i) {if (right <= intervals[i][0]) {right = intervals[i][1];cnt++;}}return n - cnt;}
}

原题链接:763 划分字母区间

利用一个长为26的数组记录每个字母最后出现的位置,然后一趟遍历更新该区间所有字母最后的出现位置,如果right == i,即表明该段区间内所有字母都仅在该区间内出现,而不会在区间外。将该区间长度加入答案即可。

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> ans = new ArrayList<>();int n = s.length();int[] lastPos = new int[26];for (int i = 0; i < n; ++i) {lastPos[s.charAt(i) - 'a'] = i; }int left = 0, right = 0;for (int i = 0; i < n; ++i) {right = Math.max(right, lastPos[s.charAt(i) - 'a']);if (i == right) {ans.add(right - left + 1);left = right + 1;}}return ans;}
}

原题链接:56 合并区间

区间的经典题了。排序后先将第一段区间加入答案,然后往后遍历,如果右端点大于当前遍历区间左端点,那么将该段区间右端点更新为当前遍历区间的右端点与原本右端点的最大值,否则将新的区间加入答案,同时更新右端点值为该遍历端点的右端点。

class Solution {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));List<int[]> ans = new ArrayList<>();for (int i = 0; i < intervals.length; ++i) {int left = intervals[i][0], right = intervals[i][1];if (ans.isEmpty() || ans.get(ans.size() - 1)[1] < left) {ans.add(new int[]{left, right});} else ans.get(ans.size() - 1)[1] = Math.max(right, ans.get(ans.size() - 1)[1]);}return ans.toArray(new int[ans.size()][]);}
}

这篇关于代码随想录算法训练营Day36|LC435 无重叠区间LC763 划分字母区间LC56 合并区间的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringCloud集成AlloyDB的示例代码

《SpringCloud集成AlloyDB的示例代码》AlloyDB是GoogleCloud提供的一种高度可扩展、强性能的关系型数据库服务,它兼容PostgreSQL,并提供了更快的查询性能... 目录1.AlloyDBjavascript是什么?AlloyDB 的工作原理2.搭建测试环境3.代码工程1.

Java调用Python代码的几种方法小结

《Java调用Python代码的几种方法小结》Python语言有丰富的系统管理、数据处理、统计类软件包,因此从java应用中调用Python代码的需求很常见、实用,本文介绍几种方法从java调用Pyt... 目录引言Java core使用ProcessBuilder使用Java脚本引擎总结引言python

Java中ArrayList的8种浅拷贝方式示例代码

《Java中ArrayList的8种浅拷贝方式示例代码》:本文主要介绍Java中ArrayList的8种浅拷贝方式的相关资料,讲解了Java中ArrayList的浅拷贝概念,并详细分享了八种实现浅... 目录引言什么是浅拷贝?ArrayList 浅拷贝的重要性方法一:使用构造函数方法二:使用 addAll(

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,:本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一:“杨辉三角”题目链接二:题解代码:三:题解思路:总结一:“杨辉三角”题目链接题目链接:点击这里

SpringBoot使用注解集成Redis缓存的示例代码

《SpringBoot使用注解集成Redis缓存的示例代码》:本文主要介绍在SpringBoot中使用注解集成Redis缓存的步骤,包括添加依赖、创建相关配置类、需要缓存数据的类(Tes... 目录一、创建 Caching 配置类二、创建需要缓存数据的类三、测试方法Spring Boot 熟悉后,集成一个外

不删数据还能合并磁盘? 让电脑C盘D盘合并并保留数据的技巧

《不删数据还能合并磁盘?让电脑C盘D盘合并并保留数据的技巧》在Windows操作系统中,合并C盘和D盘是一个相对复杂的任务,尤其是当你不希望删除其中的数据时,幸运的是,有几种方法可以实现这一目标且在... 在电脑生产时,制造商常为C盘分配较小的磁盘空间,以确保软件在运行过程中不会出现磁盘空间不足的问题。但在

在C#中合并和解析相对路径方式

《在C#中合并和解析相对路径方式》Path类提供了几个用于操作文件路径的静态方法,其中包括Combine方法和GetFullPath方法,Combine方法将两个路径合并在一起,但不会解析包含相对元素... 目录C#合并和解析相对路径System.IO.Path类幸运的是总结C#合并和解析相对路径对于 C

轻松掌握python的dataclass让你的代码更简洁优雅

《轻松掌握python的dataclass让你的代码更简洁优雅》本文总结了几个我在使用Python的dataclass时常用的技巧,dataclass装饰器可以帮助我们简化数据类的定义过程,包括设置默... 目录1. 传统的类定义方式2. dataclass装饰器定义类2.1. 默认值2.2. 隐藏敏感信息

opencv实现像素统计的示例代码

《opencv实现像素统计的示例代码》本文介绍了OpenCV中统计图像像素信息的常用方法和函数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 统计像素值的基本信息2. 统计像素值的直方图3. 统计像素值的总和4. 统计非零像素的数量

IDEA常用插件之代码扫描SonarLint详解

《IDEA常用插件之代码扫描SonarLint详解》SonarLint是一款用于代码扫描的插件,可以帮助查找隐藏的bug,下载并安装插件后,右键点击项目并选择“Analyze”、“Analyzewit... 目录SonajavascriptrLint 查找隐藏的bug下载安装插件扫描代码查看结果总结Sona