代码随想录day37

738.单调递增的数字 

先转成字符串，如果出现x>y，让x--，记录y的下标位置，最后从y的下标位置往后都赋值成9，最后再转回int。

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s=to_string(n);
        int flag=s.size();
        for(int i=s.size()-1;i>0;i--){
            if(s[i-1]>s[i]){
                s[i-1]--;
                flag=i;
            }
        }
        for(int i=flag;i<s.size();i++){
            s[i]='9';
        }
        return stoi(s);
    }
};

968.监控二叉树 

优先在叶子节点的父节点放摄像头，然后每隔两个节点放一个摄像头，因为叶子结点的数量相对于根节点的数量是指数级的，所以从低向上考虑，所以用后序遍历。

注意函数返回的是状态信息，不是最后的结果。

class Solution {
public:
    int res;
    int traversal(TreeNode* node){
        if(node==NULL) return 2;
        //后序遍历
        int left=traversal(node->left);
        int right=traversal(node->right);
        if(left==2&&right==2) return 0;
        if(left==0||right==0){
            res++;
            return 1;
        } 
        if(left==1||right==1) return 2;
        return -1;
    }
    int minCameraCover(TreeNode* root) {
        res=0;
        if(traversal(root)==0) res++;
        return res;
    }
};