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

738. 单调递增的数字

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

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

文章讲解/视频讲解：https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html

思路

将整数n转化成字符串num来处理，遍历num的每一位，如果当前下标index指向的数字num[index]大于num[index+1]，则将num[index]减一，并回退进行判断，一直回退到当前[0,index]构成的数字单调递增为止。如果在遍历的过程中有回退操作，那么[0, index]构成的数字一定小于原数字，为了使获得的数字最大，将后续的数字全部赋予’9’。

写代码的时候把自己绕晕了，debug了好久。。

C++实现

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string num = to_string(n);
        int curIdx = 0;
        bool backtrack = false;
        while(curIdx < num.size() - 1){
            if(backtrack){
                num[curIdx] = '9';
                curIdx++;
                continue;
            }
            if(num[curIdx] <= num[curIdx + 1]){
                curIdx++;
            }
            else{
                while(curIdx >= 0 && num[curIdx] > num[curIdx + 1]){
                    num[curIdx] -= 1;
                    curIdx--;
                }
                curIdx+=2;
                backtrack = true;
            }
        }

        if(backtrack) num[num.size() - 1] = '9';

        int result = stoi(num); // 不用管前导0
        return result;
    }
};

968. 监控二叉树

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

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

文章讲解/视频讲解：https://programmercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html

思路

尽量让叶子节点的父节点安装摄像头，因此是从下往上遍历，采用后序遍历。

定义每个节点可能的状态：

• 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：头节点没有覆盖

这时为头节点加一个摄像头。

这题没做出来，mark一下，回溯+贪心

C++实现

class Solution {
public:
    int result;

    int traversal(TreeNode* node){
        if(node == nullptr) return 2;

        int left = traversal(node->left);
        int right = traversal(node->right);

        if(left == 2 && right == 2) return 0;

        if(left == 0 || right == 0){
            result += 1;
            return 1;
        }

        if(left == 1 || right == 1){
            return 2;
        }

        return -1;
    }

    int minCameraCover(TreeNode* root) {
        result = 0;
        int head = traversal(root);
        if(head == 0) result += 1;
        return result;
    }
};

贪心总结

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