「代码随想录算法训练营」第二十七天 | 贪心算法 part5

56. 合并区间

题目链接:https://leetcode.cn/problems/merge-intervals/
题目难度:中等
文章讲解:https://programmercarl.com/0056.合并区间.html
视频讲解:https://www.bilibili.com/video/BV1wx4y157nD
题目状态:有思路,嘻嘻🤣

思路:

首先,按照每个区间开头的前后顺序进行排列,然后定义一个vector<int>类型的变量来保存我们合并的区间,循环遍历每个区间,判断当前合并的区间结尾是否大于等于下一个区间的开头。若大于,表示可以将该区间合并起来,否则,表明下面的区间不会和已经合并的区间有重叠了,将其存入返回变量,并改变其为下一个区间,继续遍历,直到遍历完。

代码:

点击查看代码
class Solution {
public:
    static bool cmp(const vector<int> &a, const vector<int> &b) {
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        vector<vector<int>> res;
        vector<int> temp = intervals[0];
        for(int i = 1; i < intervals.size(); ++i) {
            if(temp[1] >= intervals[i][0]) {
                temp[1] = max(temp[1], intervals[i][1]);
            } else {
                res.push_back(temp);
                temp = intervals[i];
            }
        }
        res.push_back(temp);
        return res;
    }
};

738. 单调递增的数字

题目链接:https://leetcode.cn/problems/monotone-increasing-digits/
题目难度:中等
文章讲解:https://programmercarl.com/0738.单调递增的数字.html
视频讲解:https://www.bilibili.com/video/BV1Kv4y1x7tP
题目状态:没有思路,不嘻嘻😭

思路:

从后往前遍历(这是关键),判断前一位数是否大于后一位数:

  • 若大于,将前一位数减1,这表明前一位数已经大于后面的数了,只能将前面的数减1,之后在将后面的数置为9
  • 若不大于,则向前继续遍历。

注意要记录最后一个减1的位数的下一个位数,之后要统一将其后面的数置为9.

代码:

点击查看代码
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strNum = to_string(n);
        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);
    }
};

968. 监控二叉树

题目链接:hhttps://leetcode.cn/problems/binary-tree-cameras/
题目难度:困难
文章讲解:https://programmercarl.com/0968.监控二叉树.html
视频讲解:https://www.bilibili.com/video/BV1SA411U75i
题目状态:看完题目就知道了,要看题解了😭

思路:

首先,明确遍历顺序,要用后序遍历来实现从下往上遍历,因为要避免叶子节点安装监控(这种情况下会产生最大的浪费)。

之后,将节点的状态分为以下几种:

  1. 本节点没有被摄像头覆盖,用0表示;
  2. 本节点上安装摄像头,用1表示;
  3. 本节点被摄像头覆盖,用2表示。

注意:递归结果是判断该节点是否为nullptr来结束的,通常节点为nullptr时说明我们遍历到了叶子节点的下面,那我们要给空节点设置一个状态,为了符合下面判断的逻辑,我们要将空节点设置为状态2(尽管并没有被覆盖),因为若我们将空节点设置为没有被覆盖的状态,我们就需要将叶子节点设置为状态1,此时就出现了最大浪费。

下面我们进行单层的逻辑:

  1. 本节点的左右孩子都有被覆盖,即left == 2 && right == 2
    此时该节点没有被覆盖,因此该节点的状态为0
  2. 本节点的左右孩子中至少有一个是没有被覆盖的,即left == 0 || right == 0
    此时该节点需要对下面的孩子进行覆盖,因此需要将摄像头的个数加一,然后返回状态1
  3. 本节点的左右孩子中至少一个安装了摄像头,即left == 1 || right == 1
    此时该节点处于被覆盖状态,返回状态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:
    int res;
    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) {
            res++;
            return 1;
        }
        if(left == 1 || right == 1) {
            return 2;
        }
        return -1;
    }
    int minCameraCover(TreeNode* root) {
        res = 0;
        if(traversal(root) == 0) {
            res++;
        }
        return res;
    }
};

热门相关:欧神   林家有女异世归   吹神   邪王独爱:娘子不准逃跑   大首长,小媳妇