算法打卡day32|贪心算法篇06|Leetcode 738.单调递增的数字、968.监控二叉树

算法题

Leetcode 738.单调递增的数字

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

大佬视频讲解：单调递增的数字视频讲解

个人思路

这个题目就是从例子中找规律，例如 332，从后往前遍历，32不是单调递增将2变为9,3减1，变成了329，遍历到2,32不是递增，将2变为9,3减1，变成299，符合题目条件，打印输出。

解法

贪心法

这道题只能从后往前遍历，因为如果是从前向后遍历的话，拿例子332看，第一步变成了292，第二步变成了289，并不是真正的结果299。

而从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299；确定了遍历顺序之后，发现局部最优就可以推出全局，可以用贪心

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);//int变为字符串
        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;//更改需要变为9的位置
            }

        }
        for (int i = start; i < s.length(); i++) {
            chars[i] = '9';
        }
        return Integer.parseInt(String.valueOf(chars));//转为integer类型
    }
}

时间复杂度:O(n)；（遍历字符串中的每个字符）

空间复杂度:O( 1);（无动态使用空间）

Leetcode 968.监控二叉树

题目链接:968.监控二叉树

大佬视频讲解：监控二叉树视频讲解

个人思路

一整个难住，看看题解...

解法

贪心法

根据题目所给例子，知道摄像头不能安装到叶子节点，因为这样会浪费一层监控空间，所以安装摄像头从下往上考虑，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点.

下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！局部最优可以推出全局最优，找不出反例，用贪心

1.确定遍历顺序

二叉树从低向上推导，可以使用后序遍历（左右中）

在遍历时取了左孩子的返回值，右孩子的返回值，以便推导中间节点的状态

2.隔两个节点放一个摄像头状态分析

每个节点可能有如下三种状态，可以分别有三个数字来表示

该节点无覆盖 -> 0
本节点有摄像头 -> 1
本节点有覆盖 -> 2

为了让摄像头数量最少，先叶子节点的父节点安装摄像头

终止条件：空节点的判断;返回状态值只能是有覆盖(2),否则不满足在叶子节点父节点安装摄像头

单层逻辑处理主要有如下四类情况：

情况1：左右节点都有覆盖

左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。

如图：

情况2：左右节点至少有一个无覆盖的情况

如果是以下情况，则中间节点（父节点）应该放摄像头：

left == 0 && right == 0 左右节点无覆盖
left == 1 && right == 0 左节点有摄像头，右节点无覆盖
left == 0 && right == 1 左节点有无覆盖，右节点摄像头
left == 0 && right == 2 左节点无覆盖，右节点覆盖
left == 2 && right == 0 左节点覆盖，右节点无覆盖

有一个孩子没有覆盖，父节点就应该放摄像头，摄像头的数量要加一，并且return 1，代表中间节点放摄像头。

情况3：左右节点至少有一个有摄像头

如果是以下情况，其实就是左右孩子节点有一个有摄像头了，那么其父节点就为2（覆盖的状态）

left == 1 && right == 2 左节点有摄像头，右节点有覆盖
left == 2 && right == 1 左节点有覆盖，右节点有摄像头
left == 1 && right == 1 左右节点都有摄像头

情况4：头结点没有覆盖

递归结束之后，可能头结点还有一个无覆盖的情况，如下图，所以递归结束之后，还要判断根节点，如果没有覆盖，result++

class Solution {
    int  res=0;
    public int minCameraCover(TreeNode root) {
        if(minCame(root)==0){// 情况4：对根节点的状态做检验
            res++;
        }
        return res;
    }
    
    public int minCame(TreeNode root){
        if(root==null){ // 空节点默认为 有覆盖状态，避免在叶子节点上放摄像头
            return 2;
        }

        int left=minCame(root.left);
        int  right=minCame(root.right);

        // 情况1：如果左右节点都覆盖了的话, 那么本节点的状态就应该是无覆盖,没有摄像头
        if(left==2&&right==2){:
            return 0;

        }else if(left==0||right==0){
            //情况2： 左右节点都是无覆盖状态,那 根节点此时应该放一个摄像头
            res++;
            return 1;// 状态值为 1 摄像头数 ++;

        }else{
            // 情况3：左右节点至少存在 1个摄像头，那么本节点就是处于被覆盖状态
            return 2;
        }
    }
}