代码随想录算法训练营第三六天 | 无重叠区间、划分字母区间、合并区间

LeetCode 435. 无重叠区间
LeetCode 763.划分字母区间
LeetCode 56. 合并区间

无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

和用最少数量的箭引爆气球很像，唯一的区别是引爆气球记录的是非重叠数量， 本题记录的是重叠数量。 在 if else 内操作会有所不同。

另外，本题对左区间和右区间均可排序，可以计算非重叠数量，用总数量减去非重叠得到重叠数量，也可以按下面代码直接计算重叠数量。

class Solution {// [1,2],[2,3],[3,4],[1,3]// [1,2],[1,3],[2,3],[3,4]  => [1,2],[1,2],[2,3],[3,4]// 1 < 2 重叠 记录删除 result++// 重叠记录最小右区间 // 直到遍历完数组public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) -> {if (a[0] == b[0]) return a[1] - b[1];return a[0] - b[0];});int result = 0;for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] < intervals[i - 1][1]) {  // 重叠步骤intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1]); result++;   } }return result;}
}

划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

题目要求同一字母最多出现在一个片段中。

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

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

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> result = new ArrayList<>();int[] hash = new int[26];for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);hash[c - 'a'] = i;}// s -> [8, 5, 8, ... ]int idx = 0;int last = -1;for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);idx = Math.max(idx, hash[c - 'a']);if (i == idx) {result.add(i - last);last = i;}}return result;}
}

class Solution {public int[][] findPartitions(String s) {// "ababcbacadefegdehijhklij"List<Integer> temp = new ArrayList<>();int[][] hash = new int[26][2]; // 26 个字母 2 列 表示该字母对应的区间// 哈希数组// [[0,8], [1,5], [4,7], [9,14], [10, 15] ...]for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (hash[c - 'a'][0] == 0) hash[c - 'a'][0] = i;hash[c - 'a'][1] = i;hash[s.charAt(0) - 'a'][0] = 0; }List<List<Integer>> h = new LinkedList<>();// 去除字符串中未出现的字母所占用区间// 组装区间到集合for (int i = 0; i < 26; i++) {// if (hash[i][0] != hash[i][1]) {temp.clear();temp.add(hash[i][0]);temp.add(hash[i][1]);h.add(new ArrayList<>(temp));// }}// 存入数组int[][] res = new int[h.size()][2];for (int i = 0; i < h.size(); i++) {List<Integer> list = h.get(i);res[i][0] = list.get(0);res[i][1] = list.get(1);}return res;}public List<Integer> partitionLabels(String s) {int[][] partitions = findPartitions(s);List<Integer> result = new ArrayList<>();// [[0,8], [1,5], [4,7], [9,14], [10, 15] ...]Arrays.sort(partitions, (o1, o2) -> Integer.compare(o1[0], o2[0]));int right = partitions[0][1];int left = 0;for (int i = 0; i < partitions.length; i++) {if (partitions[i][0] > right) { // 一旦下一区间左边界大于当前右边界，即可认为出现分割点result.add(right - left + 1);left = partitions[i][0];}right = Math.max(right, partitions[i][1]);}result.add(right - left + 1);return result;}
}

合并区间

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

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

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