贪心算法力扣刷题练习（含思路与题解）

贪心算法

保证每次操作都是局部最优，使得最终结果也是全局最优的。
需要找到贪心的策略，使得每次的最优能保证全局最优。

通常需要排序。根据排序需求，自定义比较函数。

sort(a.begin(),a.end(),[](vector<int> a,vector<int> b){a[1]>b[1];});

技巧：有两种比较时，通常先满足一种，再考虑另一种，如果这两种可以分开，则可以局部最优到全局最优。

• 题目455，饼干分配问题

有一群有不同饥饿度的孩子和一堆不同大小的饼干，每个孩子只能吃最多一个饼干，且只有饼干的大小大于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。

思路：小孩饼干都升序排序，每个小孩吃满足他的最小的饼干

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        //都排序后，饼干按从小到大给从小到大的孩子分配
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int i = 0;//孩子胃口值从小到大排序后 的下标值
        int cnt = 0;
        for(int j=0; j<s.size(); j++){
            if(s[j]>=g[i]){
                 cnt++; //满足情况分配给孩子，
                 i++;  //继续看下一个孩子  
                 if(i>=g.size())  //孩子分配完
                    return cnt;
            } 
        }
        return cnt;
    }
};

• 题目135, 糖果分配问题

一群不同评分的孩子站成一排，如果一个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所有孩子至少要有一个糖果。求解最少需要多少个糖果。

思路：小孩都先发一个糖，从左到右遍历，若右边比左边孩子评分高则比左边多分一个，再由右往左遍历，如果左边比右边高，左边加1。

class Solution {
public:
    int candy(vector<int>& ratings) {
        int len = ratings.size(); 
        int num=0;
        vector<int> candy(len,1); //每个人先确保有一颗 
        for(int i=0; i<len-1; i++){
            if(ratings[i+1]>ratings[i])
                candy[i+1] = candy[i] + 1;    //确保右边孩子比左边孩子评分高的 多拿一颗
        }
        for(int i=len-1; i>0; i--){
            if(ratings[i-1]>ratings[i]&&candy[i-1]<=candy[i])
                candy[i-1] = candy[i] + 1;    //确保左边孩子比右边孩子评分高的 多拿一颗
            num += candy[i];      
        }
        num += candy[0];
        return num;
    }
};

• 题目435. 区间问题

给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。

思路：在选择要保留区间时，区间的结尾十分重要：选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因此，我们采取的贪心策略为，优先保留结尾小且不相交的区
间。

具体实现方法为，先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间。这里使用 C++ 的Lambda，结合std::sort()函数进行自定义排序。

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),[](vector<int>a,vector<int>b){return a[1]<b[1];});
        int num = 0;
        int endCur = intervals[0][1];  //第一个区间尾部
        for(int i = 1;i < intervals.size(); i++){
            if(intervals[i][0]>=endCur){ //遇到头大于当前区间尾部的，更新尾部
                endCur = intervals[i][1];
            }
            else{ //有重叠，去除个数增加
                num++;
            }
        }
        return num;
    }
};

• 题目605. 种花问题

给你一个由若干 0 和 1 组成的数组flowerbed表示花坛，其中0表示没种植花，1 表示种了。另有一个数n ，能否在不打破种植规则（花不能种在相邻地块上）的情况下种入n朵花？能则返回 true ，不能则返回 false。

思路：每三个一起的0可以种一个花，注意首位只需要两个零，所以可以现在首尾添加0.

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int count0 = 0,m = 0,inv = 3;
        flowerbed.insert(flowerbed.begin(),1,0);//在花坛的首尾加入空地   解决首尾只需要两个计数问题
        flowerbed.insert(flowerbed.end(),1,0);
        for(int i=0;i<flowerbed.size();i++){
         //   if((i==0&&flowerbed[i]==0 )||(i==flowerbed.size()-1&&flowerbed[i]==0)) inv = 2; //当只有一个0时，出错
            if(flowerbed[i]==0){
                count0++;
                if(count0==inv){
                    count0 =0;
                    m++;
                    if(inv==3)
                        inv=2;
                }
            }else{
                count0 = 0;
                inv = 3;
            }
        }
        return m>=n;
    }
};

• 题目452. 最少箭引爆气球（区间问题）

已知气球x轴左右点坐标，一支弓箭可以沿着x 轴从不同点完全垂直地射出。若落点再气球左右点坐标内，则该气球会被引爆。找到使得所有气球全部被引爆，所需的弓箭的最小数量。就是求能重合的区间

思路：

1. 按气球左坐标升序排序（头部排序），则起始点一直在变大，每次比较当前起始点与当前所有气球右坐标最远的点，如果起始点大于右坐标最远点，则第一个箭能射中最多的区间到了，更新头尾气球区间。
2. 按气球右坐标升序排序（尾部排序），右坐标一直在变大，每次记录当前所有气球头部最远的点，如果头大于尾部，则第一个箭能射中最多的区间到了，更新头尾为新的气球区间。

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        //头部排序  也可以尾部排序
        sort(points.begin(),points.end(),[](vector<int> a,vector<int> b) {return a[1]<b[1];});  //按起始点从小到大排列
        int xend = points[0][1]; // xstart = points[0][0],
        int nArrow = 0;
        for(int i =0;i<points.size();i++){
            //if(xstart<points[i][0]) xstart = points[i][0]; //起始点变大，则更新起始点  其起始点可以一直更新为当前起始点
          //  if(xend>points[i][1])   xend = points[i][1];   //结束点变小，则更新结束点  尾部排序则不需要这判断
            if( points[i][0] > xend ){   //没有公共区域了   
                nArrow++;
                //xstart = points[i][0];    //重新开始计算 更新起始和结束点
                xend =   points[i][1];
            }
        }
        return nArrow+1;


    }
};

