当前位置：首页 > article >正文

leetcode刷题day31|贪心算法Part05重叠区间问题（56. 合并区间、738.单调递增的数字、968.监控二叉树）

article 2024/10/1 20:20:13

56. 合并区间

思路：这个题跟气球重叠区间的题目类似，只需要先按左边界进行排序，判断是否重叠，如果重叠，就选择最小的左边界和最大的右边界构成新的区间。

代码如下：

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

738.单调递增的数字

思路：局部解题方法：比如98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]–，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。全局思路：从后往前遍历。

代码如下：

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s=String.valueOf(n);
        char[] chars=s.toCharArray();
        int start=chars.length;
        for(int i=chars.length-1;i>0;i--){
            if(chars[i-1]>chars[i]){
                chars[i-1]--;
                start=i;
            }
        }
        for(int i=start;i<chars.length;i++) {
            chars[i]='9';
        }
        return Integer.parseInt(String.valueOf(chars));
    }
}

注意：考虑到有100，1000这样的数存在，所以需要记录修改的点，并将后面的所有值填充为9.

968.监控二叉树

思路：如果是从根节点开始遍历可能会重复计算，所以最好使用后序遍历。考虑到叶子节点都没有监控点，监控点会分布在叶子节点的上一层；同时可以监控到监控点的上一层节点。也就是说，把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。

此时，大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。使用全局变量result来记录摄像头个数。

此时这道题目还有一个难点：如何隔两个节点放一个摄像头

解决这个问题需要状态转移的公式，每个节点可能有三种状态，分别用数字表示：

0:该节点无覆盖
1:本节点有摄像头
2:本节点有覆盖

递归三部曲：

传入参数；根节点，返回值为int类型（节点的状态）
终止条件：空节点的状态应该是有覆盖，这样就可以在叶子节点的父节点放摄像头了。所以递归的终止条件应该是遇到了空节点，此时应该返回2（有覆盖）。
递归函数单层逻辑：主要有如下四类情况：
情况1：左右节点都有覆盖
左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
情况2：左右节点至少有一个无覆盖的情况，则中间节点（父节点）应该放摄像头。
情况3：左右节点至少有一个有摄像头，那么其父节点就应该是2（覆盖的状态）
情况4：头结点没有覆盖，所以递归结束之后，还要判断根节点，如果没有覆盖，result++。

代码如下：

class Solution {
    int result=0;
    public int minCameraCover(TreeNode root) {
        if(treeStatus(root)==0) result++;
        return result;
    }
    public int treeStatus(TreeNode root){
        if(root==null) return 2;
        int left=treeStatus(root.left);
        int right=treeStatus(root.right);
        if(left==0 || right==0){
            result++;
            return 1;
        }else if(left==1 || right==1){
            return 2;
        }else {
            return 0;
        }
    }
}