网站制作九江,台州高端网站设计,湛江外包做网站,四川建设网是国企吗452. 用最少数量的弓箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points #xff0c;其中points[i] [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全…452. 用最少数量的弓箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points 其中points[i] [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 xstart ≤ x ≤ xend则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后可以无限地前进。
给你一个数组 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]。
思路看到这种情况要想通过遍历来判断能否“一箭多雕”那么肯定需要排序的这个排序规则需要自定义按气球起始的x从小到大排序然后进行判断。通过一个气球结束的x来和下一个气球起始的x比较判断能否一箭引爆前后两个气球既然能引爆“气放光”也没关系然后为了确保箭射入的位置能完成这个动作可以将第二个气球“放气”让第二个气球结束的x变为第一个气球结束的x。需要注意的是题目中给出过至少会有一个气球所以不用判断气球数为0的情况
代码实现
class Solution {
public:static bool mySort(const vectorint a, const vectorint b) {return a[0] b[0];}int findMinArrowShots(vectorvectorint points) {sort(points.begin(), points.end(), mySort);int ret 1; //题目说了至少会有一个气球for(int i 0; i points.size() - 1; i) {if(points[i][1] points[i 1][0]) {ret;}else { //限定范围保证一支箭击破前后两个气球points[i 1][1] min(points[i 1][1], points[i][1]);}}return ret; }
};
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
解释: 你不需要移除任何区间因为它们已经是无重叠的了。
思路和上面一题有些相似不过这里要怎么排序呢——因为要判断的是前者的右边界是否在后者的范围内那么按右边界排序。遍历比较的过程和上面都是大同小异的。记得在合适的情况更新边界。
代码实现
class Solution {
public:static bool mySort(const vectorint a, const vectorint b) {return a[1] b[1]; //按右边界从小到大排序因为要判断的是前者的右边界有没有在在后者的范围内}int eraseOverlapIntervals(vectorvectorint intervals) {sort(intervals.begin(), intervals.end(), mySort);int ret 0;int end intervals[0][1]; //记录起始的右边界for(int i 1; i intervals.size(); i) {if(end intervals[i][0]) { //重叠ret;}else if(end intervals[i][0]) { //不重叠end intervals[i][1];}}return ret;}
};
