738.单调递增的数字

参考文档：代码随想录

题目：

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

• 示例 1:
  输入: N = 10
  输出: 9
  示例 2:
• 输入: N = 1234
  输出: 1234
• 示例 3:
  输入: N = 332
  输出: 299
  说明: N 是在 [0, 10^9] 范围内的一个整数。

分析：
获取一个整数n的每一位数字：
求余和除交替操作。

bool increase(int n){while(n){int t = n % 10;cout << t << " ";n = n / 10;}
}

转为字符串。

string num = to_string(n);
for(int i = 0; i < num.size(); i++) cout << num[i] << " ";

解题思路：

1. 为什么从后到前，而不是从前到后：从前到后遇到前大于后，前减一可能会影响到再前一个。而从后到前遇到前小于后，前减一，再继续向前，如果前还是小于后，前再减1。关键是找到最后的位置，之后将此位置之后的所有数都置为9。
2. 条件满足：若前大于后，要满足前小于等于后的最大值是（前减一，9）。

代码：

class Solution {
public:int monotoneIncreasingDigits(int n) {// 如何获取n的位数//从后到前，遇到 后大于前 继续，遇到 后小于前 前-1，后面都变成9 string num = to_string(n);int pos = num.size();//记录位置for (int i = (num.size() - 1); i > 0; i--){if((num[i] - num[i-1]) < 0){pos = i;num[i-1] -= 1;}}for(int i = pos; i < num.size(); i++) num[i] = '9';return stoi(num);}
};

968.监控二叉树

参考文档：代码随想录

题目：

分析：

1. 最终的return指的是当前节点的值还是调用该节点的值：调用的返回值，树枝的值而非节点的值。
2. 对于 left == 2 && right == 2 处理 return 0；的理解。
   （从下到上遍历，所以是前一个，两个都是覆盖点对上一个节点什么都不提供）
3. if的处理顺序，先处理两个2，之后是两个不同时为2，只要有一个0就用一个摄像头弥补，之后是不可能出现0，只要一个1就向上提供一个覆盖范围。

代码：

/*** 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 {int result;int traversal(TreeNode* cur){//2：被覆盖；1：安装摄像头；0:没有被覆盖if(cur == NULL) return 2;int left = traversal(cur->left);int right = traversal(cur->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;}
public:int minCameraCover(TreeNode* root) {//有孩子，给孩子，没孩子，给自己，记录的标记。中序遍历，记录已经遍历过的节点（用一个数组，节点标记为1）result = 0;if(traversal(root) == 0){result++;}return result;}
};