【代码随想录day30】【C++复健】452. 用最少数量的箭引爆气球；435. 无重叠区间；763. 划分字母区间

452. 用最少数量的箭引爆气球

本题一开始就有思路，也算是一遍写出来了，不过问题一个是写麻烦了，还有一个就是对于这个自定义比较方法还是不熟。

首先关于写麻烦了这件事，在自定义cmp的时候，我是这么写的：

static bool cmp(vector<int>& points1, vector<int>& points2){
        if(points1[0] == points2[0]){
            return points1[1] < points2[1];
        }
        return points1[0] < points2[0];
    }

但其实不用比较points[1]，打个比方，两个气球，一个是[1,5]，一个是[1,3]，无论先排哪个，这两个气球都肯定存在焦点，所以可以被一起打掉。所以没必要排后面的1号位的顺序。

其次就是关于cmp定义的部分，昨天本来也想说，后来忘记了，一定要写一个static的原因：

在 C++ 中，成员函数会隐式接受一个 this 指针，指向类的实例，因此它不能直接作为函数指针传递给像 std::sort 这样的算法。如果要在类内使用成员函数作为比较函数，需要将其声明为 static，这样就不再依赖对象实例，可以像普通函数一样传递给算法。静态成员函数与类的实例无关，不需要 this 指针，能直接作为函数指针使用。而类外的普通函数本身就不依赖 this 指针，因此可以直接传递给算法。总的来说，静态成员函数和类外普通函数都可以作为比较函数传递给 std::sort，而非静态成员函数则不能。

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), cmp);
        int count = 1;
        vector<int> mark = points[0];
        for(int i=0; i<points.size(); i++){
            if(mark[1] < points[i][0]){
                mark = points[i];
                count++;
            }
            else{
                if(mark[1] > points[i][1]){
                    mark[1] = points[i][1];
                }
            }
        }
        return count;
    }
    static bool cmp(vector<int>& points1, vector<int>& points2){
        if(points1[0] == points2[0]){
            return points1[1] < points2[1];
        }
        return points1[0] < points2[0];
    }
};

435. 无重叠区间

本题也是有想法能做出来，但做麻烦了。

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

这个代码时间复杂度也是0(nlogn)，但我的运行耗时2699ms。

先说这个代码写的时候遇到的问题，当我已经设定vector<int> mark = intervals[0]后，后续的for循环就得从i=1开始，不然一上来就得++，最后总是比答案多1。

再有就是比较和逻辑判断都写复杂了，我的这套代码的终极优化版应该是卡哥的这个：
 

class Solution {
public:
    static bool cmp (const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0]; // 改为左边界排序
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) return 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 0; // 注意这里从0开始，因为是记录重叠区间
        int end = intervals[0][1]; // 记录区间分割点
        for (int i = 1; i < intervals.size(); i++) {   
            if (intervals[i][0] >= end)  end = intervals[i][1]; // 无重叠的情况
            else { // 重叠情况 
                end = min(end, intervals[i][1]);
                count++;
            }
        }
        return count;
    }
};

让我们看看都多写了什么无效比较：

1 cmp里面只用判断左边界，不用管右边界。

2 只要出现了范围交叉，取它们右边界最小值即可，无需分两种情况讨论（不过我写的逻辑好像也差不多，只是用max写看着会更省空间）

3 只用一个int值记录右边界即可，不用把左边界一同记录，反正比较的时候也没用到过左边界。

763.划分字母区间

我的思路是首先使用一个哈希表统计每个字母在字符串中出现的次数。接着，我们用一个集合来追踪当前窗口中尚未满足其出现次数的字母。在遍历字符串时，当遇到某个字母时，就将它加入集合，并且每次遇到字母时，更新它在哈希表中的剩余次数。每当一个字母的剩余次数为 0，说明它已经满足出现次数条件，可以从集合中移除。当集合为空时，表示当前窗口可以作为一个划分点，此时进行一次划分操作。

这个思路看似有效，但我在实现时发现它变得比较复杂。主要是在管理集合和更新哈希表的过程中，特别是在动态插入和移除字母时，容易出错。此外，划分条件的判断也变得较为复杂，因为需要确保每次都正确更新集合和剩余次数。

看了卡哥的思路之后，确实，我们没有必要去关系它到底出现了几次，我们只要管它最后出现在哪其实就可以了。而这也这是我想复杂的地方。

但看完思路后自己写的代码还是复杂了些：

class Solution {
public:
    vector<int> partitionLabels(string s) {
        unordered_map<char, int> dict;
        for(int i=0; i<s.size(); i++){
            dict[s[i]] = i;
        }
        vector<int> count;
        int length = 0;
        int maxpo = dict[s[0]];
        for(int i=0; i < s.size(); i++){
            length++;
            if(dict[s[i]] > maxpo){
                maxpo = dict[s[i]];
            }
            else if(i == maxpo){
                if(i < s.size()-1){
                    maxpo = dict[s[i+1]];
                }
                count.push_back(length);
                length = 0;
            }
        }
        return count;
    }
};

1 没有使用数组代替哈希表

2 使用左右指针left和right，就不需要担心越界的问题，也不用再加一个length专门去统计长度了：

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 left = 0;  // 当前子串的起始位置
        int right = 0; // 当前子串的结束位置

        for (int i = 0; i < s.size(); i++) {
            right = max(right, hash[s[i] - 'a']); // 更新子串的结束位置
            if (i == right) {  // 如果当前位置是当前子串的结束位置
                result.push_back(right - left + 1);  // 计算子串长度
                left = i + 1;  // 更新起始位置，准备开始下一个子串
            }
        }
        return result;
    }
};