代码随想录算法训练营第36天

今日任务

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

链接：https://docs.qq.com/doc/DUERGbnhhRkFRVENZ (opens in a new tab)

435. 无重叠区间

自己想法

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

763.划分字母区间

自己想法

用int[26][2]的table记录每个字母的起始和终止位置，然后排序，然后遍历，如果当前的起始位置大于等于上一个的终止位置，就是一个新的区间，否则就是重叠的区间。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[][] table = new int[26][2];
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i);
            if(table[c - 'a'][0] == 0) {
                table[c - 'a'][0] = i + 1;
                table[c - 'a'][1] = i + 1;
            }
            else {
                table[c - 'a'][1] = i + 1;
            }
        }
        Arrays.sort(table, (a, b) -> {
            if(a[0] == b[0]) return Integer.compare(a[1], b[1]);
            else return Integer.compare(a[0], b[0]);
        });
        int i = 0;
        while(i < 26 && table[i][0] == 0) i++;
        int right = table[i][1];
        if(i == 25) ans.add(right);
        for(i = i + 1; i < 26; i++) {
            if(table[i][0] >= right) {
                if(ans.size() == 0) ans.add(right);
                else ans.add(right - ans.stream().mapToInt(Integer::intValue).sum());
                right = table[i][1];
            }
            else {
                right = Math.max(table[i][1], right);
                
            }
            if(i == 25) {
                if(ans.size() == 0) ans.add(right);
                else ans.add(right - ans.stream().mapToInt(Integer::intValue).sum());
            }
        }
        return ans;
    }
}

题解想法

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

56. 合并区间

自己想法

找重叠区间，然后合并。

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if(a[0] == b[0]) return Integer.compare(a[1], b[1]);
            else return Integer.compare(a[0], b[0]);
        });
        List<List<Integer>> ans = new ArrayList<>();
        int left = intervals[0][0];
        int right = intervals[0][1];
        if(intervals.length == 1) ans.add(Arrays.asList(left, right));
        for(int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] <= right) {
                right = Math.max(intervals[i][1], right);
            }
            else {
                ans.add(Arrays.asList(left, right));
                left = intervals[i][0];
                right = intervals[i][1];
            }
            if(i == intervals.length - 1) ans.add(Arrays.asList(left, right));
        }
        int[][] array = ans.stream()
            .map(list -> list.stream().mapToInt(i -> i).toArray())
            .toArray(int[][]::new);
        return array;
    }
}