算法训练营day36

1.单调递增的数字

参考链接代码随想录 (programmercarl.com)

题目要求小于等于N的最大单调递增的整数，那么拿一个两位的数字来举例。

例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]–，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。

是从前向后遍历还是从后向前遍历呢？

从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。

那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299

确定了遍历顺序之后，那么此时局部最优就可以推出全局，找不出反例，试试贪心。

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int start = s.length(); //当 n 本身就是单调递增(1234)，更改9不会影响结果
        for (int i = s.length() - 2; i >= 0; i--) {
            if (chars[i] > chars[i + 1]) {
                chars[i]--;
    //start在刚被减小的值后面，保证更改数值更改到最高位(或结束时)，比它小的位都是9
                start = i+1;
            }
        }
        for (int i = start; i < s.length(); i++) {
            chars[i] = '9';
        }
        return Integer.parseInt(String.valueOf(chars));
    }
}

2.968监控二叉树

1. 定状态，不在监控范围为uncover(0)，在监控范围cover(1)，该节点装了摄像头set(2)

2. 如何更少的装摄像头 -> 尽可能分散(具体来讲是自底向上安装摄像头，在叶子节点的父节点安装摄像头，然后每隔两层再装)

3. 如何判断一个结点是否需要被安装摄像头？

   当这个节点的子节点处于uncover的状态的时候必须安装摄像头(因为是从底向上安装，上面的还会有更上层的节点(对应的父节点)监控，但是下层节点过了之后就没办法再安装了)

class Solution {
    public int minCameraCover(TreeNode root) {
        setCamera(root, false);
        return res;
    }

    int res = 0;

    // 定义：输入以 root 为根的二叉树，以最优策略在这棵二叉树上放置摄像头，
    // 然后返回 root 节点的情况：
    // 返回 -1 代表 root 为空，返回 0 代表 root 未被 cover，
    // 返回 1 代表 root 已经被 cover，返回 2 代表 root 上放置了摄像头。
    int setCamera(TreeNode root, boolean hasParent) {
        if (root == null) {
            return -1;
        }
        // 获取左右子节点的情况
        int left = setCamera(root.left, true);
        int right = setCamera(root.right, true);

        // 根据左右子节点的情况和父节点的情况判断当前节点应该做的事情
        if (left == -1 && right == -1) {
            // 当前节点是叶子节点
            if (hasParent) {
                // 有父节点的话，让父节点来 cover 自己
                return 0;
            }
            // 没有父节点的话，自己 set 一个摄像头
            res++;
            return 2;
        }

        if (left == 0 || right == 0) {
            // 左右子树存在没有被 cover 的
            // 必须在当前节点 set 一个摄像头
            res += 1;
            return 2;
        }

        if (left == 2 || right == 2) {
            // 左右子树只要有一个 set 了摄像头
            // 当前节点就已经是 cover 状态了
            return 1;
        }

        // 剩下 left == 1 && right == 1 的情况
        // 即当前节点的左右子节点都被 cover
        if (hasParent) {
            // 如果有父节点的话，可以等父节点 cover 自己
            return 0;
        } else {
            // 没有父节点，只能自己 set 一个摄像头
            res++;
            return 2;
        }
    }
}