代码随想录训练营Day36：Leetcode738、968

Leetcode738：

问题描述：

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

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

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

代码及注释解析：

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        //个位数直接返回
        if(n<10)return n;
 
        //最多十位数
        int arr[10];
 
        //拆分每一位存储，便于贪心
        int i=0;
        while(n>0){
            arr[i++]=n%10;
            n=n/10;
        }
 
        if(isKey(arr,i)){
 
            return f(arr,i);
        }
 
        //开始贪心，该数组必须变成最大的非递减数组
        for(int j=0;j<i-1;j++){
            //找到从低位开始的第一个逆序对，因为要尽力少减点的
            if(arr[j]<arr[j+1]){
                arr[j+1]-=1;
                //拉满低位能满足要求的最大
                for(int p=0;p<=j;p++){
                    arr[p]=9;
                }
                if(isKey(arr,i)){
                    return f(arr,i);
                }
            }
        }
        return f(arr,i);
 
       
 
        
    }
 
    //是否是满足题目要求的数组
    bool isKey(int* arr,int n){
        for(int i=0;i<n-1;i++){
            if(arr[i]<arr[i+1])return false;
 
        }
        return true;
    }
 
    //数组转整型
    int f(int*arr,int n){
 
        int sum=0;
        for(int i=n-1;i>=0;i--){
            sum=sum*10+arr[i];
        }
        return sum;
    }
};

Leetcode968：

问题描述：

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

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

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

代码及注释解析：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int result=0;
    int minCameraCover(TreeNode* root) {
        //开始装摄像头！！！
        if(dfs(root)==0){
            result+=1;
        }
        return result;
    }
 
    int dfs(TreeNode* root){
        //空节点都是覆盖
        if(!root)return 2;
 
        //递归到左右子树放置摄像头
        int left=dfs(root->left);
        int right=dfs(root->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;
    }
};