452.用最少數量的箭引爆氣球

貪心算法

重合最多的氣球射一箭，就是局部用箭數量最少的，全局的用箭數量就是最少的。

首先對二維數組進行排序，這樣就可以讓氣球更加緊湊。

思路：當前氣球是否和上一個氣球區間重合，如果不重合，那就count++；如果重合，要去更新重合氣球的重合區間最小的右邊界。（因為這樣就可以疊加重合的氣球，直到有不重合的氣球出現，就可以射一箭將重合的氣球射爆。）

class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));int count=1;for(int i=1; i<points.length; i++){if(points[i][0]>points[i-1][1]){count++;}else{points[i][1]=Math.min(points[i-1][1],points[i][1]);}}return count;}
}

435.無重疊區間

與上一題一模一樣

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(a,b)->a[0]-b[0]);int count=0;for(int i=1; i<intervals.length; i++){if(intervals[i][0]<intervals[i-1][1]){count++;intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);}}return count;}
}

763.劃分字母空間

思路：遍歷字符數組，找到每個元素出現的最大位置；然后遍歷數組，找到所有遍歷過的字母最大出現的位置，并且當前在數組的位置等于其元素最大位置，就是邊界位置。

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> list=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 idx=0;int last=-1;for(int i=0; i<chars.length; i++){idx=Math.max(idx,edge[chars[i]-'a']);if(i==idx){list.add(i-last);last=i;}}return list;}
}