当前位置: 首页 > news >正文

力扣爆刷第148天之贪心算法五连刷(区间合并)

力扣爆刷第148天之贪心算法五连刷(区间合并)

文章目录

      • 力扣爆刷第148天之贪心算法五连刷(区间合并)
      • 一、406. 根据身高重建队列
      • 二、452. 用最少数量的箭引爆气球
      • 三、435. 无重叠区间
      • 四、763. 划分字母区间
      • 五、56. 合并区间
      • 六、738. 单调递增的数字

一、406. 根据身高重建队列

题目链接:https://leetcode.cn/problems/queue-reconstruction-by-height/description/
思路:本题身高排序,有两个维度,一个是身高,一个是排队人数,让我们按照这两个维度对数组进行排序,使其满足要求。
维度要分开看,当身高相同时,排队元素需要升序排列,当身高不同时,身高需要降序排列(如果身高升序排列将导致排在前面的人数为0)。
按照以上要求排列好以后,一定是身高高的都排在前面,身高矮的排在后面,身高相同的排队人数升序,所以这个时候就按照排队人数把元素插入新数组,即可实现排序。
在这里插入图片描述

class Solution {public int[][] reconstructQueue(int[][] people) {List<int[]> list = new ArrayList<>();// 身高相同数量升序,身高不同身高降序Arrays.sort(people, (a, b) -> {if(a[0] == b[0]) return a[1] - b[1];else return b[0] - a[0];});for(int[] nums : people) {list.add(nums[1], nums);}return list.toArray(new int[list.size()][]);}
}

二、452. 用最少数量的箭引爆气球

题目链接:https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/
思路:求用最少数量的箭引爆气球,本质上是求区间的交集有几个,交集有几个,就需要几个箭,求交集只需要先按照左区间进行排序,然后选择最小的右边界,即可。

class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));int count = 1, right = points[0][1];for(int[] nums : points) {if(nums[0] > right) {count++;right = nums[1];}else{right = Math.min(right, nums[1]);}}return count;}
}

三、435. 无重叠区间

题目链接:https://leetcode.cn/problems/non-overlapping-intervals/description/
思路:本题其实求的是无重叠区间的个数,用总区间个数减去无重叠区间的个数,即为要去掉的区间的个数。
求把多个区间去掉最少区间成为无重叠区间,首先先把所有的区间按照左边界排序,然后维护一个区间进行比较,如果当前区间的左边界位于其中,说明区间重叠了,是需要计数的,作为去掉一个区间,然后右边界改成相交的两个区间的最小的右边界,这样可以尽最大努力避免区间重叠,如果当前区间的左边界位于维护区间的右边界之外,则说明无重叠区间,又因为都是按照左边界排序的,只需要把右边界改成最右边的边界即可。

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

四、763. 划分字母区间

题目链接:https://leetcode.cn/problems/partition-labels/description/
思路:划分字母区间,尽可能划分较大的区间,让所有字母只出现在一个区间中,所以只需要先遍历一遍字符串,然后记录下来各个字母出现的最远距离,然后再遍历一遍字符串,不断更新当前字母最远出现的距离,只要遍历到这个距离,就划分出了一个区间。以此往复即可。

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

五、56. 合并区间

题目链接:https://leetcode.cn/problems/merge-intervals/
思路:和前面的几道区间相关的题来说非常简单,就是判断当前区间的左边界是否位于上一个区间之中,位于就合并,不位于就是单独的区间。

class Solution {public int[][] merge(int[][] intervals) {if(intervals.length == 1) return intervals;Arrays.sort(intervals, (a, b) -> a[0] - b[0]);List<int[]> list = new ArrayList<>();for(int i = 1; i < intervals.length; i++) {if(intervals[i][0] <= intervals[i-1][1]) {intervals[i][0] = intervals[i-1][0];intervals[i][1] = Math.max(intervals[i][1], intervals[i-1][1]);}else{int[] temp = {intervals[i-1][0], intervals[i-1][1]};list.add(temp);}}list.add(new int[]{intervals[intervals.length-1][0], intervals[intervals.length-1][1]});int[][] result = new int[list.size()][2];for(int i = 0; i < list.size(); i++) {result[i] = list.get(i);}return result;}
}

