前言

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

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