算法练习-day29

贪心算法

435. 无重叠区间

题意：给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

实例：

思路：本题和452. 用最少数量的箭引爆气球做法非常类似，大家可以先看看我之前的文章。本题我们只需要统计重叠的区域，代码如下

C++代码：

    static bool cmp(vector<int>& left,vector<int>& right)
    {
        return left[0]<right[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        int count=0;
        for(int i=1;i<intervals.size();i++)
        {
            if(intervals[i-1][1]>intervals[i][0])//只需要判断两区域是否重合，重合了就++，然后重置右边界
            {
                count++;
                intervals[i][1]=min(intervals[i-1][1],intervals[i][1]);
            }
        }
        return count;
    }

763. 划分字母区间

题意：给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意：划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。返回一个表示每个字符串片段的长度的列表。

实例：

思路：本题其实和之前做过的一个找范围题类似，也是从头开始不断地扩大寻找范围，直到范围寻找结束，再保存该范围。本题也是类似，利用find函数搜索字符在整个字符串中的最远距离，以此作为基础，遍历这个临时的范围，在过程中，不断地寻找最大范围，直到跳出最大范围或者跳出字符串的范围，就说明结束便利了，可以存储字符串长度了

C++代码：

    int max(int a,int b)
    {
        if(a>b)
        {
            return a;
        }
        return b;
    }
    vector<int> partitionLabels(string s) {
        vector<int> arr;
        int i = 0;
        while (i < s.size())
        {
            int n = i;
            int maxSignal = s.rfind(s[i]);//我们先选出一个暂时的范围作为第一个字符串的长度
            while (i<s.size() && i<maxSignal)//在遍历过程中不断修改字符串的范围，直到其达到最大范围
            {
                i++;
                maxSignal = max(maxSignal, s.rfind(s[i]));
            }
            arr.push_back(maxSignal - n + 1);//跳出，说明找到了字符串的最大范围
            i++;
        }
        return arr;
    }

56. 合并区间

题意：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

实例：

思路：本题主要和之前题目类似，都需要先排序，将左边小的排到前面，便于邻界重叠。我们先构建一个二维数组arr，用于存储重叠好的边界；先放入一个边界，然后for循环，如果两边界重叠，就需要取并集；如果不重叠，则需要先保存，然后循环上去再次判断是否需要改变边界。

C++代码：

    static bool cmp(vector<int>& left,vector<int>& right)
    {
        if(left[0]==right[0])
        {
            return left[1]<right[1];
        }
        return left[0]<right[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        vector<vector<int>> arr;
        arr.push_back(intervals[0]);//我们直接插入第一个区域，然后在第一个区域基础上修改边界
        int n = 0;//为了修改边界而定义的
        for (int i = 1; i<intervals.size(); i++)
        {
            if (arr[n ][1] >= intervals[i][0])//当有重合边界时，取它们的并集
            {
                arr[n][0] = min(arr[n][0], intervals[i][0]);
                arr[n][1] = max(arr[n][1], intervals[i][1]);
            }
            else//没有时，则直接保存
            {
                arr.push_back(intervals[i]);
                n++;
            }
        }
        return arr;
    }