代码随想录算法训练营第37天（贪心算法06 ● 738.单调递增的数字 ● 968.监控二叉树 ● 总结

738.单调递增的数字

题目链接： 738.单调递增的数字
文章/视频链接: 738.单调递增的数字

解题思路

1. 一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9。
2. 考虑遍历顺序，只有从后向前遍历才能重复利用上次比较的结果。
3. 用一个flag来标记从哪里开始赋值9。

不熟悉的基础语法知识

int型数字转换为字符串再转化为字符数组
char[] strN = Integer.toString(n).toCharArray();
字符数组转化为字符串再转化为Int型数字的两种方式
Integer.parseInt(new String(strN));
Integer.parseInt(String.valueOf(chars));

// 贪心
class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] strN = Integer.toString(n).toCharArray();
        int flag = strN.length;
        for(int i = strN.length - 1; i>0; i--){
            if(strN[i-1] > strN[i]){
                strN[i-1]--;
                flag = i;    
            }
            
        }
        for(int i = flag; i < strN.length; i++){
            strN[i] = '9';
        }

        return Integer.parseInt(new String(strN));

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

968.监控二叉树 （可以跳过）

本题是贪心和二叉树的一个结合，比较难，一刷大家就跳过吧。
题目链接： 968.监控二叉树
文章/视频链接: 968.监控二叉树

解题思路

我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！

1. 确定遍历顺序
   后序遍历
2. 考虑状态转移的情况分类
   每个节点可能有几种状态：

• 该节点无覆盖
• 本节点有摄像头
• 本节点有覆盖

我们分别有三个数字来表示：

• 0：该节点无覆盖
• 1：本节点有摄像头
• 2：本节点有覆盖

空节点的状态只能是有覆盖，这样就可以在叶子节点的父节点放摄像头了

3. 单层递归情况分类

• 情况1：左右节点都有覆盖
  左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
• 情况2：左右节点至少有一个无覆盖的情况
  如果是以下情况，则中间节点（父节点）应该放摄像头
• 情况3：左右节点至少有一个有摄像头
  如果是以下情况，其实就是 左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）
• 情况4：头结点没有覆盖
  以上都处理完了，递归结束之后，可能头结点 还有一个无覆盖的情况
  所以递归结束之后，还要判断根节点，如果没有覆盖，result++

 // 贪心＋二叉树
class Solution {
    int res = 0;
    public int minCameraCover(TreeNode root) {
        // 情况4：对根节点的状态做检验,防止根节点是无覆盖状态 .
        if(minCame(root) == 0){
            res++;
        }
        return res;
    }
    public int minCame(TreeNode root){
        if(root == null){
            // 空节点默认为 有覆盖状态，避免在叶子节点上放摄像头
            return 2;
        }
        int left = minCame(root.left); // 左
        int right = minCame(root.right); // 右
        // 中
        
       if(left == 2 && right == 2){  // 情况1   如果左右节点都覆盖了的话, 那么本节点的状态就应该是无覆盖,没有摄像头
           return 0;
       }else if(left == 0 || right == 0){  // 情况2 左右节点至少有一个是无覆盖状态,那 根节点此时应该放一个摄像头
           res++;
           return 1;
       }else{                // 情况3 左右节点至少存在 1个摄像头 那么本节点就是处于被覆盖状态
           return 2;
       }
    }
}
    /**
     节点的状态值：
       0 表示无覆盖
       1 表示 有摄像头
       2 表示有覆盖
    后序遍历，根据左右节点的情况,来判读 自己的状态
     */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

总结

可以看看贪心算法的总结，贪心本来就没啥规律，能写出个总结篇真的不容易了。