第八章 贪心算法 part04
今天的三道题目，都算是 重叠区间 问题，大家可以好好感受一下。 都属于那种看起来好复杂，但一看贪心解法，惊呼：这么巧妙！
这种题还是属于那种，做过了也就会了，没做过就很难想出来。
不过大家把如下三题做了之后， 重叠区间 基本上差不多了
452. 用最少数量的箭引爆气球
思路
- 存在重叠的气球就一起射
- 不用移除气球数组的元素，只需要统计箭的数量
- 将数组按照起始位置排序，如果气球重叠了，那么右边边界的最小值
- 算法步骤
- 排序：
首先按气球的结束位置（points[i][1]）对所有气球进行排序。这是因为我们希望尽可能长地利用每支箭的有效范围。 - 初始化：
我们至少需要一支箭，所以初始化 arrows = 1。
end 用来记录当前箭的有效射程的结束位置，初始为第一个气球的结束位置 points[0][1]。 - 遍历气球：
从第二个气球开始，逐个检查气球。
如果当前气球的起始位置 points[i][0] 大于 end，这意味着当前气球与之前的气球不重叠，需要新增一支箭。
如果当前气球与之前的气球重叠（即 points[i][0] <= end），它们可以共享同一支箭。
- 排序：
class Solution {
public int findMinArrowShots(int[][] points) {
//按照结束位置从小到大排序
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int result = 1;
for(int i = 1; i < points.length; i++){
// 气球 i 的起始位置 points[i][0] 大于前一个气球 i-1 的结束位置 points[i - 1][1]，说明这两个气球不重叠，也不相邻。
if(points[i][0] > points[i-1][1]){
result++;
}else{
//注意这里的逻辑是更新气球最小右边界
points[i][1] = Math.min(points[i][1], points[i-1][1]);
}
}
return result;
}
}
435. 无重叠区间
思路
- 按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
int count = 1;
int end = intervals[0][1];
for(int i = 1; i < intervals.length; i++){
if(end <= intervals[i][0]){
end = intervals[i][1];
count++;
}
}
return intervals.length - count;
}
}
763.划分字母区间
思路
- 解法1：
1.统计每一个字符最后出现的位置
2.从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点 - 解法2：
将区间按左边界从小到大排序，找到边界将区间划分成组，互不重叠。找到的边界就是答案。
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> result = new LinkedList<>();
int[] edge = new int[26];
char[] chars = s.toCharArray();
for(int i = 0; i < chars.length; i++){
edge[chars[i] - 'a'] = i;//如：edge[0] = 2，表示字符 'a' 最后出现的位置是索引 2。
}
int left = 0;
int right = 0;
for(int i = 0; i < s.length(); i++){
// 更新最远边界 right：因为对于每个字符 chars[i]，edge[chars[i] - 'a'] 给出了该字符的最后出现位置。
// right = Math.max(right, edge[chars[i]-'a'])
// 这一行代码确保 idx 始终表示从当前字符到目前为止，所有字符的最远边界。
right = Math.max(right, edge[chars[i]-'a']);
if(i == right){
result.add(right - left + 1);
left = i + 1;
}
}
return result;
}
}
只写了第一种，有时间写第二种
