Day37 贪心 part06

738.单调递增的数字

我的思路：
一开始的思路只从后向前遍历调整arraylist，100的案例没过，应该输出99，我输出90，顿时联想到分糖果问题，果断加了从前向后检查调整的遍历，没问题

解答：

class Solution {
    public int monotoneIncreasingDigits(int n) {
        int res = 0;
        int count = 1;
        ArrayList list = new ArrayList();
        while(n > 0) {
            list.add(0, n % 10);
            n /= 10;
        }
        for(int i = list.size() - 2; i >= 0; i --) {
            if((Integer)list.get(i) > (Integer)list.get(i + 1)) {
                list.set(i, (Integer)list.get(i) - 1);
                list.set(i + 1, 9);
            }
        }
        for(int i = 1; i < list.size(); i ++) {
            if((Integer)list.get(i) < (Integer)list.get(i - 1)) {
                list.set(i, 9);
            }
        }
        for(int i = list.size() - 1; i >= 0; i --) {
            res += (Integer)list.get(i) * count;
            count *= 10;
        }
        return res;
    }
}

968.监控二叉树

我的思路：
对着代码理解了一下，开始还不理解有覆盖为什么返回2，然后发现只是卡哥标记的一种节点状态

解答：

class Solution {
    public int result;
    public int traversal(TreeNode curr) {
     	// 空节点，该节点有覆盖
        if(curr == null) {
            return 2;
        }
        int left = traversal(curr.left);
        int right = traversal(curr.right);
        // 情况1
        // 左右节点都有覆盖
        if(left == 2 && right == 2) {
            return 0;
        }
        // 情况2
        // left == 0 && right == 0 左右节点无覆盖
        // left == 1 && right == 0 左节点有摄像头，右节点无覆盖
        // left == 0 && right == 1 左节点有无覆盖，右节点摄像头
        // left == 0 && right == 2 左节点无覆盖，右节点覆盖
        // left == 2 && right == 0 左节点覆盖，右节点无覆盖
        else if(left == 0 || right == 0) {
            result++;
            return 1;
        }
        // 情况3
        // left == 1 && right == 2 左节点有摄像头，右节点有覆盖
        // left == 2 && right == 1 左节点有覆盖，右节点有摄像头
        // left == 1 && right == 1 左右节点都有摄像头
        else {
            return 2;
        }
    }
    public int minCameraCover(TreeNode root) {
        result = 0;
        //情况4
        //root无覆盖
        if(traversal(root) == 0) {
            result ++;
        }
        return result;
    }
}