代码随想录算法训练营 | 贪心算法 part05

56. 合并区间

56. 合并区间

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        if(a[0] == b[0]) {
            return a[1] < b[1];
        }
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        vector<vector<int>> res;
        int start = intervals[0][0];
        int end = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= start && intervals[i][0] <= end) { // 与前面的区间有重叠
                if(intervals[i][1] >= end) { // 更新重叠区间的右端点
                    end = intervals[i][1];
                }
            } else if (intervals[i][0] > end) { // 与前面的区间无重叠
                res.push_back({start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        res.push_back({start, end});
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

738. 单调递增的数字

738. 单调递增的数字
当发现当前数字大于下一个数字时，就把当前数字减1，后面的所有数字都设置成 9

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        if (n >= 0 && n <= 9) {
            return n;
        }
        string s = to_string(n);
        for (int i = s.size() - 2; i >=  0; i--) {
            if(s[i] > s[i + 1]) {
                s[i]--;
                for (int j = i + 1; j < s.size(); ++j){
                    s[j] = '9';
                }
            }
        }
        return stoi(s);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

第二个for循环存在重复赋值；如：304537，在检测到5<4时，数字改为303999；在遇到0<3时，数字改为299999，最后两位数同样被再次赋值；
设置flag来标记赋值9从哪里开始，同时将赋值循环分离出来；

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s = to_string(n);
        int flag = s.size();
        for (int i = s.size() - 2; i >=  0; i--) {
            if(s[i] > s[i + 1]) {
                s[i]--;
                flag = i + 1;
            }
        }
        for (int j = flag; j < s.size(); ++j){
            s[j] = '9';
        }
        return stoi(s);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

968. 监控二叉树

968. 监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。

局部最优：让叶子节点的父节点安摄像头，所用摄像头最少
全局最优：全部摄像头数量所用最少

class Solution {
private:
    int res;
    int traversal(TreeNode* cur) {
        if (cur == NULL) return 2;
        int left = traversal(cur->left);    // 左
        int right = traversal(cur->right);  // 右
        if (left == 2 && right == 2) return 0;
        else if (left == 0 || right == 0) {
            res++;
            return 1;
        } else return 2;
    }
public:
    int minCameraCover(TreeNode* root) {
        res= 0;
        if (traversal(root) == 0) { // root 无覆盖
            res++;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22