贪心算法总结（4）

一、跳跃游戏I

55. 跳跃游戏 - 力扣（LeetCode）

class Solution {
public:
    bool canJump(vector<int>& nums) {
          //贪心+双指针   用left和right指向两个区间 然后maxpos表示下一层的最右端点
        int left=0,right=0,maxpos=0,n=nums.size();
        while(left<=right) //有可能会跳不到n-1的位置 比如说出现了很多个0
        {
            if(maxpos>=n-1) return true;
            for(int i=left;i<=right;++i) maxpos=max(maxpos,nums[i]+i);
            //找到之后更新区间
            left=right+1;
            right=maxpos;
        }
        return false;
    }
};

二、跳跃游戏II

45. 跳跃游戏 II - 力扣（LeetCode）

 解法1 ：动态规划

class Solution {
public:
    int jump(vector<int>& nums) {
   //动态规划的思想 dp[i]表示以i位置为结尾时的最小步数
       int n=nums.size();
       vector<int> dp(n,INT_MAX);
       dp[0]=0;
       for(int i=1;i<n;++i)
         for(int j=0;j<i;++j)
          if(nums[j]+j>=i) dp[i]=min(dp[i],dp[j]+1);
        return dp[n-1];
    }
};

解法2：贪心 +双指针

class Solution {
public:
    int jump(vector<int>& nums) {
        //贪心+双指针   用left和right指向两个区间 然后maxpos表示下一层的最右端点
        int left=0,right=0,maxpos=0,ret=0,n=nums.size();
        while(left<=right) //有可能会跳不到n-1的位置 比如说出现了很多个0
        {
            if(maxpos>=n-1) return ret;
            for(int i=left;i<=right;++i) maxpos=max(maxpos,nums[i]+i);
            //找到之后更新区间
            left=right+1;
            right=maxpos;
            ++ret;
        }
        return -1;
    }
};

三、加油站

134. 加油站 - 力扣（LeetCode）

四、距离相等的条形码

1054. 距离相等的条形码 - 力扣（LeetCode）

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& nums) {
      //贪心  隔一个放一个 要顺便统计最多的那个
      int n=nums.size();
      unordered_map<int,int> hash;
      int maxval=0,maxcount=0;
      for(auto&e:nums)
        if(maxcount<++hash[e])
        {
            maxcount=hash[e];
            maxval=e;
        }
      //开始先放最大的数
      vector<int> ret(n);
      int index=0;
      for(int i=0;i<maxcount;++i)
      {
         ret[index]=maxval;
         index+=2;
      }
      hash.erase(maxval);
      //开始放后面的数字
      for(auto&[x,y]:hash)
         for(int i=0;i<y;++i)
         {
            if(index>=n) index=1;
            ret[index]=x;
            index+=2;
         }
      return ret;
    }
};

五、合并区间

56. 合并区间 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& nums) {
       //区间问题  按照左端点排序
       sort(nums.begin(),nums.end());
       int n=nums.size();
       //合并区间
       //用left和right来标记两个区间
       //如果left right     a   b   如果重叠了a<=right right=max(right,b)
                                    //如果没有重叠 将left和right丢到ret中  然后更新
        int left=nums[0][0],right=nums[0][1];
        vector<vector<int>> ret;
        for(int i=1;i<n;++i)
        {
            int a=nums[i][0],b=nums[i][1];
            if(a<=right) right=max(right,b);
            else 
            {
              ret.push_back({left,right});
              left=a,right=b;
            }
        }
        ret.push_back({left,right});
        return ret;
    }
};

六、无重叠区间

435. 无重叠区间 - 力扣（LeetCode）

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& nums) {
        sort(nums.begin(),nums.end());
        int n=nums.size();
        int ret=0;
        int left=nums[0][0],right=nums[0][1];
        for(int i=1;i<n;++i)
        {
            int a=nums[i][0],b=nums[i][1];
            if(a<right) 
            {
                right=min(right,b);
                ++ret;
            } //移除右端点较大的区间  更新右区间
            else right=b;
        }
        return ret;
    }
};

七、用最少数量的箭引爆气球

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

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& nums) {
      //只要出现重叠区间，就可以用一只箭射穿
      sort(nums.begin(),nums.end());
      int n =nums.size();
      int left=nums[0][0],right=nums[0][1]; //保留的是交集
      int ret=1;
      for(int i=1;i<n;++i)
      {
        int a=nums[i][0],b=nums[i][1];
        if(a<=right)//如果有交集 
        {
          right=min(right,b);
        }
        else //说明没有交集
        {
            right=b;
            ++ret;
        }
      }
      return ret;
    }
};

八、俄罗斯套娃信封问题

354. 俄罗斯套娃信封问题 - 力扣（LeetCode）

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& e) {
       //重写排序+贪心+二分
       int n=e.size();
       sort(e.begin(),e.end(),[&e](const vector<int>&v1, const vector<int>&v2){
             return v1[0]!=v2[0]?v1[0]<v2[0]:v1[1]>v2[1];
       });
       vector<int> ret;
       ret.emplace_back(e[0][1]);
       for(int i=1;i<n;++i)
       {
          int b=e[i][1];
         //如果我比最后一个都大 我直接尾插
         if(b>ret.back()) ret.emplace_back(b);
         else //否则就二分
         {
             int left=0,right=ret.size()-1;
             while(left<right)
             {
               int mid=(left+right)>>1;
               if(ret[mid]<b) left=mid+1;
               else right=mid;
             }
             ret[left]=b;
         }
       }
       return ret.size();
    }
};

九、堆箱子

面试题 08.13. 堆箱子 - 力扣（LeetCode）

class Solution {
public:
    int pileBox(vector<vector<int>>& nums) {
       sort(nums.begin(),nums.end());
       int n=nums.size();
       //23 54 64 67
       //dp[i]表示以i位置为结尾的最长递增子序列的长度
       vector<int> dp(n);
       for(int i=0;i<n;++i) dp[i]=nums[i][2];
       for(int i=1;i<n;++i)
          //开始往前找
          for(int j=0;j<i;++j) 
          if(nums[i][0]>nums[j][0]&&nums[i][1]>nums[j][1]&&nums[i][2]>nums[j][2])
           dp[i]=max(dp[i],dp[j]+nums[i][2]);
        return *max_element(dp.begin(),dp.end()); 
    }
};