【算法刷题day36】Leetcode：435. 无重叠区间、763.划分字母区间、56. 合并区间

草稿图网站
java的Deque

Leetcode 435. 无重叠区间

题目：435. 无重叠区间
解析：代码随想录解析

解题思路

先按start从小到大排序，定义一个end，如果node[0]超过end，则不用删减，end更新为node[1]；如果没超过，就更新end为end和node[1]的最小值

代码

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            return Integer.compare(a[0], b[0]);
        });
        int res = 0;
        int end = Integer.MIN_VALUE;
        for (int[] node : intervals) {
            if (node[0] >= end) {
                end = node[1];
            } else {
                end = Math.min(end, node[1]);
                res++;
            }
        }
        return res;
    }
}

//卡哥的原地操作
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            return 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]) {
                intervals[i][1] = Math.min(intervals[i-1][1], intervals[i][1]);
            } else {
                count++;
            }
        }
        return intervals.length - count;
    }
}

总结

暂无

Leetcode 763.划分字母区间

题目：763.划分字母区间
解析：代码随想录解析

解题思路

先找到每个字母的结束位置，然后每次更新目前区间的结束位置，如果到了就记录长度。

代码

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

总结

Leetcode 56. 合并区间

题目：56. 合并区间
解析：代码随想录解析

解题思路

记录好start和end。如果超过当前的第一个数超过end，就将上一个加入res中。

代码

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

总结

暂无