代码随想录算法训练营第三十六天 | 35. 无重叠区间、763. 划分字母区间、56. 合并区间

35. 无重叠区间

题目

解法

1. 更新区间，只保留最小区间，局部最优，推到最优

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b) {
        return a[0] < b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        int result = 0;
        for (int i = 1; i < intervals.size(); i++) {
            if(intervals[i][0] < intervals[i-1][1]) {
                result++;
                intervals[i][1] = min(intervals[i][1], intervals[i-1][1]); // 更新区间，只保留最小区间，局部最优，推到最优
            }
        }
        return result;
    }
};

763. 划分字母区间

题目

解法

1. 先记录后分割

class Solution {
public:
    vector<int> partitionLabels(string s) {
        // 标记每个字母最后出现的位置
        int Hash[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            Hash[s[i] - 'a'] = i;
        }
        // 进行分割
        int left = 0;
        int right = 0;
        vector<int> result;
        for (int i = 0; i < s.size(); i++) {
            right = max(right, Hash[s[i] - 'a']);
            if(i == right) {
                result.push_back(right - left + 1);
                left = i + 1;
            }
        }
        return result;
    }
};

56. 合并区间

题目

解法

1. 按照第一题思路自己写的

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b){
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        if (intervals.size() == 1) return intervals;
        vector<vector<int>> result;
        vector<int> cur = intervals[0]; // 记录值
        for (int i = 1; i < intervals.size(); i++) {
            if(intervals[i][0] > intervals[i-1][1]) {
                cur[1] = intervals[i-1][1];
                result.push_back(cur);
                cur = intervals[i];
            }else {
                intervals[i][1] = max(intervals[i][1], intervals[i-1][1]);
            }
        }
        cur[1] = intervals[intervals.size()-1][1];
        result.push_back(cur);
        return result;
    }
};

2.题解:修改重叠区间最大值

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        if (intervals.size() == 0) return result; // 区间集合为空直接返回
        // 排序的参数使用了lambda表达式
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});

        // 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并
        result.push_back(intervals[0]); 

        for (int i = 1; i < intervals.size(); i++) {
            if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间
                // 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为我们按照左边界排序的
                result.back()[1] = max(result.back()[1], intervals[i][1]); 
            } else {
                result.push_back(intervals[i]); // 区间不重叠 
            }
        }
        return result;
    }
};

感悟

【多学习，才会增加应对不确定未来的信心】算法题，没接触某类题之前一点思路也没有，接触后，面对相似问题，有了思路，并想想，有机会正确解决；