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

【贪心算法】(第十二篇)

目录

⽆重叠区间(medium)

题目解析

讲解算法原理

编写代码

⽤最少数量的箭引爆⽓球(medium)

题目解析

讲解算法原理

编写代码


⽆重叠区间(medium)

题目解析

1.题目链接:. - 力扣(LeetCode)

2.题目描述

给定⼀个区间的集合 intervals ,其中 intervals[i] = [start(i), end(i)] 。返回需要移除区间的最⼩数量,使剩余区间互不重叠。
⽰例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 <= 10^5
◦ intervals[i].length == 2
◦ -5 * 10^4 <= start(i) < end(i) <= 5 * 10^4

讲解算法原理

解法(贪⼼):
贪⼼策略:

a. 按照「左端点」排序;
b. 当两个区间「重叠」的时候,为了能够「在移除某个区间后,保留更多的区间」,我们应该把
「区间范围较⼤」的区间移除。
如何移除区间范围较⼤的区间:
由于已经按照「左端点」排序了,因此两个区间重叠的时候,我们应该移除「右端点较⼤」的区间

编写代码

c++算法代码:

class Solution
{
public:
 int eraseOverlapIntervals(vector<vector<int>>& intervals) 
 {
 // 1. 按照左端点排序
 sort(intervals.begin(), intervals.end());
 // 2. 移除区间
 int ret = 0;
 int left = intervals[0][0], right = intervals[0][1];
 for(int i = 1; i < intervals.size(); i++)
 {
 int a = intervals[i][0], b = intervals[i][1];
 if(a < right) // 有重叠部分
 {
 ret++; // 删掉⼀个区间
 right = min(right, b);
 }
 else // 没有重叠部分
 {
 right = b;
 }
 }
 return ret;
 }
};

java算法代码:

