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

前言

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

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道，今天的代码都不难主要是思路难想，多练多练