代码随想录算法训练营：30/60

非科班学习算法day30 | LeetCode452:用最少数量的箭引爆气球 ，Leetcode435:无重叠区间 ，Leetcode763:划分字母区间 

---

介绍

包含LC的两道题目，还有相应概念的补充。

相关图解和更多版本：

代码随想录 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF

---

二、LeetCode题目

1.LeetCode452:用最少数量的箭引爆气球 

题目链接：452. 用最少数量的箭引爆气球 - 力扣（LeetCode）

题目解析

       越来越理解贪心的想法了，实际上还是找到“个例”，然后推广到全部的情况，就是数学归纳法，只不过我们没有严格证明，所以我们的解法在跑案例的时候可能会卡住

        这道题最主要的思路就是把射箭问题抽象成处理区间重叠问题，画图可以看出来，在对数组排序的情况下，重叠的数组都可以用一下打中，当没有重叠的时候就要再找一只箭。

        这里面首先我们需要直到什么叫没有重叠，那就是后面区间的左端点小于前一个区间的右端点，那么这两个区间必有交集。

        同时排序是非常常见的处理，如果数据无从处理应该想到能不能先有序化。

 c++代码如下：

class Solution {
public:
    // 对数组内部升序排列-按照左区间
    static bool cmp(vector<int>& a, vector<int>& b) 
    { 
        return a[0] < b[0]; 
    }
    int arr = 1;

    int findMinArrowShots(vector<vector<int>>& points) {
        // 异常处理
        if (!points.size())
            return 0;
        // 排序
        sort(points.begin(), points.end(), cmp);
        for (int i = 1; i < points.size(); i++) {
            if (points[i][0] > points[i - 1][1]) {
                // 下一只箭（重叠区间）
                arr++;
            }
            // 重叠区间处理
            else {
                points[i][1] = min(points[i - 1][1], points[i][1]);
            }
        }
        return arr;
    }
};

这里再给出一个对原区间除了排序就没有其他修改操作的写法：

class Solution {
public:
    // 对数组内部升序排列-按照左区间
    static bool cmp(vector<int>& a, vector<int>& b) 
    { 
        return a[0] < b[0]; 
    }
    int arr = 1;

    int findMinArrowShots(vector<vector<int>>& points) {
        // 异常处理
        if (!points.size())
            return 0;
        // 排序
        sort(points.begin(), points.end(), cmp);
        //新建一个cur区间
        vector<int> cur = points[0];

        for (int i = 1; i < points.size(); i++) {
            if (points[i][0] > cur[1]) {
                // 下一只箭（重叠区间）
                arr++;
                cur = points[i];
            }
            // 重叠区间处理
            else 
            {
                cur[1] = min(points[i][1], cur[1]);
            }
        }
        return arr;
    }
};

注意点：这个写法是新建了一个cur区间作为判断重叠区间的依据。在维护的过程中，如果没有公共交集了，那么要将cur的左区间重置为当前元素的左区间，其他情况则关注右区间就可以。

 2.Leetcode435:无重叠区间 

题目链接：435. 无重叠区间 - 力扣（LeetCode）

题目解析

       和之前的处理方式基本相同，需要注意的就是这里等号的处理，是不属于重叠区间的。

 C++代码如下： 

class Solution {
public:
    //依旧升序排列
    static bool cmp(vector<int>& a, vector<int>& b)
    {
        return a[0]<b[0];
    }
    int res = 0;
    int eraseOverlapIntervals(vector<vector<int>>& intervals) 
    {
        if(!intervals.size()) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        for(int i = 1; i<intervals.size();i++)
        {
            if(intervals[i][0]<intervals[i - 1][1])
            {
                res++;
                intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);
            }
        }
        return res;
    }
};

3.Leetcode763:划分字母区间

题目链接：763. 划分字母区间 - 力扣（LeetCode）

题目解析

       本质上是区间的合并，思路有点巧妙（邪门），首先遍历一遍，用哈希表记录当前元素在字符串中出现的最大位置。

        如果我们想切分字符串，我们要保证，该字符串内所有元素都出现在被截取之后的字符串中。所以我们继续遍历，不断更新我们需要覆盖的右区间端点。

        直到！找到下标和右区间端点一样的位置，这里需要理解就相当于找到了最短的一次切分距离，可以进行记录。

C++代码如下：

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> res;
        int start = 0;
        int end = 0;

        for(int i = 0; i<s.size(); ++i)
        {
            //合并区间
            end = max(end, hash[s[i] - 'a']);
            if(end == i)
            {
                res.push_back(end - start +1);
                start = i+1;
            }
        }
        return res;
    }
};

注意点1：说贪也贪，说不贪就纯模拟。需要学会的除了思路就是怎么将字符的相对位置表示。

 

总结

打卡第30天，坚持！！！