代码随想录算法训练营第三十天 | 452-用最少数量的箭引爆气球、435-无重叠区间、763-划分字母区间
LeetCode452 用最少数量的箭引爆气球
题目链接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/
文章讲解：https://programmercarl.com/0452.用最少数量的箭引爆气球.html
视频讲解：https://www.bilibili.com/video/BV1SA41167xe/?vd_source=b989f2b109eb3b17e8178154a7de7a51
重叠区间问题，本题要先进行区间排序，我这里按照以左边界从小到大排序，然后分两种情况进行统计
第一种情况是第 i 个气球的左边界大于第 i-1 个气球的右边界，此时说明这两个气球没有重叠的区间，记录上一个气球需要一个箭矢
第二种情况是第 i 个气球的左边界小于等于第 i-1 个气球的右边界，此时说明这两个气球有重叠的区间，将第 i 个气球的右边界更新为第 i 个气球和第 i-1 个气球二者中最小右边界，然后继续往后遍历气球。这样，若下一个气球区间不重叠，则会进入情况一，增加箭矢数量；若下一个气球区间重叠，则会进入情况二，继续更新最小右边界
此外进行排序时还要防止数值溢出的情况，最好使用Integer.compare(a[0], b[0])方法来替代return a[0] - b[0]
class Solution {public int findMinArrowShots(int[][] points) {if(points.length == 0){return 0;}if(points.length == 1){return 1;}Arrays.sort(points, (a, b)->Integer.compare(a[0], b[0]));int result = 1;for(int i = 1; i < points.length; i++){if(points[i][0] > points[i-1][1]){result++;}else{points[i][1] = Math.min(points[i][1], points[i-1][1]);}}return result;}
}
LeetCode435 无重叠区间
题目链接：https://leetcode.cn/problems/non-overlapping-intervals/description/
文章讲解：https://programmercarl.com/0435.无重叠区间.html
视频讲解：https://www.bilibili.com/video/BV1A14y1c7E1/?vd_source=b989f2b109eb3b17e8178154a7de7a51
本题实际要求的是重叠区间的数量，先进行区间排序，我这里按照以左边界从小到大排序，为了防止数值溢出的情况，使用Integer.compare(a[0], b[0])方法来替代return a[0] - b[0]
当第 i 个区间的左边界小于第 i-1 个气球的右边界时，二者有重叠区间，将第 i 个区间的右边界更新为第 i 个区间和第 i-1 个区间二者中最小右边界，并做count++，然后继续往后遍历区间
class Solution {public int eraseOverlapIntervals(int[][] intervals) {if(intervals.length == 0 || intervals.length == 1){return 0;}Arrays.sort(intervals, (a, b)->Integer.compare(a[0], b[0]));int result = 0;for(int i = 1; i < intervals.length; i++){if(intervals[i][0] < intervals[i-1][1]){result++;intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);}}return result;}
}
LeetCode763 划分字母区间
题目链接：https://leetcode.cn/problems/partition-labels/description/
文章讲解：https://programmercarl.com/0763.划分字母区间.html
视频讲解：https://www.bilibili.com/video/BV18G4y1K7d5/?vd_source=b989f2b109eb3b17e8178154a7de7a51
在遍历的过程中相当于是要找每一个字母的最远边界，如果找到之前遍历过的所有字母的最远边界，则说明这个边界即为分割点。此时前面出现过所有字母，最远也就到此边界了
首先先统计每一个字符最后出现的位置，然后再从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
class Solution {public List<Integer> partitionLabels(String s) {List<Integer> result = new ArrayList<>();int[] last = new int[26];char[] str = s.toCharArray();for(int i = 0; i < str.length; i++){last[str[i] - 'a'] = i;}int end = 0;int start = -1;for(int i = 0; i < str.length; i++){end = Math.max(end, last[str[i] - 'a']);if(i == end){result.add(i - start);start = end;}}return result;}
}