day36||452. 用最少数量的箭引爆气球435. 无重叠区间 763.划分字母区间

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

class Solution {
    public int findMinArrowShots(int[][] points) {
        //Arrays.sort(points,(a,b)->a[0]-b[0]);//这句话会溢出
        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)->Integer.compare(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) {
        int[] hash = new int[26];
        for(int i = 0;i<s.length();i++){
            hash[s.charAt(i)-'a'] = i;
        }
        List<Integer> res = new ArrayList<>();
        int count = 0;
        int max = 0;
        for(int i = 0;i<s.length();i++){
            max = Math.max(hash[s.charAt(i)-'a'],max);
            count++;
            if(i == max){
                res.add(count);
                count = 0;
            }
        }
        return res;
    }
}