「算法刷题」贪心算法的相关经典题目

Posted on Edited on
LeetCode题目 相关题目类型 相关链接
455 分发饼干（简单难度） 383. 赎金信 - 力扣（LeetCode） (leetcode-cn.com)

为了了满足更多的小孩，就不要造成饼干尺寸的浪费。

大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。

这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

可以尝试使用贪心策略，先将饼干数组和小孩数组排序。

然后从后向前遍历小孩数组，用大饼干优先满足

image-20211029212703299

这个例子可以看出饼干9只有喂给胃口为7的小孩，这样才是整体最优解，并想不出反例，那么就可以撸代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 时间复杂度：O(nlogn)
// 空间复杂度：O(1)
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int index = s.size() - 1; // 饼干数组的下标
        int result = 0;
        for (int i = g.size() - 1; i >= 0; i--) {
            if (index >= 0 && s[index] >= g[i]) {
                result++;
                index--;
            }
        }
        return result;
    }
};

从代码中可以看出我用了一个index来控制饼干数组的遍历，遍历饼干并没有再起一个for循环，而是采用自减的方式，这也是常用的技巧。

有的同学看到要遍历两个数组，就想到用两个for循环，那样逻辑其实就复杂了。

也可以换一个思路，小饼干先喂饱小胃口

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int index = 0;
        for(int i = 0;i < s.size();++i){
            if(index < g.size() && g[index] <= s[i]){
                index++;
            }
        }
        return index;
    }
};
LeetCode题目 相关题目类型 相关链接
1005 K次取反后最大化的数组和（简单难度） 1005. K 次取反后最大化的数组和 - 力扣（LeetCode） (leetcode-cn.com)

本题思路其实比较好想了，如何可以让数组和最大呢？

贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。

局部最优可以推出全局最优。

那么如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大。

那么又是一个贪心：局部最优：只找数值最小的正整数进行反转，当前数值可以达到最大（例如正整数数组{5, 3, 1}，反转1 得到-1 比 反转5得到的-5 大多了），全局最优：整个 数组和 达到最大。

虽然这道题目大家做的时候，可能都不会去想什么贪心算法，一鼓作气，就AC了。

我这里其实是为了给大家展现出来 经常被大家忽略的贪心思路，这么一道简单题，就用了两次贪心！

那么本题的解题步骤为：

  • 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
  • 第二步：从前向后遍历，遇到负数将其变为正数，同时K–
  • 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
  • 第四步：求和

对应C++代码如下：

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
class Solution {
static bool cmp(int a,int b){
    return abs(a)>abs(b);
}

public:
    int largestSumAfterKNegations(vector<int>& A, int K) {
        //将数组按照绝对值大小，从大到小排列
        sort(A.begin(),A.end(),cmp);
        //如果数组中有负数，转为正数，同时k--
        for(int i=0;i<A.size()-1;i++){
            if(A[i]<0&&K>0){
                A[i]*=-1;
                K--;

            }
        }
        //如果k不为0，把数组中最小的数反复乘以-1，直到k用完
        //K%2==0的话，数组中的数还是原数
        if(K%2==1){
            A[A.size()-1]*=-1;
        }
        //求和
        int res=0;
        for(int a:A){
            res+=a;
        }
        return res;
        
    }
};
LeetCode题目 相关题目类型 相关链接
860 柠檬水找零（简单难度） 860. 柠檬水找零 - 力扣（LeetCode） (leetcode-cn.com)

本题只需维护三种金额的数量：5,10,20，

情况一：账单是5，直接收下。

情况二：账单是10，消耗一个5，增加一个10

情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

（收款20时，局部最优：优先消耗10和5，完成本次找零。少消耗5，因为5可以给10和20找零。全局最优：完成全部账单的找零。

