Studying-代码随想录训练营day31| 56.合并区间、738.单调递增的数字、968.监控二叉树、贪心算法总结

第31天，贪心最后一节(ง •_•)ง💪，编程语言：C++

56.合并区间

738.单调递增的数字

968.监控二叉树

贪心算法总结

56.合并区间

文档讲解：代码随想录合并区间

视频讲解：手撕合并区间

题目：

学习：本题属于区间问题，同样是找到重合的区间，与用最少数量的箭引爆气球和无重叠区间问题解法是相同的。

本题可以先对区间进行排序，便于找到重叠区间，可以依照每个区间的左边界从小到大排序。之后比较后续区间的左边界，与前一个区间的右边界的关系，判断是否重叠。如果不重叠，则加入答案数组中，如果重叠则更新最大右边界。

代码：

//时间复杂度O(nlogn)快速排序时间复杂度
//空间复杂度O(logn)快速排序空间复杂度
class Solution {
public:
    static bool camp(vector<int>& a, vector<int>& b) {
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        //先进行排序，按照开始节点进行排序
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> result; //返回数组
        //初始化左右边界
        int left = intervals[0][0];
        int right = intervals[0][1];
        for(int i = 1; i < intervals.size(); i++) {
            if(intervals[i][0] <= right) {
                right = max(right, intervals[i][1]);
            }
            else {
                result.push_back({left, right});
                right = intervals[i][1];
                left = intervals[i][0];
            }
        }
        //把最后一个点加入
        result.push_back({left, right});
        return result;
    }
};

本题还可以不设置单独的left，right来作为左边边界，而是使用back()来作为右边界进行更新。同时由于我们提前进行了排序，左边界又能够保证是按从小到大顺序进入的。

代码：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        //使用lambda表达式
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
        vector<vector<int>> result; //返回数组
        //使用back()来确定
        result.push_back(intervals[0]); //初始化区间

        for(int i = 1; i < intervals.size(); i++) {
            if(intervals[i][0] <= result.back()[1]) {
                result.back()[1] = max(result.back()[1], intervals[i][1]);
            }
            else {
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};

738.单调递增的数字

文档讲解：代码随想录单调递增的数字

视频讲解：手撕单调递增的数字

题目：

学习：本题重点在于需要比较每个位上的大小，来判断是否是单调递增的。贪心的方法就在于如果数不是单调递增的该如何处理。假设出现 num[i - 1] > num[i] 的情况，也就是前一位比后一位大的情况。由于需要单调递增，且不允许增大数，因此我们的贪心逻辑是，一旦出现num[i - 1] > num[i]的情况，我们就将前一位num[i - 1]--，同时将num[i]及以后的位变为9，这样就既能保证单调递增，数又是最大的。

本题我们需要从后往前遍历，我们需要利用后面比较的结果。以332为例子，如果从前往后遍历，将得到329，显然答案不对。如果从后往前遍历则是299，显然最终答案应该是这个。

写代码的时候可以注意两个关键点：

可以利用to_string()函数将数字变换为字符串，方便进行遍历处理。最后可以通过stoi()函数将字符串重新转变为int型变量。
可以设置一个flag位，确定后续要变9的位置，显然，我们只要找到最后一个需要减1的位置，后面的位就是需要置为9的。

代码：

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        //从后往前遍历，遇到前面的数大的情况，进行“前减一，后置9”的操作
        string str = to_string(n); //为了方便遍历，将int型变量转换为字符串（★）
        int flag = str.size(); //记录需要后置为9的位置
        //找到最后一个不单调的位置
        for(int i = str.size() - 1; i > 0; i--) {
            if(str[i] < str[i - 1]) {
                flag = i; //记录需要变9的位置
                str[i - 1]--; //进行减1
            } 
        }
        for(int i = flag; i < str.size(); i++) {
            str[i] = '9'; //进行变9
        }
        return stoi(str);
    }
};

968.监控二叉树

文档讲解：代码随想录监控二叉树

视频讲解：手撕监控二叉树

题目：

学习：本题的关键在于，思考如何放置摄像头才能使得摄像头的数量最小。从例子中我们可以发现，摄像头均没有放在叶子节点上。我们知道摄像头能够覆盖上中下三层，如果摄像头放在叶子节点上就必然会使得有一层是浪费的。虽然头节点放摄像头也会使得浪费一层，但是相较于头节点，叶子节点显然更多，因此叶子节点不放摄像头数量节省下来的是指数阶的。

