【C++代码】合并区间，最少用箭数，划分字符串，监控二叉树，贪心算法--代码随想录

• 在讲解[贪心算法：根据身高重建队列 中，我们提到了使用vector（C++中的动态数组）来进行insert操作是费时的。其直观上来看数组的insert操作是O(n)的，整体代码的时间复杂度是O(n^2)。

• 对于普通数组，一旦定义了大小就不能改变，例如int a[10];，这个数组a至多只能放10个元素，改不了的。对于动态数组，就是可以不用关心初始时候的大小，可以随意往里放数据，那么耗时的原因就在于动态数组的底层实现。首先vector的底层实现也是普通数组。vector的大小有两个维度一个是size一个是capicity，size就是我们平时用来遍历vector时候用的.而capicity是vector底层数组（就是普通数组）的大小，capicity可不一定就是size。当insert数据的时候，如果已经大于capicity，capicity会成倍扩容，但对外暴漏的size其实仅仅是+1。

• 就是重新申请一个二倍于原数组大小的数组，然后把数据都拷贝过去，并释放原数组内存。（对，就是这么原始粗暴的方法！）

  • 

• 那么底层其实就要申请一个大小为6的普通数组，并且把原元素拷贝过去，释放原数组内存，注意图中底层数组的内存起始地址已经变了。使用vector来做insert的操作，此时大家可会发现，虽然表面上复杂度是$O(n^2)$，但是其底层都不知道额外做了多少次全量拷贝了，所以算上vector的底层拷贝，整体时间复杂度可以认为是$O(n^2+t\times n)$级别的，t是底层拷贝的次数。

题目：用最少数量的箭引爆气球

• 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

• 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

• class Solution {
  public:
      static bool cmp(const vector<int> &a,const vector<int> &b){
          return a[0]<b[0];
      }
      int findMinArrowShots(vector<vector<int>>& points) {
          if(points.size()==0)
              return 0;
          sort(points.begin(),points.end(),cmp);
          int res=1;
          for(int i=1;i<points.size();i++){
              if(points[i][0]>points[i-1][1]){// 气球i和气球i-1不挨着，注意这里不是>=
                  res++;
              }else{
                  points[i][1]=min(points[i-1][1],points[i][1]);
              }
          }
          return res;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20

• 时间复杂度：O(nlog n)，因为有一个快排；空间复杂度：O(n)，有一个快排，最差情况(倒序)时，需要n次递归调用。因此确实需要O(n)的栈空间

• 为了让气球尽可能的重叠，需要对数组进行排序。按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。

题目：无重叠区间

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

• 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;
          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
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23

题目：划分字母区间

• 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。返回一个表示每个字符串片段的长度的列表。

• 在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。可以分为如下两步：

  • 统计每一个字符最后出现的位置
  • 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

• class Solution {
  public:
      vector<int> partitionLabels(string s) {
          int hash[27]={0};
          for(int i=0;i<s.size();i++){//统计每一个字符最后出现的位置
              hash[s[i]-'a']=i;
          }
          vector<int> res;
          int left=0,right=0;
          for(int i=0;i<s.size();i++){
              right=max(right,hash[s[i]-'a']);
              if(i==right){
                  res.push_back(right-left+1);
                  left=i+1;
              }
          }
          return res;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19

• 时间复杂度：O(n)；空间复杂度：O(1)，使用的hash数组是固定大小

题目：合并区间

• 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

• 先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同。按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1] 即intervals[i]的左边界 <= intervals[i - 1]的右边界，则一定有重叠。（本题相邻区间也算重贴，所以是<=）。

• 其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。

• class Solution {
  public:
      vector<vector<int>> merge(vector<vector<int>>& intervals) {
          vector<vector<int>> res;
          if(intervals.size()==0){
              return res;
          }
          sort(intervals.begin(),intervals.end(),[](const vector<int> &a,const vector<int> &b){return a[0]<b[0];});
          res.push_back(intervals[0]);
          for(int i=1;i<intervals.size();i++){
              if(res.back()[1]>=intervals[i][0]){//重叠区间
                  res.back()[1]=max(res.back()[1],intervals[i][1]);
              }else{
                  res.push_back(intervals[i]);
              }
          }
          return res;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19

题目：单调递增的数字

• 当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

• class Solution {
  public:
      int monotoneIncreasingDigits(int n) {
          string strnum=to_string(n);
          int len_str=strnum.size();
          for(int i=strnum.size()-1;i>0;i--){
              if(strnum[i-1]>strnum[i]){
                  len_str=i;
                  strnum[i-1]--;
              }
          }
          for(int i=len_str;i<strnum.size();i++){
              strnum[i]='9';
          }
          return stoi(strnum);
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

• 使用暴力求解，提交超时

  • class Solution {
    public:
        bool check(int num){
            int max_one=10;
            while(num){
                int t=num%10;
                if(max_one>=t){
                    max_one=t;
                }else{
                    return false;
                }
                num=num/10;
            }
            return true;
        }
        int monotoneIncreasingDigits(int n) {
            for(int i=n;i>0;i--){
                if(check(i))
                    return i;
            }
            return 0;
        }
    };
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23

题目：监控二叉树

• 给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视**其父对象、自身及其直接子对象。**计算监控树的所有节点所需的最小摄像头数量。

• 摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。所以把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。**所以我们要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！**此时，大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。可以使用后序遍历也就是左右中的顺序，这样就可以在回溯的过程中从下到上进行推导了。

• 此时需要状态转移的公式，大家不要和动态的状态转移公式混到一起，本题状态转移没有择优的过程，就是单纯的状态转移！来看看这个状态应该如何转移，先来看看每个节点可能有几种状态：该节点无覆盖；本节点有摄像头；本节点有覆盖

• 分别有三个数字来表示：0：该节点无覆盖；1：本节点有摄像头；2：本节点有覆盖

• class Solution {
  public:
      int res;
      int travesal(TreeNode* cur){
          if(cur==nullptr){
              return 2;
          }
          int left=travesal(cur->left);
          int right=travesal(cur->right);
          if(left==2&&right==2){// 左右节点都有覆盖
              return 0;
          }
          if(left==0||right==0){//没有覆盖，那么父节点需要安装摄像头来覆盖
              res++;
              return 1;
          }
          if(left==1||right==1){//子节点有摄像头了，那么算这个父节点被覆盖了
              return 2;
          }
          // 这个 return -1 逻辑不会走到这里。
          return -1;
      }
      int minCameraCover(TreeNode* root) {
          res=0;
          if(travesal(root)==0){//后序遍历
              res++;
          }
          return res;
      }
  };
    	//逻辑不会走到这里。
          return -1;
      }
      int minCameraCover(TreeNode* root) {
          res=0;
          if(travesal(root)==0){//后序遍历
              res++;
          }
          return res;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41

• 时间复杂度: O(n)，需要遍历二叉树上的每个节点；空间复杂度: O(n)