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

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

文章链接：代码随想录

视频链接：LeetCode:738.单调递增的数字

题目链接：力扣题目链接

图释：

从后向前遍历，当后一位数大于前一位位数时，前一位数减减，后一位数赋值为9（最大）

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strNum = to_string(n); //将整型转换成字符串类型，方便我们遍历
        int flag = strNum.size(); // 赋值为字符串的长度，当原整型满足递增时，就不会走第二个循环
        for(int i=strNum.size()-1; i>0; i--){ //小于0，为了防止i-1出现负数
             if(strNum[i-1]>strNum[i]){
                 strNum[i-1]--; // 前一位进行--
                 flag = i; // 当前位置要赋值成9
             }
        }
        for(int j=flag; j<strNum.size(); j++){
            strNum[j]='9'; //统一将后面的数全部赋值为9
        }
        return stoi(strNum);  // 字符串转整型
    }
};

题目：968.监控二叉树

文章链接：代码随想录

视频链接：LeetCode:968.监控二叉树

题目链接：力扣题目链接

图释：

class Solution {
public:
    int result; 
    // 0 无覆盖
    // 1 有摄像头
    // 2 有覆盖
    int traversal(TreeNode* root){
        // 终止条件
        if(root == NULL) return 2;
        // 后序遍历(左右中)
        int left = traversal(root->left);
        int right = traversal(root->right);
        // 单层逻辑
        if(left==2 && right==2) return 0; // 左右孩子都有覆盖则，父节点为无覆盖
        if(left==0 || right==0){  // 无覆盖的时候，优先级更高一点
            result++;
            return 1;  // 左右孩子只要有一个无覆盖，则父节点为有摄像头
        }
        if(left==1 || right==1) return 2; // 左右孩子只要一个摄像头，则父节点为有覆盖

        return -1;
    }
    int minCameraCover(TreeNode* root) {
        // if(root==NULL) return 0;
        result = 0;
        if(traversal(root)==0){
            result++; // 如果最后根节点为无覆盖的情况，则根节点设置为摄像头
        }
        return result;
    }
};

题目：总结

文章链接：代码随想录