六、738. 单调递增的数字

题目链接:https://leetcode.cn/problems/monotone-increasing-digits/description/
思路:将一个数改成距离它最小的单调递增的数,其实很简单,如果两个数逆序,如53,那么最大的递增数为49,那么只需要从右边往左边找,找到第一个逆序,逆序后面的都改成9即可。

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

相关文章:

力扣爆刷第148天之贪心算法五连刷(区间合并)

力扣爆刷第148天之贪心算法五连刷&#xff08;区间合并&#xff09; 文章目录 力扣爆刷第148天之贪心算法五连刷&#xff08;区间合并&#xff09;一、406. 根据身高重建队列二、452. 用最少数量的箭引爆气球三、435. 无重叠区间四、763. 划分字母区间五、56. 合并区间六、738.…...

JSON及Python操作JSON相关

JSON及Python操作JSON相关 Json简介及Python操作Json相关示例。 1. JSON概念及支持的数据类型 1.1 什么是 JSON&#xff1f; JSON&#xff08;JavaScript Object Notation&#xff09;是一种轻量级的数据交换格式&#xff0c;易于人阅读和编写&#xff0c;同时也易于机器解…...

[ 网络通信基础 ]——网络的传输介质(双绞线,光纤,标准,线序)

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;网络通信基础TCP/IP专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年6月8日14点23分 &#x1f004;️文章质量&#xff1a;94分 前言—— 在现代通信网络中&#xff0c;传输介质是数据传…...

Android 高德地图API(新版)

新版高德地图 前言正文一、创建应用① 获取PackageName② 获取调试版安全码SHA1③ 获取发布版安全码SHA1 二、配置项目① 导入SDK② 配置AndroidManifest.xml 三、获取当前定位信息① ViewBinding使用和导包② 隐私合规设置③ 权限请求④ 初始化定位⑤ 获取定位信息 四、显示地…...

LeetCode---二叉树

144/94/145. 二叉树的前、中、后序的递归遍历 以中序遍历为例&#xff0c;其余类似&#xff1a; 给定一个二叉树的根节点 root &#xff0c;返回 它的 中序 遍历 。 代码示例&#xff1a; /*** Definition for a binary tree node.* struct TreeNode {* int val;* Tr…...

从0开发一个Chrome插件:核心功能开发——弹出页面

前言 这是《从0开发一个Chrome插件》系列的第十一篇文章,本系列教你如何从0去开发一个Chrome插件,每篇文章都会好好打磨,写清楚我在开发过程遇到的问题,还有开发经验和技巧。 专栏: 从0开发一个Chrome插件:什么是Chrome插件?从0开发一个Chrome插件:开发Chrome插件的必…...

AIGC笔记--Stable Diffusion源码剖析之UNetModel

1--前言 以论文《High-Resolution Image Synthesis with Latent Diffusion Models》 开源的项目为例&#xff0c;剖析Stable Diffusion经典组成部分&#xff0c;巩固学习加深印象。 2--UNetModel 一个可以debug的小demo&#xff1a;SD_UNet​​​​​​​ 以文生图为例&#…...

Linux文件系统与日志分析

目录 inode block 链接 文件修复 实验步骤 针对ext文件系统恢复删除文件 针对xfs文件系统恢复删除文件 日志 日志级别 rsyslogd服务 日志目录 messages日志文件&#xff08;系统日志&#xff09; 集中管理日志 - 实验 1.环境配置 1.1 1.2 1.3 1.4 1.5 2.远…...

【SkyWalking】使用PostgreSQL做存储K8s部署

