738. 单调递增的数字

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

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

示例 1:

输入: N = 10
输出: 9

 分析：

这道题是今年某大厂的一道笔试题，印象很深刻，因为没做出来。

这道题的思路比较简单，就是找到第一个不严格递增（小于下一个）的数字，让他 -1 ，然后后续数字都变为 9 就好了。不过该怎么找当时第一个不递增的数字呢？从前向后找肯定不行，举例来说，332 -> 329 但是由于 第二位 -1 以后，第一位和第二位又出现了矛盾，于是我们不能从前往后找，那么从后往前找行不行呢？ 还是以 332 举例，从后往前找第一位是 2 ，因为 3 大于 2， 所以 变为 329，然后再找第二位是 2 （第2位已经变化了！），因为 3 大于 2， 所以变为 299。正解。

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

 968. 监控二叉树

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

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

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

示例 1：

输入：[0,0,null,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 {
public:int result;int dfs(TreeNode* cur) {if (cur==NULL) return 2;int left = dfs(cur->left);int right = dfs(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;}int minCameraCover(TreeNode* root) {if (dfs(root) == 0) return result+1;else return result;}
};