力扣452.用最少數量的剪引爆氣球

鏈接: link

思路

這道題的第一想法就是如果氣球重疊得越多那么用箭越少，所以先將氣球按照開始坐標從小到大排序，遇到有重疊的氣球，在重疊區域右邊界最小值之前的區域一定需要一支箭，這道題有兩個地方容易出錯：
1.出現重疊區域，忘記更新最右邊氣球的有邊界；
2.在重疊區域內射箭，即在下面提供的代碼中else里執行res++；
這是我自己容易犯的錯

class Solution {public int findMinArrowShots(int[][] points) {if (points.length == 0)return 0;Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));int res = 1;// 氣球數組不為0，至少需要一支箭for (int i = 1; i < points.length; i++) {// 當前氣球開始位>前一個氣球的結束位置if (points[i][0] > points[i - 1][1]) {res++;} else {// 否則當前氣球和前一個氣球挨著// 更新當前氣球的有邊界，瑜前一個氣球比較// 更新是為了避免和后一個氣球比較的時候重復射箭points[i][1] = Math.min(points[i][1], points[i - 1][1]);}}return res;}
}

435.無重疊區間
鏈接: link

class Solution {public int eraseOverlapIntervals(int[][] intervals) {if (intervals.length == 1)return 0;// 按照右邊界排序，從前向后遍歷Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));int cnt = 1;// 統計重合區域for (int i = 1; i < intervals.length; i++) {// 當前節點的左邊界<前一個節點的右邊界，一定有重合if (intervals[i][0] < intervals[i - 1][1]) {// 更新當前節點右邊界intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1]);} else {// 當前節點和前一個節點沒有重合cnt++;}}return intervals.length - cnt;}
}

相似題型

763.劃分字母區間
鏈接: link

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> ls = new ArrayList<>();int[] edge = new int[26];char[] chars = s.toCharArray();for (int i = 0; i < chars.length; i++) {edge[chars[i] - 'a'] = i; // 記錄每個字母最大邊界}int left = 0, right = 0;for (int i = 0; i < chars.length; i++) {right = Math.max(right, edge[chars[i] - 'a']);if (i == right) {ls.add(i - left + 1);left = right + 1;}}return ls;}
}

56.合并區間
鏈接: link

思路

這種題本質和【貪心算法4】的452和435一樣的套路，這幾道題都是判斷區間重疊，區別就是判斷區間重疊后的邏輯，本題是判斷區間重貼后要進行區間合并。所以一樣的套路，先排序，讓所有的相鄰區間盡可能的重疊在一起，按左邊界，或者右邊界排序都可以，處理邏輯稍有不同。
唯一需要考慮的是什么時候更新區間以及添加到ls中。

class Solution {public int[][] merge(int[][] intervals) {List<int[]> ls = new ArrayList<>();if(intervals.length == 1) return intervals;Arrays.sort(intervals,(a,b)->Integer.compare(a[0], b[0])); // 按照左邊界排序int start = intervals[0][0],end = intervals[0][1];for(int i = 1;i<intervals.length;i++){// 無重疊if(intervals[i][0] > end){// 合并ls.add(new int[]{start,end});// 更新start = intervals[i][0];end = intervals[i][1];}else{end = Math.max(end,intervals[i][1]);}}ls.add(new int[]{start,end});return ls.toArray(new int[ls.size()][]);}
}