局部最优可以推出全局最优，且找不到反例，就可以尝试贪心算法。

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
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five=0,ten=0,twenty=0;
        for(int bill:bills){
            //收到5
            if(bill==5){
                five++;
            }
            //收到10
            else if(bill==10){
                if(five<=0){
                    return false;
                }
                else{
                    ten++;
                    five--;
                }
                
            }
            //收到20
            else if(bill==20){
                if(five>=1&&ten>=1){//优先用10来找零
                    five--;
                    ten--;
                    twenty++;//可以不记录20块钱的个数，不用20找零
                }
                else if(five>=3){
                    five-=3;
                    twenty++;//可以不记录20块钱的个数，不用20找零
                }
                else{
                    return false;
                }
            }
        }
        return true;
    }
};
LeetCode题目 相关题目类型 相关链接
53 最大子序和（简单难度） 53. 最大子序和 - 力扣（LeetCode） (leetcode-cn.com)

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

全局最优：选取最大“连续和”

遍历nums，从头开始用count累积，如果count一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积count了，因为已经变为负数的count，只会拖累总和。

中间的最大和由result记录下来了。

题目中的答案有个示例【-2，-1】

if(result<count)和if(count<=0)，写的时候我颠倒了，会改变了count的值，res就记录不到正确的最大值了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;
        int count = 0;
        for(int i=0;i<nums.size();i++){
            count+=nums[i];
            if(result<count){
                result=count;
            } 
            if(count<=0){
                count=0;
            }
        }
        return result;
    }
};
LeetCode题目 相关题目类型 相关链接
452 用最少数量的箭引爆气球（中等难度） 452. 用最少数量的箭引爆气球 - 力扣（LeetCode） (leetcode-cn.com)

直觉上来看，貌似只射重叠最多的气球，用的弓箭一定最少

试一下举反例，发现没有这种情况。

那么就试一试贪心吧！

局部最优：当气球出现重叠，一起射，所用弓箭最少。

全局最优：把所有气球射爆所用弓箭最少。

为了让气球尽可能的重叠，需要对数组进行排序。用到sort函数

这里的排序不是简单的对整数排序，是按照数组的第一元素从小到大排序，不能简单地用sort(nums.begin(),nums.end()),

而是用sort(nums.begin(),nums.end(),cmp),cmp函数必须加上static，返回值是bool类型。例如：

static bool cmp(vector& a,vector& b){

​ return a[0]<b[0];

}

传入参数时，如果是数组，用引用&不会另外开辟内存，而是直接用原数组的数进行运算。不用引用&，会为参数另外开辟内存，每次用cmp函数都要花时间开辟内存，可能会运行超出时间限制。

按照气球的起始位置排序，从前向后遍历气球数组，尽可能让气球重复，前两个区间：比较第一个的右边界>=第二个的左边界，则气球重叠。有两个已经重叠，再比较第三个时，要比较前两个区间的最小右边界和第三个区间的左边界。因为如果想三个都重叠，必须满足最小的右边界（画图可以看出）。

前两个重叠时，不用弓箭加一，因为刚开始默认弓箭为1（因为数组数>=1）.不重叠，那肯定需要再有一个弓箭射后面的气球，这时弓箭数加一。

代码：

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
class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b){
        return a[0]<b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        /*输入一个二维数组，输出一个整数*/
        if(points.size()==1){
            return 1;
        }
        // 先将二维数组排序
        sort(points.begin(),points.end(),cmp);
        int result=1;// 需要几只箭
        for(int i=1;i<points.size();i++){
            // 会发生重叠
            if(points[i-1][1]>=points[i][0]){
                points[i][1]=min(points[i][1],points[i-1][1]);// 更新当前气球的右边界
            }
            // 没有重叠
            else{
                result++;
            }
            
        }
        return result;
    }
};
LeetCode题目 相关题目类型 相关链接
435 无重叠区间（中等难度） 435. 无重叠区间 - 力扣（LeetCode） (leetcode-cn.com)

本题与i452的区别：

移除重叠区间，按照右边界从小到大排序，如果前一个的右边界大于下一个的左边界，则算是重叠，然后保留重叠两个区间的右边界最小值（较大的可能会重叠更多区间，题目要求是移除区间的最小数量）

cmp两种都可以，第二种，考虑了如果两个元素相等，再怎么判断。但a[0]<b[0];应该会对相等情况给一个结果应该。

1
2
3
4
 static bool cmp(vector<int>& a,vector<int>& b){
         
    return a[0]<b[0];
}

