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

发布于 2023-01-03  211 次阅读


AI 摘要

本篇文章是代码随想录算法训练营第36天的总结,涵盖了三道算法题的解题思路及代码实现。 第一道题目是LeetCode 435. 无重叠区间,题目要求找出给定区间列表中,需要移除的最小区间数量,以保证剩下的所有区间不重叠。解题思路是按照区间右边界排序,从前向后遍历寻找非交叉区间的数量,最后总区间数量减去非交叉区间的数量就是需要去掉的重叠区间的数量。实现代码可以使用快排来进行排序。 第二道题是LeetCode 763. 划分字母区间,题目要求将字符串划分为尽可能多的区间,每个区间内的每个字母都只能出现在该区间内。解题思路是先遍历一遍数组,记录字符串中每个元素最后一次出现的位置。再次遍历数组,每次遇到元素都将此时的位置记录到unordered_map,若该元素此前已经被记录过,则遍历unordered_map,若unordered_map中所有位置都是最终位置则说明已经找到分割点,存入结果数组。实现代码可以使用unordered_map进行查找。 第三道题是LeetCode 56. 合并区间,题目要求合并重叠的区间。解题思路是先按照区间左边界进行排序,然后遍历区间列表,将当前区间与前一个区间进行比较,如果当前区间的左边界在前一个区间的右边界之前,则将它们合并。实现代码比较简单,可以直接按照解题思路实现。

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

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

思路:

  • 将数组按照右边界从小到大进行排序,然后从前往后循环一遍找非交叉区间的数量,最后总区间数量减去非交叉区间的数量就是需要去掉的重叠区间的数量
  • 因为是按照右边界从小到大排序,每次都给后面尽可能留出多的空间,所以可以找出最大非重叠区间数量

我的AC代码

//时间复杂度O(nlogn),空间复杂度O(n) 主要是快排所需的
class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int cnt = 1;
        sort(intervals.begin(), intervals.end(), cmp);
        int end = intervals[0][1];
        for(int i = 1; i < intervals.size(); ++i) {
            if(intervals[i][0] >= end) {
                cnt++;
                end = intervals[i][1];
            }
        }
        return intervals.size() - cnt;
    }
};

标准答案

//时间复杂度O(nlogn),空间复杂度O(n) 主要是快排所需的
class Solution {
public:
    // 按照区间右边界排序
    static bool cmp (const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 1; // 记录非交叉区间的个数
        int end = intervals[0][1]; // 记录区间分割点
        for (int i = 1; i < intervals.size(); i++) {
            if (end <= intervals[i][0]) {
                end = intervals[i][1];
                count++;
            }
        }
        return intervals.size() - count;
    }
};

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

思路:

  • 先遍历一遍数组,记录字符串中每个元素最后一次出现的位置。再次遍历数组,每次遇到元素都将此时的位置记录到unordered_map,若该元素此前已经被记录过,则遍历unordered_map,若unordered_map中所有位置都是最终位置则说明已经找到分割点,存入结果数组
  • 建议使用标准答案的做法,我的做法借助了unordered_map来判断是否此前出现的所有元素都已经被囊括在内(即所有元素的位置都与最后出现的位置一致)。但实际上只需要记录此前遍历的所有元素的最后位置的最大值即可,每次也只需要判断i是否与这个最大值相等,只要相等则说明找到分割点。这样做可以节省很多空间,在时间上也有较大的提升。

我的AC代码

使用unordered_map(速度较慢)

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<int> partitionLabels(string s) {
        int a[26] = {0};
        for(int i = 0; i < s.size(); ++i) {
            if(i > a[s[i] - 97]) {
                a[s[i] - 97] = i;
            }
        }
        unordered_map<char, int> us;
        vector<int> ans;
        int start = 0;
        for(int i = 0; i < s.size(); ++i) {
            us[s[i]] = i;
            if(us.find(s[i]) != us.end()) {
                int flag = 1;
                for(auto b : us) {
                    if(a[b.first - 97] != b.second) {
                        flag = 0;
                        break;
                    }
                }
                if(flag == 1) {
                    us.clear();
                    ans.push_back(i - start + 1);
                    start = i + 1;
                }
            }
        }
        return ans;
    }
};

复刻标准答案(推荐,时间复杂度和空间复杂度大大降低)

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    vector<int> partitionLabels(string s) {
        int a[26] = {0};
        for(int i = 0; i < s.size(); ++i) {
            if(i > a[s[i] - 97]) {
                a[s[i] - 97] = i;
            }
        }
        vector<int> ans;
        int start = 0;
        int end = 0;
        for(int i = 0; i < s.size(); ++i) {
            end = max(end, a[s[i] - 97]);
            if(end == i) {
                ans.push_back(end - start + 1);
                start = i + 1;
            }       
        }
        return ans;
    }
};

标准答案

//时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    vector<int> partitionLabels(string S) {
        int hash[27] = {0}; // i为字符,hash[i]为字符出现的最后位置
        for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置
            hash[S[i] - 'a'] = i;
        }
        vector<int> result;
        int left = 0;
        int right = 0;
        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. 合并区间 - 力扣(LeetCode)

思路:

  • 先对数组按照左边界从小到大排序,然后从左到右遍历数组,记录此时的开头和结尾,若遍历到的元素的开头大于此前记录的结尾,那么说明不重叠,则将前面记录的开头和结尾添加到结果数组,否则说明重叠,就需要更新开头和结尾的值,开头是此前值和当前值的最小值,结尾是此前值和当前值的最大值。最后遍历完成以后特判一下,若储存答案数组的大小为0或者此时记录的开头要比答案数组中最后一个元素的结尾要大,说明此时记录的开头结尾的数据还没来得及加入结果数组中,需要添加一次。最后返回结果数组。
  • 标准答案的这句result.back()[1] = max(result.back()[1], intervals[i][1]);太精髓了,因为按照左边界从小到大排序,所以每次加入的元素的左侧一定是最小值,那么只需要更新右边界即可,取右边界的最大值即完成一次合并

我的AC代码

//时间复杂度O(nlogn),空间复杂度O(n)
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>> ans;
        int start = intervals[0][0];
        int end = intervals[0][1];
        for(int i = 1; i < intervals.size(); ++i) {
            if(intervals[i][0] > end) {
                ans.push_back({start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
            else {
                start = min(start, intervals[i][0]);
                end = max(end, intervals[i][1]);
            }
        }
        if(ans.size() == 0 || start > ans[ans.size() - 1][1]) {
            ans.push_back({start, end});
        }
        return ans;
    }
};

标准答案

// 时间复杂度:O(nlog n) ,有一个快排
// 空间复杂度:O(n),有一个快排,最差情况(倒序)时,需要n次递归调用。因此确实需要O(n)的栈空间
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.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (result.back()[1] >= intervals[i][0]) { // 合并区间
                result.back()[1] = max(result.back()[1], intervals[i][1]);
            } else {
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};