第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,显然最终答案应该是这个。

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

  1. 可以利用to_string()函数将数字变换为字符串,方便进行遍历处理。最后可以通过stoi()函数将字符串重新转变为int型变量。
  2. 可以设置一个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;
    }
};

贪心算法总结 

文档讲解:代码随想录贪心算法总结

贪心算法一句话:没有套路,多加练习,手动模拟。

贪心算法的题目可以分为: 

题目之间并没有明显的顺序关系,重点还是要多加联系。 

一个系列的结束,标志着另一个系列的开始,动态规划!继续加油

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部