452. 用最少数量的箭引爆气球(中等)

news/2024/7/20 17:35:11/文章来源:https://blog.csdn.net/weixin_38979465/article/details/139249739

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

  • 1. 题目描述
  • 2.详细题解
  • 3.代码实现
    • 3.1 Python
    • 3.2 Java

1. 题目描述

题目中转:452. 用最少数量的箭引爆气球

在这里插入图片描述
在这里插入图片描述

2.详细题解

    引爆所有气球,弓箭数要最少,那么每支弓箭尽量多的引爆气球,采用贪心策略。对于重叠(仅边界重合也是重叠此题中)的区间,仅需一只弓箭即可引爆即可,因此问题转换为对于重叠的区间仅留一个区间即可,其它区间移除即可,最终留下的区间数则是所需的最少得弓箭数。和435.无重叠空间(中等)题目类似,但有区间在于仅边界重合的也可仅用一只弓箭解决,因此对于边界重合的也要视为叠加。

3.代码实现

3.1 Python

class Solution:def findMinArrowShots(self, points: List[List[int]]) -> int:points.sort(key=lambda x:(x[1],x[0]))res = 1right = points[0][1]for l,r in points[1:]:if l > right:res += 1right = rreturn res

在这里插入图片描述

3.2 Java

class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points, new Comparator<int[]>(){public int compare(int[] left, int[] right){if (left[1] >= right[1]){return 1;}else{return -1;}}});int ans = 1;int right = points[0][1];for (int i=0;i<points.length;i++){if (points[i][0] > right){ans++;right = points[i][1];}}return ans;}
}

在这里插入图片描述
  Java程序有个细节需要注意,注意看区间的取值范围,因此在排序时不能再直接比较两个数据的差值,因为一旦一个负数或者整数相减,可能会超出int的取值范围,如测试案例[[-2147483646,-2147483645],[2147483646,2147483647]]

  执行用时不必过于纠结,对比可以发现,对于python和java完全相同的编写,java的时间一般是优于python的;至于编写的代码的执行用时击败多少对手,执行用时和网络环境、当前提交代码人数等均有关系,可以尝试完全相同的代码多次执行用时也不是完全相同,只要确保自己代码的算法时间复杂度满足相应要求即可,也可以通过点击分布图查看其它coder的code

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1052506.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

用源码建站可能涉及知产侵权,建站的注意!

近日普推知产老杨看到央视报道一家公司用了某建站源码涉及知产侵权&#xff0c;起诉了全国八千多家公司&#xff0c;某梦自从创始人因病转给某公司后&#xff0c;也在大量起诉用其建站代码公司侵权&#xff0c;他们也都是申请了相关的著作权。 有的中小企业在运营中会涉及建站…

Kibana(一张图片胜过千万行日志)

Kibana&#xff08;一张图片胜过千万行日志&#xff09; Kibana是一个开源的分析和可视化平台&#xff0c;设计用于和Elasticsearch一起工作。 你用Kibana来搜索&#xff0c;查看&#xff0c;并和存储在Elasticsearch索引中的数据进行交互。 你可以轻松地执行高级数据分析&a…

STM32H750外设之ADC通道选择

目录 概述 1 通道选择功能介绍 2 通道选择&#xff08; SQRx、 JSQRx&#xff09; 2.1 通道复用 2.1.1 通道介绍 2.1.2 通道框图 2.2 转换分组 2.3 内部专用通道 3 通道预选寄存器 (ADCx_PCSEL) 3.1 功能介绍 3.2 预选通道寄存器 概述 本位主要介绍STM32H750外设之…

07_Servlet

Servlet 一 Servlet简介 1.1 动态资源和静态资源 静态资源 无需在程序运行时通过代码运行生成的资源,在程序运行之前就写好的资源. 例如:html css js img ,音频文件和视频文件 动态资源 需要在程序运行时通过代码运行生成的资源,在程序运行之前无法确定的数据,运行时动态生成…

2种方法将集合数据List构建成树形结构

文章目录 递归循环构建树结构hutool.TreeUtil.build构建树结构 递归循环构建树结构 先查最外层树节点数据&#xff0c;再递归遍历每一层子节点数据 public ApiResultDto<List<LocationDto>> getTreeByParams(LocationSearchDto searchDto, SecurityUser user) {// …

Python Keras:打造深度学习模型的利器

更多Python学习内容&#xff1a;ipengtao.com Keras是一个高级神经网络API&#xff0c;由纯Python编写并能够运行在TensorFlow、Theano和CNTK之上。Keras以简洁和可扩展性为目标&#xff0c;使研究人员能够快速实验&#xff0c;并能在生产环境中轻松部署。无论是深度学习的新手…

智慧水坝:科技变革的里程碑

在曾经的水利工程领域&#xff0c;水坝只是为了水资源的调配和控制&#xff0c;提供一定的安全储备。然而&#xff0c;随着现代科技的不断发展&#xff0c;传统的水坝已经不再是单一的水源控制工程&#xff0c;而是变成了一个充满智慧与创新的生态系统。智慧水坝的概念已经超越…

【重制版】Unity Meta Quest 一体机开发(一):前期准备,Meta XR SDK导入和环境配置,配置玩家物体