本题的贪心就在于，局部最优：让叶子节点的父节点安装摄像头，摄像头数量最少；整体最优：全部摄像头数量所用最少。

理解了上述的贪心逻辑，我们还需要解决如下两个问题：1.二叉树的遍历；2.如何隔两个节点放一个摄像头。

1.二叉树的遍历顺序，显然我们要保证叶子节点的父节点有摄像头，且要尽可能的少放摄像头，我们需要从底往上，判断当前位置是否被覆盖，是否放置摄像头。因此需要采用后序遍历的方式。

2.如何隔两个节点放一个摄像头，对于一个节点来说，可能存在3种状态：没有被覆盖，该处有摄像头，该处没有摄像头但是被覆盖。而对于一个节点是否要安装一个摄像头，我们就需要判断左右孩子处于什么状态，如果左右孩子有一个处于没有被覆盖的状态，我们就需要在当前节点安装一个摄像头，并告诉其父节点自身有摄像头。

基于以上需求，我们可以设置3个数字来表示，当前节点的状态：

0：该节点无覆盖
1：本节点有摄像头
2：本节点有覆盖。

然后通过递推关系，来判断当前节点应该处于什么状态。如果处于1状态，我们就需要记录一个摄像头。

接下来我们就需要进行遍历过程中，递归三部曲的设置了：

1.确定返回值和参数列表：由于我们需要使用三个数字来表示当前节点的状态，因此我们返回值需设置为int型，参数列表传入root。

2.确定终止条件：由于我们需要左右孩子的情况，来判断当前节点处于的状态，因此我们需要遍历到最后的空节点（解决只有左右一个孩子的情况），而对于空节点应该处于什么状态，我们需要进行确定。为了让叶子节点不放摄像头，而叶子节点的父节点放摄像头，则叶子节点应该处于无覆盖的情况，且不能放置摄像头，因此空节点应该处于的是有覆盖的情况，这样才能推出叶子节点是无覆盖的。

3.单层递归逻辑：采用的是后序遍历，而后我们需要处理的“中”逻辑有四种情况：

左右节点都有覆盖：则此时中间节点就应该是无覆盖的情况
左右节点至少有一个无覆盖的情况：则中间节点应该安装一个摄像头。
左右节点至少有一个有摄像头：则中间节点处于有覆盖的情况。
头结点没有覆盖：头节点我们需要单独进行处理，因为头节点可能处于没有覆盖的情况。

基于以上，我们可以写出代码：

//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
    int result = 0; //定义全局变量，记录摄像头的个数
    //遍历树，1.确定返回值和参数列表
    //我们使用0，1，2来表示当前节点的三种状态：无覆盖(0)、有摄像头(1)、有覆盖(2);
    int traversal(TreeNode* root) {
        //确定终止条件
        if(root == nullptr) {
            return 2; //为了让叶子节点的父节点安装摄像头，空节点应设置为有覆盖，这样遍历到叶子节点默认左右孩子为有覆盖自身为无覆盖。
        }
        //采用后续遍历的方式，进行单层递归逻辑
        int left = traversal(root->left); //左
        int right = traversal(root->right); //右
        //中：分为三种情况
        //1.左右孩子均为有覆盖
        if(left == 2 && right == 2) {
            return 0; //则当前节点返回无覆盖
        }
        //2.左右孩子有一个是无覆盖(包含了5种情况)
        // left == 0 && right == 0 左右节点无覆盖
        // left == 1 && right == 0 左节点有摄像头，右节点无覆盖
        // left == 0 && right == 1 左节点有无覆盖，右节点摄像头
        // left == 0 && right == 2 左节点无覆盖，右节点覆盖
        // left == 2 && right == 0 左节点覆盖，右节点无覆盖
        if(left == 0 || right == 0) {
            result++; //则该节点需要有一个摄像头
            return 1;
        }

        //3.在上一个情况筛选的基础上，左右孩子有一个是有摄像头的
        if(left == 1 || right == 1) {
            return 2; //返回有覆盖
        }
        return -1; //在没有写else的情况下，需要加一个return，但实际上该return不会运行到
    }
    int minCameraCover(TreeNode* root) {
        //头节点单独处理判断
        if(traversal(root) == 0) { //如果头节点没有被覆盖
            result++;
        }
        return result;
    }
};