738.单调递增的数字

链接：LeetCode738.单调递增的数字

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

为了方便遍历每一位上的数字，将所给数字转变为字符串。从头到尾遍历该字符串或者从尾到头遍历该字符串都是可以的。本解法采用的是从尾到头遍历该字符串。本题要求的是找出最大的满足条件的数字。9是所有单位数字中最大的值，所以每当遇到str[i]>str[i+1]时，就先将str[i]减一，之后将i之后(不包括i)位置的数字变成‘9’。最后将字符串转变为整数。

968.监控二叉树

链接：968.监控二叉树

/*** 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 minCameraCover(TreeNode* root) {if(getnums(root)==0) ++ans;return ans;}
private:/*0:无覆盖1:有摄像头2:有覆盖*/int ans=0;int getnums(TreeNode *cur){//递归终止条件if(!cur) return 2;int left = getnums(cur->left);int right = getnums(cur->right);if(left==2&&right==2) return 0;//情况一if(left==0 || right==0) {++ans;return 1;}//情况二if(left==1 || right==1) return 2;//情况三return -1;}
};

代码随想录思路讲解
摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费一层的覆盖。把摄像头放在叶子节点的父节点的位置，才能充分利用摄像头的覆盖面积。

为什么不从头节点开始看起呢？因为头节点不放摄像头可以省下一个摄像头，叶子节点不放摄像头可以省下指数级别的摄像头。

所以从下往上看，局部最优：让叶子节点的父节点安装摄像头，所用摄像头最少；整体最优：全部摄像头数量所用最少。

大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头节点。

首先确定遍历顺序。
使用后序遍历，可以在回溯的过程中从下到上进行推导。
如何隔两个节点放一个摄像头。
首先看看每个节点可能有几种状态并用数字表示：

• 该节点无覆盖：0
• 本节点有摄像头：1
• 本节点有覆盖：2

那么空节点是哪一种状态呢？
为了让摄像头数量最少，尽量让叶子节点的父节点安装摄像头，这样才能使摄像头的数量最少。空节点如果是无覆盖或者有摄像头的状态，都不用在叶子节点的父节点安装摄像头，所以空节点只能是有覆盖2的状态。

主要有以下四种情况：

• 情况一：左右节点都有覆盖。那么父节点的状态为无覆盖。

• 情况二：左右节点至少有一个无覆盖的。父节点应该安装摄像头。
  1.left == 0 && right == 0左右节点无覆盖
  2.left == 0 && right == 1左节点无覆盖右节点有摄像头
  3.left == 0 && right==2左节点无覆盖右节点有覆盖
  4.left == 1 && right == 0左节点有摄像头右节点无覆盖
  5.left == 2 && right == 0左节点有覆盖右节点无覆盖

• 左右节点至少一个有摄像头。父节点的状态为有覆盖。
  1.left == 1 && right == 1左右节点都有摄像头。
  2.left == 1 && right ==2左节点有摄像头右节点有覆盖
  3.left == 2 && right == 1左节点有覆盖右节点有摄像头。

• 单独观察头节点的情况。(因为不论头节点是什么状态，都会在遍历到头节点的时候退出程序，如果头节点没有被覆盖摄像头的数量不会加一。 另外一种比较方便的操作就是设置一个虚拟头节点，这样就不会遗漏头节点的状态。)