Day31 贪心算法 part05

56. 合并区间

本题也是重叠区间问题，如果昨天三道都吸收的话，本题就容易理解了。

代码随想录

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0]));
        List<int[]> result = new ArrayList<>();

        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] <= intervals[i-1][1]){
                intervals[i][0] = Math.min(intervals[i][0], intervals[i-1][0]);
                intervals[i][1] = Math.max(intervals[i][1], intervals[i-1][1]);
            }else{
                result.add(new int[]{intervals[i-1][0], intervals[i-1][1]});            
            }

        }
        result.add(new int[]{intervals[intervals.length-1][0], intervals[intervals.length-1][1]}); 
        
        return result.toArray(new int[0][]);
       
    }
}

总结

1.本题的套路还是判断重叠区间问题。和射气球是一样的套路，只是判断条件和判断后的更新操作有所不同。

2.还是一样的套路，我们先对左边界进行排序，让所有的相邻区间尽可能的重叠在一起。如果intervals[i][0] <= intervals[i-1][1]说明当前段的边界和上一个边界有重叠，然后对当前边界进行跟新，需要更新当前边界的左边取最小值，然后更新当前边界的右边取最大值。如果判断没有重叠，就把上一段区间加入到集合里面。注意for循环之后，其实最后一段区间是没有加入到集合里面的，我们需要在for循环之后，单独把最后一段区间加入到集合里面。最后把集合result.toArray(new int[0][])转为二维数组。

738.单调递增的数字

代码随想录

class Solution {
    public int monotoneIncreasingDigits(int n) {
        //一开始不知道怎么处理整数的每一位，其实转为字符串或者字符数组处理就可以了

        String num = String.valueOf(n);
        char[] chars = num.toCharArray();
        int flag = chars.length;

        for(int i = chars.length - 1; i > 0; i--){
            if(chars[i] < chars[i-1]){
                chars[i-1]--;
                flag = i;
            }
        }

        for(int i = flag; i < chars.length; i++){
            chars[i] = '9';
        }

        return Integer.parseInt(new String(chars));

    }
}

总结

1.这道题只需要想明白我们要遵循的处理逻辑就可以。就是如果碰到前一位的数字比当前位高，那我们就把前一位数字减1，当前数字应该变成9。想明白这个就好做了。然后还有一个难点就是应该前序遍历还是后序遍历，这种情况可以自己模拟一下，对于这道题，应该是后序遍历，因为后序遍历可以利用到前一次处理的结果。最后一个难点就是我们不应该是直接把当前数字变成9，而是设置一个flag，让flag后面的数字全变成9，这是为了防止1000，这种情况，如果不使用flag，就是900，而不是999。还有flag的初始不能为0，因为如果碰到1234，这种就不需要处理flag，所以我们应该初始为 int flag = chars.length;

2.一开始不知道怎么处理整数的每一位，其实转为字符串或者字符数组处理就可以了，后面再通过Integer.parseInt()转为int类型。然后基本数据类型是没有toString方法的。

3.这道题关键是想到个例怎么处理，还要考虑遍历顺序，只有从后向前遍历才能重复利用上次比较的结果。最后想到使用flag来标记从哪里开始赋值9。

968.监控二叉树 （可跳过）

本题是贪心和二叉树的一个结合，比较难，一刷大家就跳过吧。

代码随想录

总结

总结

可以看看贪心算法的总结，贪心本来就没啥规律，能写出个总结篇真的不容易了。

代码随想录