目录

一、(leetcode 738)单调递增的数字

二、(leetcode 968)监控二叉树


一、(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;
    }
};
10-29 18:47