Day32 第八章 贪心算法 part05

一. 学习文章及资料

二. 学习内容

1. 无重叠区间

(1) 解题思路：

 方法一：右边界排序，从左向右记录非交叉区间的个数(count初始化化为0，从第二个数开始，如这个数左边界大于等于上一个数右边界，说明不重叠，count++，更新比较右边界)。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length==0) return 0;
        Arrays.sort(intervals,(a,b)->Integer.compare(a[1],b[1]));
        int count=1; //非重叠区间
        int end=intervals[0][1];
        for(int i=1;i<intervals.length;i++){
            if(end<=intervals[i][0]){
                count++;
                end=intervals[i][1];
            }
        }
        return intervals.length-count;
    }
}

方法二：左边界排序（左边界排序，或者按照右边界排序，都可以），当前数左边界大于等于上一个数右边界时，count++；如重叠的话，就更新最小右边界，弓箭的数量就相当于是非交叉区间的数量，只要把弓箭那道题目代码里射爆气球的判断条件加个等号（认为[0，1][1，2]不是相邻区间），然后用总区间数减去弓箭数量 就是要移除的区间数量了。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length==0) return 0;
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        int count=1; //箭的个数即不重叠区间
        for(int i=1;i<intervals.length;i++){
            if(intervals[i][0]>=intervals[i-1][1]){
                count++;
            }else{
                intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);
            }
        }
        return intervals.length-count;
    }
}

2. 划分字母区间

(1) 解题思路：

在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

可以分为如下两步：

1. 统计每一个字符最后出现的位置
2. 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] hash=new int[26];
        for(int i=0;i<s.length();i++){ //i为字符，hash[i]为字符出现的最后位置
            hash[s.charAt(i)-'a']=i;   //统计每一个字符最后出现的位置
        }
        int left=0;
        int right=0;
        List<Integer> result=new LinkedList<>();
        for(int i=0;i<s.length();i++){ //从头遍历字符，并更新字符的最远出现下标
            right=Math.max(right,hash[s.charAt(i)-'a']);//找到字符出现的最远边界
            if(i==right){ //如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
                result.add(right-left+1);
                left=right+1;
            }
        }
        return result;
    }
}

3. 合并区间

(1) 解题思路：

和452. 用最少数量的箭引爆气球 (opens new window)和 435. 无重叠区间 (opens new window)都一个套路。

这几道题都是判断区间重叠，区别就是判断区间重叠后的逻辑，本题是判断区间重贴后要进行区间合并。

所以一样的套路，先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同。

按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1] 即intervals[i]的左边界 <= intervals[i - 1]的右边界，则一定有重叠。（本题相邻区间也算重贴，所以是<=）

如何去模拟合并区间呢？

其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result里就可以了。如果没有合并就把原区间加入到result

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> result=new LinkedList<>();
        if(intervals.length==0)  result.toArray(new int[result.size()][]);
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        //第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并
        result.add(intervals[0]);
        for(int i=0;i<intervals.length;i++){
            if(intervals[i][0]<=result.getLast()[1]){
//合并区间，只更新右边界就好，因为result.getLast()[0]的左边界一定是最小值，因为我们按照左边界排序的
                int start=result.getLast()[0];
                int end=Math.max(intervals[i][1],result.getLast()[1]);
                result.removeLast();
                result.add(new int[]{start,end});
            }else{
                result.add(intervals[i]); //区间不重叠
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

(2) 扩展：

toArray( )的使用方法