和

 static bool cmp(vector<int>& a,vector<int>& b){
    if(a[0]==b[0]){
         return a[1]<b[1];
    }
    return a[0]<b[0];
}

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
class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b){
        
        if(a[0]==b[0]){
            return a[1]<b[1];
        }
        return a[0]<b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        /*输入一个二维数组，输出一个整数*/
        if(points.size()==1){
            return 1;
        }
        // 先将二维数组排序
        sort(points.begin(),points.end(),cmp);
        int result=1;// 需要几只箭
        for(int i=1;i<points.size();i++){
            // 会发生重叠
            if(points[i-1][1]>=points[i][0]){
                points[i][1]=min(points[i][1],points[i-1][1]);// 更新当前气球的右边界
            }
            // 没有重叠
            else{
                result++;
            }
            
        }
        return result;
    }
};
LeetCode题目 相关题目类型 相关链接
56 合并区间（中等难度） 56. 合并区间 - 力扣（LeetCode） (leetcode-cn.com) 
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
static bool cmp(vector<int> &a,vector<int> &b){
        return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        /*输入一个二维数组，输出一个二维数组*/
        if(intervals.size()==1){
            return intervals;
        }
        //对数组进行排序
        sort(intervals.begin(),intervals.end(),cmp);
        //
        vector<vector<int>> result;
        bool flag = false;// 标记最后一个区间有没有合并
        for(int i=1;i<intervals.size();i++){
            // 当相邻区间重叠时，合并，当前区间i就是合并后的区间
            int start=intervals[i-1][0];
            int end = intervals[i-1][1];
            
            while(i<intervals.size()&&end>=intervals[i][0]){
                end = max(intervals[i][1],end);
                if (i == intervals.size() - 1) flag = true;
                i++;
            }
            result.push_back({start,end});
        }
        // 如果最后一个区间没有和前一个区间重叠，将需单独加入result
        if (flag == false) {
            result.push_back({intervals[intervals.size() - 1][0], intervals[intervals.size() - 1][1]});
        }
        return result;
    }
LeetCode题目* 相关题目类型 相关链接
55 跳跃游戏（中等难度） 55. 跳跃游戏 - 力扣（LeetCode） (leetcode-cn.com)

该题判断是否能跳到终点。

刚看到本题一开始可能想：当前位置元素如果是3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？

其实跳几步无所谓，关键在于可跳的覆盖范围！不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。

这个范围内，别管是怎么跳的，反正一定可以跳过来。

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        if (nums.size() == 1) return true; // 只有一个元素，就是能达到
        for (int i = 0; i <= cover; i++) { // 注意这里是小于等于cover
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
        }
        return false;
    }
};
题目 相关链接
763划分字母区间（中等难度）

记录每个字符在数组中出现的最远距离，找到之前遍历过的所有字母的最远边界，这个边界点就是分割点。前面出现的所有字母最远就到这个边界。

分为两步：

1 统计每个字符出现的最远位置

2 从头遍历字符，更新字符出现的最远下表，如果找到字符最远出现位置下表和当前下标相等，则找到了分割点。

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

};
LeetCode题目* 相关题目类型 相关链接
135 （中等难度） 55. 跳跃游戏 - 力扣（LeetCode） (leetcode-cn.com)

这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。

先确定右边评分大于左边的情况（也就是从前向后遍历）

此时局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果

2.再确定左孩子大于右孩子的情况（从后向前遍历）

遍历顺序这里有同学可能会有疑问，为什么不能从前向后遍历呢？

因为如果从前向后遍历，根据 ratings[i + 1] 来确定 ratings[i] 对应的糖果，那么每次都不能利用上前一次的比较结果了。

如果 ratings[i] > ratings[i + 1]，此时candyVec[i]（第i个小孩的糖果数量）就有两个选择了，一个是candyVec[i + 1] + 1（从右边这个加1得到的糖果数量），一个是candyVec[i]（之前比较右孩子大于左孩子得到的糖果数量）。

那么又要贪心了，局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量即大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果。

整体代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyVec(ratings.size(), 1);
        // 从前向后
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
        }
        // 从后向前
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] ) {
                candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
            }
        }
        // 统计结果
        int result = 0;
        for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];
        return result;
    }
};