【算法训练营day36】LeetCode435. 无重叠区间 LeetCode763. 划分字母区间 LeetCode56. 合并区间

LeetCode435. 无重叠区间

题目链接：435. 无重叠区间

独上高楼，望尽天涯路

好像有点开窍了！我的思路是，升序排序（左对齐），然后按顺序遍历，遇到重叠时，拿走尾巴更长的区间，从而保证局部最优。

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

慕然回首，灯火阑珊处

贪心的思路是一样的，甚至感觉我的实现比题解更巧妙一点！！

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;
    }
};

LeetCode763. 划分字母区间

题目链接：763. 划分字母区间

独上高楼，望尽天涯

遍历s的过程中讨论所有情况，勉强ac。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> result;
        bool used[26] = {0};
        int start_index = 0;
        int end_index = 0;
        for (int i = 0; i < s.size(); i++) {
            if (used[s[i] - 'a']) {
                continue;
            }
            used[s[i] - 'a'] = true;
            int j;
            for (j = s.size() - 1; j >= i; j--) {
                if (s[j] == s[i]) {
                        break;
                    }
                }
            if (i <= end_index && j > end_index) {
                end_index = j;
            }
            else if (i > end_index && j > end_index) {
                result.push_back(end_index - start_index + 1);
                start_index = i;
                end_index = j;
            }
        }
        result.push_back(end_index - start_index + 1);
        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;
        }
        vector<int> result;
        int begin = 0;
        int end = 0;
        for (int i = 0; i < s.size(); i++) {
            end = max(end, hash[s[i] - 'a']);
            if (end == i) {
                result.push_back(end - begin + 1);
                begin = i + 1;
            }
        }
        return result;
    }
};

LeetCode56. 合并区间

题目链接：56. 合并区间

独上高楼，望尽天涯

排序后，遍历intervals的过程中讨论所有情况。

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>> result;
        int left = intervals[0][0];
        int right = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] <= right && intervals[i][1] > right) {
                right = intervals[i][1];
            }
            else if (intervals[i][0] > right) {
                result.push_back({left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        result.push_back({left, right});
        return result;
    }
};

慕然回首，灯火阑珊

思路本质上是一样的，但是代码还有很多可以优化的地方，学习了！

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;
    }
};