最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

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

来源：博客园


(资料图)

LeetCode435. 无重叠区间

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

独上高楼，望尽天涯路

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

class Solution {public:    static bool cmp(vector& a, vector& b) {        return a[0] < b[0];    }    int eraseOverlapIntervals(vector>& 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& a, const vector& b) {        return a[1] < b[1];    }    int eraseOverlapIntervals(vector>& 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 partitionLabels(string s) {        vector 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 partitionLabels(string s) {        int hash[26] = {0};        for (int i = 0; i < s.size(); i++) {            hash[s[i] - "a"] = i;        }        vector 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& a, const vector& b) {        return a[0] < b[0];    }    vector> merge(vector>& intervals) {        sort(intervals.begin(), intervals.end(), cmp);        vector> 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> merge(vector>& intervals) {        vector> result;        if (intervals.size() == 0) return result;        // 排序的参数使用了lambda表达式        sort(intervals.begin(), intervals.end(), [](const vector& a, const vector& 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;    }};

关键词： 独上高楼 灯火阑珊 灯火阑珊处