代码随想录算法训练营第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;
    }
};