代码随想录算法训练营第三十七天|738.单调递增的数字，968.监控二叉树

738.单调递增的数字

题目链接：704. 二分查找

文档讲解：代码随想录

视频讲解：贪心算法，思路不难想，但代码不好写！LeetCode:738.单调自增的数字

思路

数要尽可能的大，高位开始尽量不变，从低位开始找到不满足递减的第一个位置，当前位置减1，后面的全都变成9即可。

代码

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strNum = to_string(n);
        int idx;
        for (int i = strNum.size() - 1; i > 0; i--) {
            if (strNum[i - 1] > strNum[i]) {
                strNum[i] = '9';
                strNum[i - 1]--;
            }
        }
        return stoi(strNum);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

968.监控二叉树

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

文档讲解：代码随想录

视频讲解：贪心算法，二叉树与贪心的结合，有点难… LeetCode:968.监督二叉树

思路

很容易想到要从叶子结点的父节点开始每隔两个结点放一个摄像头为局部最优，但是怎样表示一个结点的状态（有摄像头，没有摄像头但被摄像头覆盖，没有摄像头也没有被摄像头覆盖）是个难点。

后序遍历递归返回值选择int型，返回0、1、2，其中0表示没有摄像头也没有被摄像头覆盖，1表示有摄像头，2表示没有摄像头但被摄像头覆盖。

空结点处理：

• 如果空结点是未被覆盖状态，这时叶子结点就需要放摄像头，不是局部最优；
• 如果空结点是有摄像头状态，这时叶子结点被覆盖，叶子结点的父节点不用放置摄像头，而父节点的父节点放置摄像头，这时叶子结点没有被覆盖；
• 如果空结点是被覆盖状态，则叶子结点不用放置摄像头，叶子结点的父节点放置摄像头即可，是局部最优。

分四种情况：

• 情况一：左右结点都有覆盖，这时当前结点不用放置摄像头，当前节点的父结点放置摄像头，返回0
• 情况二：左右结点至少有一个未被覆盖，这时当前结点需要放置摄像头，返回1
• 情况三：左右结点至少有一个摄像头，且另一个结点被覆盖，这时当前结点不需要放置摄像头，且被左右结点覆盖，返回2；
• 情况四：如果递归完后，根结点没有被覆盖，则根结点也需要放置一个摄像头

代码

class Solution {
public:
    int minCameraCover(TreeNode *root) {
        // 情况4
        if (traversal(root) == 0)
            // root无覆盖
            result++;
        return result;
    }

private:
    int result = 0;
    int traversal(TreeNode *node) {
        // 空结点，该结点有覆盖
        if (node == NULL)
            return 2;

        int left = traversal(node->left);
        int right = traversal(node->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 左节点覆盖，右节点无覆盖
        if (left == 0 || right == 0) {
            result++;
            return 1;
        }

        // 情况3
        // left == 1 && right == 2 左节点有摄像头，右节点有覆盖
        // left == 2 && right == 1 左节点有覆盖，右节点有摄像头
        // left == 1 && right == 1 左右节点都有摄像头
        // 其他情况前段代码均已覆盖
        if (left == 1 || right == 1)
            return 2;

        return -1;
    }
};
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
37
38
39
40
41
42
43
44
45
46
47
48