class Solution
{
 public int eraseOverlapIntervals(int[][] intervals) 
 {
 // 1. 按照左端点排序
 Arrays.sort(intervals, (v1, v2) -> 
 {
 return v1[0] - v2[0];
 });
 // 2. 移除区间
 int ret = 0;
 int left = intervals[0][0], right = intervals[0][1];
 for(int i = 1; i < intervals.length; i++)
 {
 int a = intervals[i][0], b = intervals[i][1];
 if(a < right) // 有重叠区间
 {
 ret++;
 right = Math.min(right, b); // 贪⼼:删除右端点较⼤的区间 }
 else // 没有重叠区间
 {
 right = b;
 }
 }
 return ret;
 }
}

⽤最少数量的箭引爆⽓球(medium)

题目解析

1.题目链接:. - 力扣(LeetCode)

2.题目描述

有⼀些球形⽓球贴在⼀堵⽤XY平⾯表⽰的墙⾯上。墙⾯上的⽓球记录在整数数组 points ,其中
points[i] = [x(start), x(end)] 表⽰⽔平直径在 x(start) 和 x(end) 之间的⽓球。
你不知道⽓球的确切y坐标。
⼀⽀⼸箭可以沿着x轴从不同点完全垂直地射出。在坐标 x 处射出⼀⽀箭,若有⼀个⽓球的直径的开始和结束坐标为 x (start), x (end)且满⾜ x(start) ≤ x ≤ x(end) ,则该⽓球会被引爆。可以射出的⼸箭的数量没有限制。⼸箭⼀旦被射出之后,可以⽆限地前进。
给你⼀个数组 points ,返回引爆所有⽓球所必须射出的最⼩⼸箭数。
⽰例1:
输⼊:points=[[10,16],[2,8],[1,6],[7,12]]
输出:2
解释:⽓球可以⽤2⽀箭来爆破:
-在x=6处射出箭,击破⽓球[2,8]和[1,6]。
-在x=11处发射箭,击破⽓球[10,16]和[7,12]。
⽰例2:
输⼊:points=[[1,2],[3,4],[5,6],[7,8]]
输出:4
解释:每个⽓球需要射出⼀⽀箭,总共需要4⽀箭。
⽰例3:
输⼊:points=[[1,2],[2,3],[3,4],[4,5]]
输出:2
解释:⽓球可以⽤2⽀箭来爆破:
-在x=2处发射箭,击破⽓球[1,2]和[2,3]。
-在x=4处射出箭,击破⽓球[3,4]和[4,5]。
提⽰:
◦ 1 <= points.length <= 10^5
◦ points[i].length == 2
◦ -2^31 <= x(start) < x(end) <= 2^31 - 1

讲解算法原理

解法(贪⼼):
贪⼼策略:

a. 按照左端点排序,我们发现,排序后有这样⼀个性质:「互相重叠的区间都是连续的」;b. 这样,我们在射箭的时候,要发挥每⼀⽀箭「最⼤的作⽤」,应该把「互相重叠的区间」统⼀
引爆。
如何求互相重叠区间?
由于我们是按照「左端点」排序的,因此对于两个区间,我们求的是它们的「交集」:a. 左端点为两个区间左端点的「最⼤值」(但是左端点不会影响我们的合并结果,所以可以忽略);
b. 右端点为两个区间右端点的「最⼩值」。

编写代码

c++算法代码:

class Solution
{
public:
 int findMinArrowShots(vector<vector<int>>& points) 
 {
 // 1. 按照左端点排序
 sort(points.begin(), points.end());
 // 2. 求互相重叠区间的数量
 int right = points[0][1];
 int ret = 1;
 for(int i = 1; i < points.size(); i++)
 {
 int a = points[i][0], b = points[i][1];
 if(a <= right) // 有重叠部分
 {
 right = min(right, b);
 }
 else // ⽆重叠部分
 {
 ret++;
 right = b;
 }
 }
 return ret;
 }
};

java算法代码:

class Solution
{
 public int findMinArrowShots(int[][] points) 
 {
 // 1. 按照左端点排序
 Arrays.sort(points, (v1, v2) -> 
 {
 return v1[0] > v2[0] ? 1 : -1;
 });
 // 2. 求出互相重叠的区间的数量
 int right = points[0][1];
 int ret = 1;
 for(int i = 1; i < points.length; i++)
 {
 int a = points[i][0], b = points[i][1];
 if(a <= right) // 有重叠
 {
 right = Math.min(right, b);
 }
 else // 没有重叠
 {
 ret++;
 right = b;
 }
 }
 return ret;
 }
}


http://www.kler.cn/a/373272.html

相关文章:

  • 架构师之路-学渣到学霸历程-32
  • 【解决方案】微信小程序如何使用 ProtoBuf 进行 WebSocket 通信
  • 环形运输距离Conveyor Belts
  • 【更新】cyのLastDance - Chapter2(20241030~)
  • linux驱动—在自己的总线目录下创建属性文件
  • 贪心算法入门(一)
  • 鸿蒙生态崛起带来的机遇与挑战
  • React面试常见题目(基础-进阶)
  • 使用Selenium时,如何模拟正常用户行为?
  • Python数据分析NumPy和pandas(十六、文本格式数据的读取与存储:csv、json、xml和html)
  • 使用 BERT 和逻辑回归进行文本分类及示例验证
  • Pycharm,2024最新版Pycharm现在安装环境配置汉化详细教程!
  • 网管平台(三):如何高效管理无线网络
  • leetcode:面试题 05.07. 配对交换(python3解法)
  • 第二十章 Vue组件通信之父子通信
  • Flutter Color 大调整,需适配迁移,颜色不再是 0-255,而是 0-1.0,支持更大色域
  • Spring5学习记录(一)之IOC容器管理(基于XML方式)
  • vue前端使用pdfjs与pdfdist-mergeofd 实现预览pdf并翻页,同时解决预览pdf显示模糊的问题
  • 【算法与数据结构】二分查找思想
  • 海外媒体发稿:如何打造媒体发稿策略
  • 【SSM详细教程】-13-SpringMVC详解
  • Convolution 卷积
  • QT 实现自定义动态选择指示器
  • git的学习之远程进行操作
  • AIGC与教育行业的邂逅--其在数学领域的应用与实现
  • 【代码随想录Day55】图论Part07