【代码随想录】刷题Day37

1.单调递增的数字

738. 单调递增的数字

解释一下题目：其实就是将小于输入的数n，并且该数从左到右非递减的最大符合这两条件的数返回。

贪心的思路：如果给出的n就是非递减的，那么最大的就是它本身。如果给的n不是非递减的，我们其实可以看出一些规律，比如，如果我们要最大的非递减，那么最后取9才是最稳妥的，那么大致方向就是找n是否非递归，然后调节数字

1.定义string s由n转化，flag用来标记9出现的位置

2.遍历s，由最后一位开始，为什么这样，首先我们已经知道我们需要将递减的位置变为9，那么比较相邻两位就可以了。不过我们如果是从左往右我们无法清楚到底是不需要少一位还是需要少一位，比如输入10要输出9，就是右往左就能避免。

3.遍历中，if (s[i] < s[i - 1])，说明此时的位置数字递减，那么s[i - 1]--将前一位减一处理，flag = i将要置为9的位置更新到当下位置

4.最后将拿到的flag位置遍历到最后，将位置上的数字置为9

5.stoi转换回去

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] < s[i - 1])
            {
                s[i - 1]--;
                flag = i;
            }
        }
        for (int i = flag; i < s.size(); i++)
            s[i] = '9';
        return stoi(s);
    }
};

2.监控二叉树

968. 监控二叉树

1.先分析从上到下安装还是从下到上安装。首先，我们知道根节点安装还是叶子节点安装其实都存在所谓的“浪费”，因为跟节点没有父节点，而叶子节点没有孩子节点。不过根节点只有一个，而叶子节点有很多，所以我们不在任何叶子节点上安装摄像头，这样子减少了一部分不必要的摄像头数量了

2.由于摄像头可以观察相邻的位置，那么此时我们就有了两种状态：一种是有摄像头；一种是无摄像头。那么由于相邻的位置，摄像头是可以看见的，所以我们安装摄像尽量隔开两个位置。那么自下而上安装摄像头时，会出现三种状态：一种是有摄像头；一种是已经被监视；另外一种是需要被监视。我们分别定义为1，2，0返回。

3.那么空节点应该返回什么呢？我们意识到空节点的父节点就是叶子节点，叶子节点不能是有摄像头的状态，它是需要被监视的状态，那么空节点返回为已经被监视，这样就不会被干扰了，返回2

4.如果左右节点为2，说明此时左右都被监视了，那么目前的节点是需要被监视的状态返回给上面就是0；如果有一个节点是0，说明此时就需要一个摄像头去监视，不然再往上就没有摄像能看到了，因此ret++，返回1；如果有一个节点是1，说明此时需要往上返回2，告诉上层当前位置是被监视的状态。顺序是不能变的，我们按从下到上思路过一遍，由于一定先碰到叶子节点，所以先判断左右节点是否为2；随后就是需要被设置摄像头的节点，所以判断如果有节点是0的情况；最后判断被监视的情况，即节点为1情况

5.注意，我们此时没有对根节点进行任何处理，那么我们需要清楚，如果根节点为0状态，则没有它的父节点对他进行监视，所以根节点上需要放一个，那这个判断在递归结束后，我们观察到，如果最后root返回的是0，则ret++

class Solution {
public:
    int _CameraCoverR(TreeNode* root,int& ret)
    {
        if(root==nullptr)
            return 2;
        int left = _CameraCoverR(root->left,ret);
        int right = _CameraCoverR(root->right,ret);
        if(left==2&&right==2)
            return 0;
        if(left==0||right==0)
        {
            ret++;
            return 1;
        }
        if(left==1||right==1)
            return 2;
        return 0;
    }
    int minCameraCover(TreeNode* root) {
        int ret = 0;
        if(_CameraCoverR(root,ret)==0)
            ret++;
        return ret;
    }
};