Day32第八章贪心算法part05

一. 学习文章及资料 435.无重叠区间 763.划分字母区间 56.合并区间 二. 学习内容

1. 无重叠区间

(1) 解题思路：

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

class Solution { public int eraseOverlapIntervals(int[][] intervals) { if(intervals.length==0) return 0; Arrays.sort(intervals,(a,b)->Integer pare(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 pare(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) 解题思路：

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

可以分为如下两步：

统计每一个字符最后出现的位置从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点 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 pare(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( )的使用方法