1、LeetCode738单调递增的数字

题目链接：738、单调递增的数字

暴力解法：

判断是否单调递增，可以先定义一个max = 10；

m = num % 10取最后一个数字，判断是否max>=m;

num = num / 10去掉最后一个数字，再继续取最后的数字与max比较，一旦大于max，说明不是单调递增，return false;

class Solution {
public:bool checkNum(int num){int max = 10;while(num){int m = num % 10;if (max >= m){max = m;num = num / 10;}else{return false;}}return true;}int monotoneIncreasingDigits(int n) {while(n){if (checkNum(n)){return n;}else{n--;}}return 0;}
};

贪心解法：

一旦出现strNum[i - 1] > strNum[i]的情况，首先想让strNum[i - 1]--，然后strNum[i]为9。

而且定义一个falg，标记赋值9从哪里开始。flag初始化为strNum.size()。

to_string()

stoi()

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

2、LeetCode968监控二叉树

题目链接：968、监控二叉树

分为三种情况：0-该节点无覆盖，1-该节点有摄像头，2-该节点有覆盖

因为叶子结点多，应该尽可能让叶子结点的父节点有摄像头，才能让摄像头最少。

首先遍历时遇到空节点怎么办？

如果空节点状态为0无覆盖，则叶子结点必须为1有摄像头，不符合叶子结点的父节点有摄像头。

如果空节点状态为1有摄像头，则叶子结点为2有覆盖，叶子结点的父节点不需要有摄像头。

如果空节点状态为2有覆盖，则叶子结点为无覆盖，叶子结点的父节点要有摄像头。

所以遇到空节点应该返回状态2。

遍历时的情况：

左右孩子都有覆盖2，该节点为无覆盖0；

左右孩子至少有一个无覆盖，则该节点一定要有摄像头1；result++;

左右孩子其中有一个摄像头，则该节点有覆盖2；

递归结束后头结点可能为0无覆盖，则让头结点状态变为有摄像头。result++。

/*** 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 traversal(TreeNode * cur){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;}int minCameraCover(TreeNode* root) {result = 0;if (traversal(root) == 0) result++;return result;}
};