当前位置：首页 > news >正文

代码随想录 day 30 贪心

news 来源：原创 2024/9/20 23:27:06

第八章贪心算法 part04

今天的三道题目，都算是重叠区间问题，大家可以好好感受一下。都属于那种看起来好复杂，但一看贪心解法，惊呼：这么巧妙！
这种题还是属于那种，做过了也就会了，没做过就很难想出来。
不过大家把如下三题做了之后，重叠区间基本上差不多了

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

https://programmercarl.com/0452.%E7%94%A8%E6%9C%80%E5%B0%91%E6%95%B0%E9%87%8F%E7%9A%84%E7%AE%AD%E5%BC%95%E7%88%86%E6%B0%94%E7%90%83.html

435. 无重叠区间

https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html

763.划分字母区间

https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html

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

题目链接

https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/

解题思路

贪心的思路，重复的气球尽量用一个弓箭来射爆

1.数组排序
2.模拟判断，是否重叠，处理俩个边界
注意重叠后要更新重叠的最小右边界，才能判断下一个是否还能用上一个弓箭

code

class Solution {public int findMinArrowShots(int[][] points) {if(points.length==0){return 0;}Arrays.sort(points,(i1,i2)->{//return i1[0]-i2[0]; 这里直接相减有越界 //[[-2147483646,-2147483645],[2147483646,2147483647]]if(i1[0]>i2[0]){return 1;}else{return -1;}});int result=1;//为0的已经判断过，所以至少是1个弓箭for(int i=1;i<points.length;i++){//i也是重1开始， 当前i和i-1比较，这种思想比较常用//数据排序后 ，当前i的左边界大于 i-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. 无重叠区间

题目链接

https://leetcode.cn/problems/non-overlapping-intervals/description/

解题思路

思路和上一题基本一样
左边界排序，删除重叠区间，重叠区间要取最小的
比如[[1,8],[2,6],[7,9]] 要移除的是[1,8] 而不是 [2,6],[7,9]
右边界排序更好理解

code

class Solution {public int eraseOverlapIntervals(int[][] intervals) {if(intervals.length==0){return 0;}Arrays.sort(intervals,(i1,i2)->{if(i1[0]==i2[0]){return i1[1]-i2[1];}if(i1[0]>i2[0]){return 1;}else{return -1;}});int result=0;for(int i=1;i<intervals.length;i++){if(intervals[i][0]<intervals[i-1][1]){result++;//仍然要记录最小的 比如// [[1,8],[2,6],[7,9]] //前面俩重叠，必定要移除其中一个 那么移除[1,8] 即可 输出1// 如果移除[2,6] 那么也要移除[7,9] 就输出2，不是最小数量intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);//intervals[i][1]=intervals[i-1][1];}}return result;}
}

class Solution {public int eraseOverlapIntervals(int[][] intervals) {if(intervals.length==0){return 0;}Arrays.sort(intervals,(i1,i2)->{if(i1[1]==i2[1]){return i1[0]-i2[0];}if(i1[1]>i2[1]){return 1;}else{return -1;}});int result=0;for(int i=1;i<intervals.length;i++){if(intervals[i][0]<intervals[i-1][1]){result++;//仍然要记录最小的 比如// [[1,8],[2,6],[7,9]] //前面俩重叠，必定要移除其中一个 那么移除[1,8] 即可 输出1// 如果移除[2,6] 那么也要移除[7,9] 就输出2，不是最小数量//intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);intervals[i][1]=intervals[i-1][1];}}return result;}
}

763. 划分字母区间

题目链接

https://leetcode.cn/problems/partition-labels/description/

解题思路

hash 记录最后位置
遍历更新start和end区间 end==i 结束当前区间收集结果

code

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> res=new ArrayList<>();Map<Character,Integer> hash=new HashMap<>();for(int i=0;i<s.length();i++){hash.put(s.charAt(i),i);}int end=0;int start=0;for(int i=0;i<s.length();i++){end=Math.max(hash.get(s.charAt(i)),end);if(end==i){res.add(end-start+1);start=i+1;}  }return res;}
}