代码随想录第三十六天｜贪心算法

今天继续是贪心算法

435. 无重叠区间

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

和昨天射箭的那道题一样的思路，先把数组按最远的区间进行排列。然后去判断是否重合就可以了。

763.划分字母区间 

class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> res = new ArrayList<>();
        HashMap<Character, Integer> map = new HashMap<>();
        int start = 0;
        int end = 0;

        for (int i = 0; i< s.length(); i++){
            map.put(s.charAt(i), i);
        }

        for (int i = 0; i< s.length(); i++){
            end = Math.max(end, map.get(s.charAt(i)));
            if (i == end){
                res.add(end - start +1);
                start = i + 1;
            }
        }
        return res;
    }
}

用HashMap，如果有新的重复字母出现，就把end扩展

56. 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
         //思路：
        //1.先将二维数组每一行按第一列排序得到诸如 [ [0,2], [1,5], [6,8], [10,11] ]
        //2.循环遍历每一行,给结果数组添加数据,有以下添加情况
        //3.对于结果数组 merge 的第一行,直接 add 进去即先将 [0,2] 添加
        //4.对于 merge 的其他行,若无重叠也直接添加如 [6,8], [10,11]
        //5.若有重叠,则修改上一行如 [0,2], [1,5] -> [0,5]

        int n = intervals.length;

        //通过 sort 函数对二维数组每一行按第一列元素进行排序
        //重写比较器方法,o1[] - o2[] 表示当 o1 大于 o2 时,将 o1 放在 o2 后面,即基本的升序排序
        //而 o1[0] - o2[0] 表示按二维数组的每一行第一列元素排序,类似的 o[1] - o2[1]代表按第二列进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        List<int[]> merge = new ArrayList<int[]>();

        for (int i = 0; i < n; i++) {

            //创建变量指向每行的左右元素(两列)
            int left = intervals[i][0];
            int right = intervals[i][1];

            //直接 add 的情况：当为第一行或者相邻两行无重叠时
            //解释：两行无重叠,即对应在 merge 中上一行的第 1 列小于本行第 0 列
            if (merge.size() == 0 || merge.get(merge.size() - 1)[1] < left) {
                merge.add(new int[]{left, right});
            }
            //合并的情况：当有重叠时,将 merge 中上一行的右边界更新
            else {
                merge.get(merge.size() - 1)[1] = Math.max(merge.get(merge.size() - 1)[1], right);
            }
        }
        //可以学习下此种将 list 转二维数组的方法
        return merge.toArray(new int[merge.size()][]);
    }
}

想不出来这道题

今天的题都是区间问题，除了最后一道题外都还好