代码随想录算法训练营第37天

今日任务

● 738.单调递增的数字 ● 968.监控二叉树

链接：https://docs.qq.com/doc/DUFVRd3p5SHFMSExQ (opens in a new tab)

435. 无重叠区间

一旦遇到前一位比后一位大的情况，就将前一位减一，然后将后面的全部变成9

自己想法

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

968. 监控二叉树

自己想法

不在叶子上放置摄像头，在父节点上放置摄像头，所以使用后序遍历。其中使用状态转移的思想。然后使用一个数来记录三种状态，0表示未被监控，1表示被监控，2表示放置了摄像头

class Solution {
    private int count = 0;
    public int minCameraCover(TreeNode root) {
        int covered = invert(root);
        if (covered == 0) count++;  // 额外处理一下root，因为它没有父节点
        return count;
    }
    // 返回值：root被监控情况。0是没有被监控到（自己也就没有摄像头），1是被监控到但自己没有摄像头，2是自己有摄像头
    // 左右中递归遍历
    private int invert(TreeNode root) {
        if (root == null) return 1;
        // 左
        int leftCoverd = invert(root.left);
        // 右
        int rightCoverd = invert(root.right);
        // 中(3*3棋盘 状态转移)
        int midCoverd;
        if (leftCoverd == 0 || rightCoverd == 0) {
            midCoverd = 2;
            count++;
        } else if (leftCoverd == 2 || rightCoverd == 2) {
            midCoverd = 1;
        } else {
            midCoverd = 0;
        }
        return midCoverd;
    }
}

力扣题解

动态规划

https://leetcode.cn/problems/binary-tree-cameras/solutions/422860/jian-kong-er-cha-shu-by-leetcode-solution/ (opens in a new tab)

class Solution {
    public int minCameraCover(TreeNode root) {
        int[] array = dfs(root);
        return array[1];
    }
 
    public int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[]{Integer.MAX_VALUE / 2, 0, 0};
        }
        int[] leftArray = dfs(root.left);
        int[] rightArray = dfs(root.right);
        int[] array = new int[3];
        array[0] = leftArray[2] + rightArray[2] + 1;
        array[1] = Math.min(array[0], Math.min(leftArray[0] + rightArray[1], rightArray[0] + leftArray[1]));
        array[2] = Math.min(array[0], leftArray[1] + rightArray[1]);
        return array;
    }
}