Day37｜贪心算法part06：738.单调递增的数字、968. 监控二叉树、贪心总结

738. 单调递增的数字

总体思想就是从后往前遍历，比较第i位和第i+1位的大小，不符合顺序char[i]减1，i+1位填9，找到需要填9的最先位置，然后填9。

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

• 数据转换：n → String → char[] → String→ n
• Integer.parseInt：String->int
• String.valueOf(n)：int → String

968. 监控二叉树

https://programmercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E6%80%9D%E8%B7%AF

这题之前完全没做过，直接看题解了。

• 贪心：尽可能把摄像头放在非叶子结点，且从下往上看（指数级更省（
• 此时，大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。

直接看代码，这里构造了虚拟根节点来将处理root的逻辑一般化：

class Solution {
        private int res = 0;

        private int traversal(TreeNode node){
            //0表示没被覆盖；
            //1表示装了摄像头；
            //2表示状态是被覆盖到。
            if(node == null){
                return 2;//2表示状态是被覆盖到。
            }
            int left = traversal(node.left);
            int right = traversal(node.right);

            //左右都被覆盖，在本结点肯定没被覆盖（按我们的贪心思想）
            if(left == 2 && right == 2){
                return 0;
            }
            //左右都没被覆盖，装摄像头
            if(left == 0 || right == 0){
                res++;//装摄像头
                return 1;
            }
            //左右有一个装了摄像头，本节点被照到
//            else if(left == 1 || right == 1){
//                return 2;
//            }
            else {
                return 2;
            }

        }
        public int minCameraCover(TreeNode root) {
            //考虑根节点是否被覆盖
            TreeNode dummyRoot = new TreeNode();
            dummyRoot.left = root;
            traversal(dummyRoot);

            return res;
        }
    }

贪心总结

https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E7%AF%87.html#%E8%B4%AA%E5%BF%83%E6%AF%8F%E5%91%A8%E6%80%BB%E7%BB%93

最近发现总结还有每道题的总结，之后大批量刷的时候根据总结去刷题。