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

738.单调递增的数字

代码随想录链接

题目

LeetCode-738.单调递增的数字

定义左位数字小于等于右位数字的整数为单调递增整数, 给定一个整数, 返回小于等于该整数的最大的单调递增整数.

自己的想法

如果要求最大的小于给定数字的单调递增数, 应该从后向前遍历, 遇到前一位数字大于后一位数字时, 前一位数字要-1且后位数字要变为9, 这样能保证这两位数字满足单调递增且是小于原数字的最大单调递增数, 这样就做到了局部最优.

由局部最优推广到全局最优, 就从后向前遍历并不断进行此类操作.

题解

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string numStr = to_string(n);
        int pos = numStr.size();
        for (int i = numStr.size() - 1;  i > 0; i--) {  // 从后向前遍历, 遇见前位数字大于后位数字的情况就将前位数字减一
            if (numStr[i - 1] > numStr[i]) {
                pos = i;
                numStr[i - 1]--;
            }
        }
        for (int i = pos; i < numStr.size(); i++)   // 将最后一次遇到前位数字大于后位数字情况的位置之后的所有数字改为9
            numStr[i] = '9';
        return stoi(numStr);
    }
};

968.监控二叉树

代码随想录链接

题目

LeetCode-968.监控二叉树

给定一棵二叉树, 一个节点安装了监控后可以监测到其自身, 父节点以及子节点, 求至少使用多少个监控能够将整个二叉树覆盖.

自己的想法

还是要遍历.

一个节点可能有三种情况, 无覆盖, 装了摄像头, 被其他节点的摄像头覆盖到. 如果要让使用的摄像头最少, 叶子节点一定不能装摄像头(因为这样一个摄像头能覆盖到的节点最少), 为了确保这点, 应该由底向上进行遍历, 所以应该是后序遍历.

题解

class Solution {
private:
    int result;     // 结果
    int traversal(TreeNode* cur) {  // 递归函数, 0 代表无覆盖, 1 代表装有摄像头, 2代表被覆盖
        if (cur == NULL) return 2;  // 如果当前是空节点, 应该返回被覆盖, 避免对其他节点的覆盖造成影响
        int left = traversal(cur -> left);  // 查找左子节点的状态
        int right = traversal(cur -> right); // 查询右子节点的状态

        if (left == 2 && right == 2) return 0;  // 如果两个孩子都是被覆盖而没有摄像头, 说明当前位置没有覆盖, 返回0
        else if (left == 0 || right  == 0) {    // 如果至少有一个孩子没有覆盖, 当前位置就需要安装一个摄像头, 并告知父节点
            result++;
            return 1;
        } else return 2;    // 上面两种情况都不符合, 就说明该节点也已经被覆盖
    }
public:
    int minCameraCover(TreeNode* root) {
        if (traversal(root) == 0) result++;
        return result;
    }
};