【代码随想录】刷题笔记Day38

2023-12-26 12:30:57

前言

  • 一觉醒来都这个点了,冬天的被窝真的太舒服了,抓紧刷题刷题

452. 用最少数量的箭引爆气球 - 力扣(LeetCode)

  • 按照左边界排序,不重叠result++,重叠就更新最小右边界(难点)
  • class Solution {
    private:
        static bool cmp(const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        }
    public:
        int findMinArrowShots(vector<vector<int>>& points) {
            if (points.size() == 0) return 0;
            sort(points.begin(), points.end(), cmp);
    
            int result = 1; // points 不为空至少需要一支箭
            for (int i = 1; i < points.size(); i++) {
                if (points[i][0] > points[i - 1][1]) {  // 气球i和气球i-1不挨着,注意这里不是>=
                    result++; // 需要一支箭
                }
                else {  // 气球i和气球i-1挨着
                    points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
                }
            }
            return result;
        }
    };

435. 无重叠区间 - 力扣(LeetCode)?

  • 和上一题很相似,用更新最小右边界来替代删除的操作
  • 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) {
            int sum = 0;
            sort(intervals.begin(), intervals.end(), cmp);
            for(int i = 1; i < intervals.size(); i++){
                if(intervals[i][0] < intervals[i - 1][1]){  // 如果重叠
                    sum++;  // 要删除,用更新最小右边界来替代删除(妙啊)
                    intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);
                }
            }
            return sum;
        }
    };

?763. 划分字母区间 - 力扣(LeetCode)

  • 先用哈希遍历一遍得到每个元素的最远位置,再遍历达到最远就得到长度
  • class Solution {
    public:
        vector<int> partitionLabels(string S) {
            int hash[27] = {0}; // i为字符,hash[i]为字符出现的最后位置
            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;
        }
    };

?后言

  • 极限12点刷完3道,今天的代码都不难主要是思路难想,多练多练

文章来源:https://blog.csdn.net/qq_56077562/article/details/135216048
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。