拉取镜像 docker pull apache/skywalking-ui:10.0.1 docker tag apache/skywalking-ui:10.0.1 xxx/xxx/skywalking-ui:10.0.1 docker push xxx/xxx/skywalking-ui:10.0.1docker pull apache/skywalking-oap-server:10.0.1 docker tag apache/skywalking-oap-server:10.0.1 xxx…...

详解大模型微调数据集构建方法(持续更新)

大家好,我是herosunly。985院校硕士毕业,现担任算法t研究员一职,热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名,CCF比赛第二名,科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的见解。曾经辅导过若干个非计算机专业的学生进入到算…...

自制植物大战僵尸:HTML5与JavaScript实现的简单游戏

引言 在本文中&#xff0c;我们将一起探索如何使用HTML5和JavaScript来创建一个简单的植物大战僵尸游戏。这不仅是一项有趣的编程挑战&#xff0c;也是学习游戏开发基础的绝佳机会。 什么是植物大战僵尸&#xff1f; 植物大战僵尸是一款流行的策略塔防游戏&#xff0c;玩家需…...

Istio_1.17.8安装

项目背景 按照istio官网的命令一路安装下来&#xff0c;安装好的istio版本为目前的最新版本&#xff0c;1.22.0。而我的k8s集群的版本并不支持istio_1.22的版本&#xff0c;导致ingress-gate网关安装不上&#xff0c;再仔细查看istio的发布文档&#xff0c;如果用istio_1.22版本…...

[数据集][目标检测]室内积水检测数据集VOC+YOLO格式761张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;761 标注数量(xml文件个数)&#xff1a;761 标注数量(txt文件个数)&#xff1a;761 标注类别…...

17_Vue高级监听器生命周期Vue组件组件通信

文章目录 1. 数据监听器watch2. Vue生命周期3. Vue组件4. Vue组件通信Appendix 1. 数据监听器watch 首先watch需要单独引 import {watch} from vuewatch函数监听ref响应式数据 watch(监听的内容&#xff0c;监听行为)监听行为默认为(newValue,oldValue) let firstname ref…...

【ROS使用记录】—— ros使用过程中的rosbag录制播放和ros话题信息相关的指令与操作记录

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、rosbag的介绍二、rosbag的在线和离线录制三、rosbag的播放相关的指令四、其他rosbag和ros话题相关的指令总结 前言 rosbag是ROS&#xff08;机器人操作系统…...

Laravel 富文本内容

Laravel 获取富文本的纯文本内容-CSDN博客 Laravel 富文本内容里面的图片添加前缀URL-CSDN博客 Laravel 富文本图片的style样式删除-CSDN博客. Laravel 获取富文本中的所有图片-CSDN博客 富文本字体font-famly删除 $data preg_replace(/(<[^>])style["\][^"…...

Spark Python环境搭建与优化:深入剖析四个方面、五个方面、六个方面及七个关键要点

Spark Python环境搭建与优化&#xff1a;深入剖析四个方面、五个方面、六个方面及七个关键要点 在大数据处理领域&#xff0c;Apache Spark凭借其出色的性能和灵活性备受瞩目。而要在Python中利用Spark的强大功能&#xff0c;首先需要搭建一个稳定且高效的Spark Python环境。本…...

【微信小程序开发】小程序中的上滑加载更多,下拉刷新是如何实现的?

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…...

从 Android 恢复已删除的备份录

本文介绍了几种在 Android 上恢复丢失和删除的短信的方法。这些方法都不能保证一定成功&#xff0c;但您可能能够恢复一些短信或其中存储的文件。 首先要尝试什么 首先&#xff0c;尝试保留数据。如果你刚刚删除了信息&#xff0c;请立即将手机置于飞行模式&#xff0c;方法是…...

如何使用Python中的random模块生成随机数

在Python中&#xff0c;random模块提供了多种用于生成随机数的函数。以下是一些基本示例&#xff1a; 生成随机整数&#xff1a; 使用random.randint(a, b)函数生成一个介于a和b之间的随机整数&#xff08;包括a和b&#xff09;。 python复制代码 import random random_int …...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...