代码随想录Day.36 | 435. 无重叠区间、763. 划分字母区间、56. 合并区间

发布时间:2024年01月17日

435. 无重叠区间

1. LeetCode链接

435. 无重叠区间 - 力扣(LeetCode)

2. 解法

移除最小数目的区间,使得剩余区间互不重叠。

想清楚这道题和计算最小重叠区间的个数的关系,就大概明白了。

1. 如果某一堆区间存在最小交集区间,说明这堆区间最多保留一个区间,其余都要移除。

2. 假如存在另一堆区间,这堆区间有着与上一堆区间不同的最小区间,是否可以证明这两堆区间最终要移除至只剩两个区间?可以证明,因为如果有第三个剩余区间,那么这个区间要么和其中一个重叠,要么和另一个重叠;剩余的这两个区间有没有可能重叠?为啥不能剩余一个区间?假如有两堆各自有最小公共区间的区间,如果只剩余一个区间a,那么这个区间是有可能与两个最小公共区间重叠的,但是,一定可以找到另外两个区间b,c,其中,b,c和a的公共区间不同。否则如果找不到,则与前提不同,即存在两个拥有不同最小公共区间的区间堆。因为要移除最少数量,所以,只能是两堆中剩余两个。

3. 所以,使得剩余区间互不重叠的最小移除数目,是区间总数 - 最小重叠区间个数。

class Solution {
static bool cmp(vector<int>& a, vector<int>& b) {
    if (a[0] != b[0]) return a[0] < b[0];
    else return a[1] < b[1];
}
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        vector<int> region(2, 0);
        int sum = 1;
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
            } else sum++;
        }
        return intervals.size() - sum;
    }
};

763. 划分字母区间

1. LeetCode链接

763. 划分字母区间 - 力扣(LeetCode)

2. 解法

记录每个字母的第一次出现时的坐标,和最后一次出现时的坐标。然后根据起始坐标从大到小排列,如果起始坐标相等,按照末尾坐标从大到小排列后,遍历区间,依次吞并可以吞并的区间。

这里要注意,有很多没出现过的字母,一直处于[0, 0],需要排除。很麻烦。

class Solution {
static bool cmp(vector<int>& a, vector<int>& b) {
    if (a[0] != b[0]) return a[0] < b[0];
    else return a[1] < b[1];
}
public:
    vector<int> partitionLabels(string s) {
        vector<vector<int>> word(26, vector<int>(2, 0));
        vector<int> result;
        for (int i = 0; i < s.size(); i++) {
            if (word[s[i] - 'a'][0] == 0 && word[s[i] - 'a'][1] == 0) {
                word[s[i] - 'a'][0] = i;
                word[s[i] - 'a'][1] = i + 1;
            } else {
                word[s[i] - 'a'][1] = i + 1;
            }
        }
        sort(word.begin(), word.end(), cmp);
        vector<int> region = word[0];
        for (int i = 0; i < 26; i++) {
            if (word[i][0] == 0 && word[i][1] == 0) continue;
            else if (region[0] == 0 && region[1] == 0) {
                region = word[i];
                continue;
            }
            if (word[i][0] >= region[1]) {
                result.push_back(region[1] - region[0]);
                region = word[i];
            } else region[1] = max(region[1], word[i][1]);
        }
        result.push_back(region[1] - region[0]);
        return result;
    }
};

巧妙方法:

因为是合并区间的问题,所以可以这么简单。

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 = hash[s[0] - 'a'];
        vector<int> result;
        for (int i = 0; i < s.size(); i++) {
            if (right == i) {
                result.push_back(right - left + 1);
                if (i != s.size() - 1) {
                    left = i + 1;
                    right = hash[s[i + 1] - 'a'];
                }
            } else right = max(hash[s[i] - 'a'], right);
        }
        return result;
    }
};

56. 合并区间

1. LeetCode链接

56. 合并区间 - 力扣(LeetCode)

2. 解法

这就跟上一个的复杂解法类似了。

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

文章来源:https://blog.csdn.net/papilon_/article/details/135649336
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。