1. LeetCode 452. 用最少数量的箭引爆气球
题目链接:https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/
文章链接:https://programmercarl.com/0452.用最少数量的箭引爆气球.html
视频链接:https://www.bilibili.com/video/BV1SA41167xe
思路:
解题关键:只需要比较当前气球起始位置与重叠气球的最小右边界即可,若大于,则说明需要新的一支箭射中当前气球;否则,当前气球仍然与重叠气球重叠,共用一只箭。
首先按照起始位置排序,那么就从前向后遍历气球数组,靠左尽可能让气球重复。
然后,如果气球重叠了,重叠气球中右边边界的最小值之前的区间一定需要一个弓箭。
贪心:
局部最优:当气球出现重叠,一起射,所用弓箭最少。
全局最优:把所有气球射爆所用弓箭最少。
解法:
class Solution {
public int findMinArrowShots(int[][] points) {
// 升序
Arrays.sort(points,(a,b)->{
return a[0] > b[0] ? 1:-1;
});
int count=1;
for (int i=1;i<points.length;i++) {
// i的起始位置与重叠气球的结束位置进行比较
if (points[i][0] > points[i-1][1]) {// 若符合,则说明不重叠
count++;
} else {
// 更新重叠气球的结束位置
points[i][1] = Math.min(points[i][1],points[i-1][1]);
}
}
return count;
}
}
2. LeetCode 435. 无重叠区间
题目链接:https://leetcode.cn/problems/non-overlapping-intervals/description/
文章链接:https://programmercarl.com/0435.无重叠区间.html
视频链接:https://www.bilibili.com/video/BV1A14y1c7E1
思路:
与452相同,只要把射爆气球的判断条件加个等号(认为[0,1][1,2]不是相邻区间),然后用总区间数减去弓箭数量 就是要移除的区间数量了。
解法:
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
// 升序排列
Arrays.sort(intervals,(a,b)->{
return a[0]>b[0] ? 1: a[0]<b[0] ? -1:0;
});
int count=1;//不重叠的个数
for (int i=1;i<intervals.length;i++) {
// 若不重叠
if (intervals[i][0] >= intervals[i-1][1]) {
count++;
} else {
intervals[i][1] = Math.min(intervals[i][1],intervals[i-1][1]);
}
}
return intervals.length-count;
}
}
3. LeetCode 763.划分字母区间
题目链接:https://leetcode.cn/problems/partition-labels/description/
文章链接:https://programmercarl.com/0763.划分字母区间.html
视频链接:https://www.bilibili.com/video/BV18G4y1K7d5
思路:
本题关键是要求字符串尽可能划分多个片段。
在遍历的过程中相当于是要找每一个字母的边界,如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了。此时前面出现过所有字母,最远也就到这个边界了。
可以分为如下两步:
1️⃣统计每一个字符最后出现的位置;
2️⃣从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点。
解法:
class Solution {
public List<Integer> partitionLabels(String s) {
// 获取每个字符最远的位置
int[] temp = new int[27];
for (int i=0;i<s.length();i++) {
temp[s.charAt(i)-'a'] = i;
}
int right=0;
int left=0;
List<Integer> res = new ArrayList<>();
for (int i=0;i<s.length();i++) {
// 更新遍历过的字符的最远右边界
right = Math.max(right,temp[s.charAt(i)-'a']);
if (i==right) {
res.add(right-left+1);
left=i+1;
}
}
return res;
}
}