代码随想录算法训练营第三十五天 | LeetCode 435. 无重叠区间、763. 划分字母区间、56. 合并区间

代码随想录算法训练营第三十五天 | LeetCode 435. 无重叠区间、763. 划分字母区间、56. 合并区间

文章链接：无重叠区间        划分字母区间        合并区间

视频链接：无重叠区间        划分字母区间        合并区间

1. LeetCode 435. 无重叠区间

1.1 思路

1. 本题是通过删除最少个区间数使得这些区间没有重叠，注意 [1,2][2,3] 这种是不算重叠的。其实就是让我们求这些区间里有几个重叠区间，把个数统计出来然后输出即可
2. 如何让这些区间尽可能重叠呢？通过排序。让相邻的区间挨在一起，挨个遍历时才能把重叠的区间给判断出来。那是按照左边界排序还是右边界排序呢？其实都可以，那接下来是按照左边界排序的
3. 先判断数组长度是否为 0，为 0 直接 return 0。然后开始先对数组按照左边界排序，定义 count 计数
4. for（int i=1；i<nums.length；i++），从 1 开始，因为要 i 和 i-1 比较。我们遍历到第 i 个区间，前一个区间是第 i-1 个，if（nums[i][0]>=nums[i-1][0]）即 i 的左边界>= i-1 的右边界这种情况是不重叠的，由于挨着的不算重叠因此需要等于号，但我们要处理的是重叠区间，这里是不重叠的，因此这里不做处理
5. else 即重叠，i 的左边界<i-1 的右边界，这里发现了重叠区间就 count++。我们这里知道了当前区间和上一个区间是重叠的了，那怎么知道下一个区间和这两个区间重不重叠呢？此时就要更新这两个区间的最小右边界，即 nums[i][1]=Math.min(nums[i][1]，nums[i-1][1])，因为这个位置前面的位置一定是重叠的，而如果取了最大右边界，这两区间就不重叠了。
6. 此时遍历到下一个区间了，这个区间为 i，拿 i 的左边界和上一个区间 i-1 更新后的右边界相比，如果 i 的左边界>=i-1 更新后的右边界，就没有重叠。如果<了就是重叠了

1.2 代码

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

2. LeetCode 763. 划分字母区间

2.1 思路

1. 要让这个区间里的字符只出现在这个区间了，比如这个区间包含 a，其他 a 就不能出现在别的区间了
2. 我们要统计每个字符出现过的最远位置，比如我们包含了 a，我们就要知道 a 最远出现在哪里，最远的位置之前就把当前字符出现的所有位置都包含了
3. 整体是分为两步，一步需要记录每个元素出现的最远位置，接下来遍历的时候根据这个最远位置来决定这个区间的最远位置
4. 首先定义个哈希数组，记录每个元素出现的最远位置，定义长度 27，因为 26 个字母，27 足够了
5. for 循环第一次遍历数组获取哈希值，hash[s[i]-'a']=i；等于 i 是因为每次遍历更新的都是最新的下标位置。遍历结束后 hash 数组存的就是每个字符存的最远下标位置
6. 定义个数组 result 存放结果，定义左区间和右区间的下标 left 和 right
7. for 循环第二次遍历字符串数组，right=Math.max（right，hash[s[i]-'a']），因为我们要取的是每个字符出现的最远处，当 i 遍历到最远距离时即 i==right 就找到分割线了然后就 result 记录区间里的长度 right-left+1，更新 left=right+1。
8. 最后 return result 即可

2.2 代码

//
class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> list = new LinkedList<>();
        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;
    }
}

3. LeetCode 56. 合并区间

3.1 思路

1. 本题和452. 用最少数量的箭引爆气球、435. 无重叠区间很相似。把本题的区间中有重叠的都合并，最终输出所有的区间。相邻挨在一起的也要合并。
2. 首先我们要先给数组排序，按左边界或者右边界排序都是可以的。我们就按照左边界排序
3. 如果第 i 个区间的左边界<=第 i-1 个区间的右边界，证明这两个区间重叠了，就要合并区间了。else 就是第 i 个区间的左边界>第 i-1 个区间的右边界，就可以把第 i-1 个区间放入我们的 result 中了
4. 首先定义个二维数组 result，如果题目给的数组长度为 0 就直接 return null。然后我们就按照左边界排序数组
5. 由于上面已经排除了数组为 0 的情况，因此数组里肯定有一个数组，就先放入 result 中，后续如果有数组和它重叠，就把它获取然后修改
6. for（int i=1；i<intervals.length；i++）从 1 开始是因为第 i 个和第 i-1 个比较。if（intervals[i][0]<=intervals[i-1][1]）这就是重叠了，然后我们就更新新数组的边界，由于左边界一定是最小的了，因此更新的是右边界，右边界由于可能出现 i-1 的右边界比 i 的右边界还大，取的是右边界的最大值，因此就是先获取 result 的最后一个数组result.getLast()，result.getLast()[1]=Math.max（result.getLast()[1]，intervals[i][1]）。以上就是合并的操作，并且不需要再放入 result 中。
7. else 就是不重叠的情况，就直接把这区间放入 result，result.add（intervals[i]）

3.2 代码

//
// 版本2
class Solution {
    public int[][] merge(int[][] intervals) {
        LinkedList<int[]> res = new LinkedList<>();
        Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= res.getLast()[1]) {
                int start = res.getLast()[0];
                int end = Math.max(intervals[i][1], res.getLast()[1]);
                res.removeLast();
                res.add(new int[]{start, end});
            }
            else {
                res.add(intervals[i]);
            }         
        }
        return res.toArray(new int[res.size()][]);
    }
}