【随想录】Day37—第八章 贪心算法 part06

题目1: 单调递增的数字

• 题目链接：738. 单调递增的数字

1- 思路

• 1. 转 String：将 int 类型的数转为 String 类型，之后通过
• 2. 逆向遍历：从后往前遍历 String
• 3. 处理思路：从 size()-2 遍历到 i >= 0
  • 处理情况：当当前元素 i 的元素值大于 后一位 i+1 ，此时需要处理
  • 处理逻辑：令 i 的元素值为当前元素值减一，同时定义 start 记录 i 的位置

2- 题解

⭐ 单调递增的数字——题解思路

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String str = Integer.toString(n);
        char[] chars = str.toCharArray();
        int start = str.length();

        for (int i = str.length() - 2; i >= 0; i--) {
            if (chars[i] > chars[i + 1]) {
                chars[i]--;
                start = i+1;
            }
        }
        for(int i = start ; i<chars.length ;i++){
            chars[i] = '9';
        }
        return Integer.parseInt(String.valueOf(chars));
    }
}

题目2: 监控二叉树

• 题目链接：968. 监控二叉树

1- 思路

贪心思路

• 通过从下网上遍历的方式，则采取二叉树的 后序遍历 ，即 左右中方式
• 在叶子结点的上一个结点放摄像头，每隔两个结点放一个摄像头，直到遍历到根节点为止

定义结点状态

• 0 代表这个结点没覆盖
• 1 代表这个结点有摄像头
• 2 代表当前这个结点有覆盖的状态
• 空节点一定是有覆盖状态，才能满足 叶子结点的父节点是有摄像头

后续遍历逻辑

• 情况1：左右孩子都有覆盖 ——> 父节点只能是状态0，等待父节点的父节点装摄像头
• 情况2：左右孩子至少有一个无覆盖 ——> 此时 父节点 必须要装一个摄像头，只有父节点装了摄像头才能将当前结点的另一个孩子给覆盖
• 情况3：左右孩子有一个有摄像头 ——> 此时 父节点一定是覆盖状态
• 情况4：根节点无覆盖 ——> 此时 要对根节点加一个摄像头

2- 题解

⭐ 监控二叉树——题解思路

class Solution {
    int res = 0;
    public int minCameraCover(TreeNode root) {
        if(Traversal(root)==0){
            res++;
        }
        return res;
    }


    public int Traversal(TreeNode root){
        if(root== null){
            return 2;
        }
        int left = Traversal(root.left);
        int right = Traversal(root.right);
        // 左右孩子都覆盖
        if(left==2 && right==2){
            return 0;
        }
        // 左右至少有一个无覆盖
        if(left==0 || right==0){
            res++;
            return 1;
        }
        // 左右有一个摄像头，当前被覆盖
        if(left==1 || right==1){
            return 2;
        }
        
        return -1;
    }
}