代码随想录算法训练营第三十一天-56合并区间、738单调递增的数字、968监控二叉树

前言
状态：56、738AC。968 看提示说比较难，先去做贪心的总结。968 不会，直接看解析。
更新

1	24-06-17 初始记录

初步题解

56 合并区间

题目链接：(https://leetcode.cn/problems/merge-intervals)

public static int[][] merge(int[][] intervals) {  
    ArrayList<int[]> list = new ArrayList<>();  
    // 按左边界排序  
    Arrays.sort(intervals, (o1, o2) -> {  
        if (o1[0] == o2[0]) {  
            return o1[1] - o2[1];  
        }  
        return o1[0] - o2[0];  
    });  
  
    if (intervals.length <= 1) {  
        return intervals;  
    }  
  
    int start = intervals[0][0];  
    int end = intervals[0][1];  
    for (int i = 1; i < intervals.length; i++) {  
        // 没有重合区间，将上一个合并区间加入list，并更新最新的合并区间  
        if (intervals[i][0] > intervals[i - 1][1]) {  
            list.add(new int[]{start, end});  
            start = intervals[i][0];  
            end = intervals[i][1];  
        // 更新合并的右边界  
        } else {  
            end = Math.max(end, intervals[i][1]);  
            // 更新右边界  
            intervals[i][1] = end;  
        }  
    }  
    // 最后需要将最后一个合并区间加入  
    list.add(new int[]{start, end});  
    return list.toArray(new int[list.size()][]);  
}

738 单调递增的数字

题目链接：(https://leetcode.cn/problems/monotone-increasing-digits)

public static int monotoneIncreasingDigits(int n) {  
    String num = n + "";  
    if (num.length() <= 1) {  
        return n;  
    }  
  
    char[] chars = num.toCharArray();  
    for (int i = chars.length - 1; i >= 1; i--) {  
        if (chars[i - 1] > chars[i]) {  
            chars[i - 1]--;  
            // 从i开始都变成9  
            for (int j = i; j < chars.length; j++) {  
                chars[j] = '9';  
            }  
        }  
    }  
  
    return Integer.parseInt(String.valueOf(chars));  
}

// 优化了一下，感觉循环还是放外面好
public static int monotoneIncreasingDigits(int n) {  
    String num = n + "";  
    if (num.length() <= 1) {  
        return n;  
    }  
  
    int start = -1;  
    char[] chars = num.toCharArray();  
    for (int i = chars.length - 1; i >= 1; i--) {  
        if (chars[i - 1] > chars[i]) {  
            chars[i - 1]--;  
            start = i;  
//          // 从i开始都变成9  
//          for (int j = i; j < chars.length; j++) {  
//              chars[j] = '9';  
//          }  
        }  
    }  
    if (start != -1) {  
        // 从i开始都变成9  
        for (int j = start; j < chars.length; j++) {  
            chars[j] = '9';  
        }  
    }  
  
    return Integer.parseInt(String.valueOf(chars));  
}

968 监控二叉树

题目链接：(https://leetcode.cn/problems/binary-tree-cameras)

看解析

思路：本题要从叶子节点分析，贪心贪叶子节点的上一个节点为摄像头（这种情况下摄像头最少）。然后，根据节点状态，一共分了 3 种：0 无覆盖；1 有摄像头；2 有覆盖。按照下图的思路做题，就可以解出，还是比较难想的。

内链：[[968监控二叉树图示.excalidraw]]

外链：

int res = 0;  
public int minCameraCover(TreeNode root) {  
    if (minCameraCoverTravel(root) == 0) {  
        res++;  
    }  
    return res;  
}  
  
private int minCameraCoverTravel(TreeNode root) {  
    if (root == null) {  
        // 空节点默认为有覆盖的状态  
        return 2;  
    }  
  
    // 后续遍历  
    int left = minCameraCoverTravel(root.left);  
    int right = minCameraCoverTravel(root.right);  
  
    // 前两个if可以互换  
    // 情况1  
    if (left == 2 && right == 2) {  
        return 0;  
    // 情况2，加一个摄像头   
} else if (left == 0 || right == 0) {  
        res++;  
        return 1;  
    } else {  
        return 2;  
    }  
}