• 题目763. 划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

思路：先找出每个字符出现的最远的位置（下标），然后从字符串头开始遍历，把每个字母有它对应的最远的点，记录当前所有字母的最远的位置，如果最远的位置等于现在的位置 ，则可以分段了。再继续往下分。

using namespace std;
class Solution {
public:
    vector<int> partitionLabels(string s) {

        //一开始想转换为区间划分问题，但是因为这是字符串，顺序固定的，所以只需要判断字母出现的最后一个位置就可以了
        //vector<int> mp(26); 
        unordered_map<char,int> mp;    //也可直接用 26的数组
        for(int i= 0 ; i < s.length() ;i++){
            mp[s[i]] = i;  //存放最后出现的下标
        }
        vector<int> res;
        int start = 0,lend= mp[s[0]];   //记得赋初值
        for(int i=0 ; i<s.length();i++){
            if(i>lend){         //起始大于尾部 即可分开  
                res.push_back(i-start);
                start = i;
            }
            lend = mp[s[i]]>lend?mp[s[i]]:lend;  //（尾部要一直更新为当前最长）
        }
        res.push_back( s.length()-start); //最后一个
        return res;
    }
};

• 题目122. 买股票最佳时机

给定一个数组 prices ，其中prices[i]是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：就是求股票所有上升区间的最高点减最低点的价格的总和。

• 一个思路是求出所有上升的区间，去求。
• 一个思路是因为最大收益就是所有增加递增的那些增量，所以只要比前一个价格上涨，就加为收益；

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //贪心算法，因为股票有限制，卖出才能买入，最大收益就是所有增加递增的那些增量；
        long long profit = 0;
        for(int i = 1;i<prices.size();i++){
            profit += max(prices[i]-prices[i-1],0);
        }
        return profit;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = 0;
        long long profit=0;
        bool bought = 0;
        for(int i = 0;i<prices.size();i++){
            if(bought){
                if(i==prices.size()-1||prices[i+1]<prices[i]){   //买入状态下，遇到下降则卖出
                    profit += (prices[i]-buy);
                    bought = 0;
                }
            }else{
                if(i!=prices.size()-1&&prices[i+1]>prices[i]){    //没买情况下，遇到上涨，则买入
                    buy=prices[i];
                    bought = 1;
                }
            }
        }      
        return profit;
    }
};

• 题目406. 重建身高队列

数组people是打乱顺序的一群人，每个people[i] = [hi, ki]表示第i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人。
请重新构造并返回满足每个人位置情况的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j个人的属性（queue[0] 是排在队列前面的人）。

思路：

• 思路1：把所有人按身高从高到低排序，从最高的人开始，一个一个进入结果队列，每次进去的人根据自己前面有多少个比自己高的人（ki）插入到队列中。(因为结果队列里的人都是比自己高的人，所以自己插入到哪里都不会影响前面的那些结果)
• 思路2：把所有人按身高从低到高排序。可以把结果队列看成是一排空座位，因为你知道自己前面有几个比自己高的人，但是不知道有几个比自己矮的人，所以让比自己矮的人先进去坐。最矮的人先进去坐下，它前面要空出ki个座位给比自己高的人，后面的人进来，从头开始遍历座位，数到ki个空座位后（有的座位有比自己矮的人坐着），第ki+1个空座位坐下。
• 注意：身高相同的情况要怎么排序？身高相同时，ki大的人，排在后面，可以把它看成是比排在前面的身高一样的人矮一点点，所以排序时，在身高相同时，再判断下ki，ki大的矮。

#include <vector>
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        从高到低排序，  高的先放，再根据比前面高的有几个人遍历插入，因为后面插入的人比较矮不影响前面的
        sort(people.begin(), people.end(), [](vector<int> a, vector<int> b)
            {return a[0]>b[0] || (a[0] == b[0] && a[1] < b[1]); });//相同高度转为比他矮一点点的，k越大说明越矮。
        int len = people.size();
        vector<vector<int>> res;
        for (int i = 0; i < len; i++) {   //排序好的队列里第几个人
           //第k个人后面插入,因为res里的都比自己高
            res.insert(res.begin()+people[i][1],people[i]);  //必须加上res.begin(),不然报错
        }
        return res;
    }
};

时间复杂度：O（n^2） (快速排序O(nlogn)但是远小于n的平方，所以忽略)
遍历n次插入，插入复杂度n；

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        从低到高排序，前面有几个高的人，就留几个空位置,但你前面有未知个比你矮的人,
        //所以从低到高开始放，你前面有几个比你矮的人就确定了，你就在这基础上再加k个人。
        sort(people.begin(), people.end(), [](vector<int> a, vector<int> b)
            {return a[0]<b[0] || (a[0] == b[0] && a[1] > b[1]); });//相同高度转为比他矮一点点的，k越大说明越矮。
        int len = people.size();
        vector<vector<int>> res(len);
      //  vector<bool> emp(len,0);//是否为空座位       //可以用res是否为空来判断
        int k = 0;//你前面的空座位数
        for (int i = 0; i < len; i++) {   //第几个人
            for (int j = 0; j < len; j++) {    //第几个座位
                if (res[j].empty())//当前空座位数等于你前面比你高的人数，且当前是空位 你就到了你该到的位置
                {
                    if(k == people[i][1]){
                    res[j] = people[i];   
                    k = 0;
                  //  emp[j] = 1;
                    break;
                    }
                    k++;
                }
            }
        }
        return res;
    }
};

时间复杂度同上。