1.738单调递增的数字
贪心策略：如果strNum[i]<strNum[i-1]那么strNum[i] = '9',strNum[i-1]--;//比如87对应的最大的单调递增的就是79.
具体实现：
- 对于遇到小于的情况：如果strNum[i]<strNum[i-1]那么strNum[i] = '9',strNum[i-1]--;
- 遍历顺序必须得是一个反向遍历，这样才能保证找到最高位数需要进行改变的地方。（如果从左往右进行便利的话，会出现一种这样的情况，例如N = 999998前面的都相等，那么需要改变的是最右侧那个位置，明显不符合，所以要从右往左进行遍历）
- 使用flag来确定需要变成9的最左侧的位置
class Solution {
public:
int monotoneIncreasingDigits(int N) {
string strNum = to_string(N);
// flag用来标记赋值9从哪里开始
// 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
int flag = strNum.size();
for (int i = strNum.size() - 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);
}
};2.968监控二叉树
贪心策略：一个摄像头能够监控到更多的节点。
具体实现：
- 首先要确定的就是遍历顺序，是自顶向下还是自底向上的遍历顺序如果是自顶向下的话，那么就是判断父节点是否被覆盖，此时需要设置的节点就是：2,3,8,9,10,11,12,13,14,15.如果是自底向上的情况那么就是判断左右孩子节点是否被覆盖，此时需要设置的节点就是：4,5,6,7,1.所以确定的遍历顺序就是自底向上的情况。
- 再确定就是状态：分为三种状态：0：未被覆盖，1：存放摄像头，2：被覆盖三种状态。
- 对于空节点的处理：如果空节点的状态为0，那么叶子结点就需要设置为存放摄像头的，明显是不符合的，当空节点的状态为2的时候，此时叶子结点就不需要设置摄像头了，只需要在叶子结点的上方设置摄像头即可，所以空节点设置为2.
- 当前节点为2（被覆盖）：左右孩子中至少有一个是1（设置为节点），且左右孩子不能为0。
- 当前节点为1（设置摄像头）：左右孩子中至少有一个为0（未被覆盖）。
- 当前节点为0（为被覆盖）：左右孩子全都是2（被覆盖状态）。
- 对于最后根节点的处理：因为会出现一种情况就是如果23全都是被覆盖，那么设置的1就是为未覆盖状态（0）退出，但是不符合实际，此时需要将其变成设置摄像头（2），所以最后还需要在主函数里面判断返回值是否为0。
/**
* 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:
//节点分三种情况：
//0:没覆盖；1：该节点存放摄像头；2：该节点被覆盖
//当节点为空的时候设置为被覆盖
int result;
int traversal(TreeNode* cur){
if(cur == nullptr) 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;
}
//该节点设置为被覆盖
//1.left =1,right =1;
if(left == 1||right ==1){
return 2;
}
return -1;//代表的知识一个完整性
}
int minCameraCover(TreeNode* root) {
result = 0;
if(traversal(root) == 0){//对于最后一个根节点的处理，如果此时设置为0，代表未被覆盖，需要重新设置为1，即result++;
result++;
}
return result;
}
};