文章目录 &#x1f4d5;教程说明&#x1f4d5;Meta XR SDK 介绍&#x1f4d5;前期准备⭐开启开发者模式⚡在 Meta 官网申请开发者⚡在 Meta Quest 手机 APP 开启开发者 ⭐电脑需要下载的软件⚡Meta Quest Link&#xff08;以前叫做Oculus PC客户端&#xff09;⚡Oculus ADB Dri…

工业级3D开发引擎HOOPS:创新与效率的融合!

在当今这个技术日新月异的时代&#xff0c;3D技术已成为推动各行各业发展的重要力量。从工程设计到游戏开发&#xff0c;从虚拟现实到增强现实&#xff0c;3D技术的应用无处不在&#xff0c;它极大地丰富了我们的生活和工作。而在这样的背景下&#xff0c;HOOPS作为一个强大的3…

想玩转Python爬虫?这些知识点你必须掌握!

想玩转Python爬虫&#xff1f;这些知识点你必须掌握&#xff01; Python爬虫作为数据获取的利器&#xff0c;吸引着越来越多的人学习。但想要真正掌握这门技术&#xff0c;仅仅停留在“会用”的阶段是远远不够的。你需要建立一个系统的知识体系&#xff0c;才能在面对各种复杂情…

景源畅信:如何让抖音短视频标签越来越精准?

在数字媒体的海洋中&#xff0c;抖音短视频以其独特的魅力和高效的信息传递方式吸引了无数眼球。如何让这些短视频的标签变得更精准&#xff0c;是提高推荐质量、增强用户体验的关键问题。标签的精确度直接关系到内容能否触达感兴趣的用户&#xff0c;进而影响用户的留存率和平…

实现 Vue 标签页切换效果的组件开发

在本次开发中&#xff0c;我们将实现一个 Vue 组件&#xff0c;用于展示和切换标签页。 背景有移动动画效果 该组件将具有以下功能&#xff1a; 标签页左右滚动点击标签页切换内容关闭指定标签页支持多种标签页风格 以下是实现该组件的具体步骤&#xff1a; 创建 Vue 组件…

stream-并行流

定义 常规的流都是串行的流并行流就是并发的处理数据&#xff0c;一般要求被处理的数据互相不影响优点&#xff1a;数据多的时候速度更快&#xff0c;缺点&#xff1a;浪费系统资源&#xff0c;数据少的时候开启线程更耗费时间 模版 Stream<Integer> stream1 Stream.of…

Redis篇 String

String概念和set,get扩充 一. String类型的基本介绍二. String中set,get方法扩充 一. String类型的基本介绍 redis中所有的key都是字符串类型的,但是value的类型差异很大. redis中的字符串,直接就是二进制方式存储的,可以存储整数,二进制数据 文本数据,Json,xml还有音频等. 二.…

Unity 生成物体的几种方式

系列文章目录 unity工具 文章目录 系列文章目录前言&#x1f449;一、直接new的方式创建生成1-1.代码如下1-2. 效果图 &#x1f449;二、使用Instantiate创建生成&#xff08;GameObject&#xff09;2-1.代码如下2-2.效果如下图 &#x1f449;三.系统CreatePrimitive创建生成3…

C++ | Leetcode C++题解之第116题填充每个节点的下一个右侧节点指针

题目&#xff1a; 题解&#xff1a; class Solution { public:Node* connect(Node* root) {if (root nullptr) {return root;}// 从根节点开始Node* leftmost root;while (leftmost->left ! nullptr) {// 遍历这一层节点组织成的链表&#xff0c;为下一层的节点更新 next…

APM2.8飞控

ArduPilotMega 主控可应用于 固定翼、直升机、多旋翼、地面车辆 APM2.8飞控供电有两种 1.电流计供电&#xff0c; 2.带BEC&#xff08;稳压功能&#xff09;的电调供电 ArduPilotMega 内部的硬件结构图&#xff1a; 调试时&#xff0c;不要使用向导&#xff0c;由于向导功能不…

针对上两篇微信同声传译语音播报功能,又出现了坑

我又双叒叕来了&#xff0c;自己写的bug&#xff0c;跪着也要改完&#xff0c;我是真的服了 首先&#xff0c;我们来说说是什么问题吧 上一篇文章的这张图还记得吧&#xff0c;不记得的&#xff0c;我在下面贴出来了&#xff1b; 我们在长度大于300的时候&#xff0c;根据句号…

Docker(四) 文件和网络

1 Dockerfile 1.1 什么是Dockerfile Dockerfile是一个文本文件&#xff0c;包含一系列命令&#xff0c;这些命令用于在 Docker 镜像中自动执行操作。Dockerfile 定义了如何构建 Docker 镜像的步骤和所需的操作。 Dockerfile 中包含的命令可以设置和定制容器的环境&#xff0c;…

[每周一更]-(第98期):PHP版本的升级历程

文章目录 大致历程PHP/FI (PHP 1.0)PHP 2.0PHP 3.0PHP 4.0PHP 5.0PHP 5.3 - 5.6PHP 7.0PHP 7.1 - 7.4PHP 8.0PHP 8.1 - 8.2 参考 PHP&#xff0c;即“超文本预处理器”&#xff08;Hypertext Preprocessor&#xff09;&#xff0c;是广泛应用于web开发的服务器端脚本语言。自19…