目录
一、（leetcode 738）单调递增的数字
暴力方法肯定是超时，因此需要逐位进行判断：如果i-1的数字大于i的位置，就把i处的值变为9，i-1处的值减一。这个方法从局部出发，如果说想要从这个局部最优扩展到全局最优，需要使全局最优的答案可以复用局部最优，就只能从后往前判断而不是从前往后，和重叠区间有一点点逻辑上的类似，但是不好描述，用心体会。
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string number = to_string(n);
int len = number.size(), flag = len;
// flag从后向前遍历，确定从哪里开始向后替换为9
for(int i = len-1; i > 0; --i){
if(number[i-1] > number[i]){
flag = i;
number[i-1]--;
}
}
for(int i = flag; i < len; ++i){
number[i] = '9';
}
return stoi(number);
}
};二、（leetcode 968）监控二叉树
这道题最重要的第一步就是知道要从哪里出发进行判断，根据这个方向再确定二叉树的遍历序列，再进行逻辑设计。所以应该是从叶子结点出发，将叶子节点的父节点装上摄像头，根据这个方向，可以使用左右中的递归顺序，这样可以在回溯的时候对中间节点进行逻辑判断，为此我们需要对每个节点的状态进行讨论，可以用3钟状态来描述：无覆盖0，有摄像头1，被覆盖2。需要注意的是空节点的状态应该是2。具体的逻辑分析参考代码，最后需要再额外对根节点进行判断，总体而言是个很难的问题，需要多多体会巩固。
/**
* 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 res;
int traversal(TreeNode* root){
if(root == nullptr) return 2;
int left = traversal(root->left);
int right = traversal(root->right);
// 逻辑判断
if(left == 2 && right == 2){
return 0;
}else if(left == 0 || right == 0){
res++;
return 1;
}else if(left == 1 || right == 1){
return 2;
}
return -1;
}
int minCameraCover(TreeNode* root) {
res = 0;
if(traversal(root) == 0){
res++;
}
return res;
}
};