【力扣刷题 | 第二十一天】

亦凉 2024-03-17 22:41 16阅读 0赞

![6146e8178ef2485c87620c8fea43c1b4.jpeg][]

**目录**

前言：

435. 无重叠区间 - 力扣（LeetCode）

763. 划分字母区间 - 力扣（LeetCode）

总结：

--------------------

## 前言： ##

今天依旧爆刷贪心算法类型的题目。

## [435. 无重叠区间 - 力扣（LeetCode）][435. _ - _LeetCode] ##

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

![12b4709362c345f28afbd328fb8d68c7.png][]

其实本题与我们之前做过的弓箭射爆气球重叠问题的思路一样，只不过在处理数据上略有不同，当我们确定好区域的时候，至少要移除多少个区间，实际上就是要求最少的重叠区间个数。

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

## [763. 划分字母区间 - 力扣（LeetCode）][763. _ - _LeetCode] ##

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

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

![794660fc011645f3b94256e19e258d10.png][]

这道题的思路确实有点复杂：

遍历字符串，得到每一个字符第一次和最后一次出现的位置，构成一个区间，如果区间相交，就合并成为一个大区间，如果不相交，就求区间长度，加入到结果中。

class Solution {
    public:
        vector<int> partitionLabels(string S) {
           std::unordered_map<char, int> lastPosMap;
            for (int i = 0; i < S.size(); i++) { 
                lastPosMap[S[i]] = i;
            }
            std::vector<int> result;
            int start = 0;
            int end = 0;
            for (int i = 0; i < S.size(); i++) {
                end = std::max(end, lastPosMap[S[i]]);
                if (i == end) {
                    result.push_back(end - start + 1);
                    start = i + 1;
                }
            }
            return result;
        }
    };

## 总结： ##

打好基础。

如果我的内容对你有帮助，请**点赞，评论，收藏**。创作不易，大家的支持就是我坚持下去的动力！

![69e9169c980f43e0aad31ff9ada88a9c.png][]

[6146e8178ef2485c87620c8fea43c1b4.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7b1db43e9915445391c770af04583307.png
[435. _ - _LeetCode]: https://leetcode.cn/problems/non-overlapping-intervals/
[12b4709362c345f28afbd328fb8d68c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/a6cf5e2b85f242f0b5a373065c2e489c.png
[763. _ - _LeetCode]: https://leetcode.cn/problems/partition-labels/
[794660fc011645f3b94256e19e258d10.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/c54d8bea04434b6697ae48a1bf01d401.png
[69e9169c980f43e0aad31ff9ada88a9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/cac8d2e7793d4c4294bc2be1d6847f82.png