贪心算法-

代码随想录

什么是贪心

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

这么说有点抽象，来举一个例子：

例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？

指定每次拿最大的，最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。

什么时候用贪心 

贪心算法、动态规划、机器学习都属于优化算法。当题目要求最优解的时候基本上都是贪心算法或者动态规划

贪心算法并没有固定的套路。

所以唯一的难点就是如何通过局部最优，推出整体最优。

那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？

不好意思，也没有！ 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。

有同学问了如何验证可不可以用贪心算法呢？

最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

可有有同学认为手动模拟，举例子得出的结论不靠谱，想要严格的数学证明。

一般数学证明有如下两种方法：

• 数学归纳法
• 反证法

看教课书上讲解贪心可以是一堆公式，估计大家连看都不想看，所以数学证明就不在我要讲解的范围内了，大家感兴趣可以自行查找资料。

面试中基本不会让面试者现场证明贪心的合理性，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了。

举一个不太恰当的例子：我要用一下1+1 = 2，但我要先证明1+1 为什么等于2。严谨是严谨了，但没必要。

虽然这个例子很极端，但可以表达这么个意思：刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。

贪心一般解题步骤

贪心算法一般分为如下四步：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

这个四步其实过于理论化了，我们平时在做贪心类的题目 很难去按照这四步去思考，真是有点“鸡肋”。

做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了。

题目

455.分发饼干

455. 分发饼干_侯孟禹的博客-CSDN博客

53. 最大子序和

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路：1.因为求最大和，第一个数就是正数才能成为优解，所以当第一个数是负数的时候就跳过

           2.求和时，一旦当前和为负数则直接放弃（新加上的数肯定是负数），从下一个数作为第一个数重新开始。
 

代码：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT32_MIN;//不能设成0，否则序列[-1]会返回空，正确返回-1
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            count += nums[i];
 
            if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）
                result = count;
            }
 
            //这一句保证第一个数为正；同时也保证当前和为负时从下一个元素重新开始
            if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
        }
        return result;
    }
};

 本题动态规划解法：代码随想录

122.买卖股票的最佳时机 II

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路：

如果想到其实最终利润是可以分解的，那么本题就很容易了！

如何分解呢？

假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！

那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0;
        for (int i = 1; i < prices.size(); i++) {
            result += max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
};

55. 跳跃游戏

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

我的想法：

        第一版：从后往前推，sum计算从后往前的和，nums[len-2]>1;nums[len-2] + nums[len-3]>2;

代码：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size() == 1) return true;
        if(nums[0] == 0) return false;
        int index = nums.size() - 2;
        int sum = 0;
        int count = 1;
        for(int i = index; i >= 0; i--)
        {
            sum += nums[i];
            if(sum < count)
            {
                return false;
            }
            count++;
        }
        return true;
    }
};

存在的问题：[2,0,0]这样是过不了的

正确答案：

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

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

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

代码：

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;
    }
};

 45.跳跃游戏 II

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路：

        1.其实就是一个更新最大范围的过程，只需要统计通过多少次更新就可以达到最大长度

curDistance表示0-2这个范围

nextDistance表示遍历下标0-2后的最大范围即max(nums[0]+0, nums[1]+3, nums[2]+1) =下标4

当遍历到下标2的时候就表示要在走一步了，此时步数count++，下一步走的范围就是nextDistance的范围。当nextDistance>=最大长度的时候就表示够了

class Solution {
public:
    int jump(vector<int>& nums) {
        int count = 0;
        int curDistance = 0;
        int nextDistance = 0;
        for(int i = 0; i < nums.size() - 1; i++)
        {
            nextDistance = max(nextDistance, nums[i] + i);
            if(i == curDistance)
            {
                curDistance = nextDistance;
                count++;
                if(curDistance >= nums.size() - 1) return count;
            }
        }
        return count;
    }
};

1005.K次取反后最大化的数组和

 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

我的想法：1.排序 2.从左到右遇到负数取反，同时k-- 3.剩下k-i%2取余 4.排序，对最小的如果取余为1则取反否则不变 5.求和

我的代码：

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int i = 0;
        for(; i < k && i < nums.size(); i++)
        {
            if(nums[i] < 0)
            {
                nums[i] = 0 - nums[i];
            }
            else
            {
                break;
            }
        }
        sort(nums.begin(), nums.end());
 
         if((k-i)%2 == 1)
            {
                nums[0] = 0 - nums[0];
            }
        int sum = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            sum += nums[i];
        }
        return sum;
    }
};

 随想录思想：

         1.对我的想法中排序为绝对值排序，从右往左遇到负数取反k--，剩余在第一个元素（最小的）上处理，可以减少一次排序 

代码：

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);       // 第一步
        for (int i = 0; i < A.size(); i++) { // 第二步
            if (A[i] < 0 && K > 0) {
                A[i] *= -1;
                K--;
            }
        }
        if (K % 2 == 1) A[A.size() - 1] *= -1; // 第三步
        int result = 0;
        for (int a : A) result += a;        // 第四步
        return result;
    }
};

134. 加油站

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

代码随想录

 理解不过来

135. 分发糖果 

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

官方思路及解法

我们可以将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理。

左规则：当 ratings[i−1]<ratings[i]时，i 号学生的糖果数量将比 i−1 号孩子的糖果数量多。

右规则：当 ratings[i]>ratings[i+1]时，i 号学生的糖果数量将比 i+1号孩子的糖果数量多。

我们遍历该数组两次，处理出每一个学生分别满足左规则或右规则时，最少需要被分得的糖果数量。每个人最终分得的糖果数量即为这两个数量的最大值。

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;
    }
};

860. 柠檬水找零

860. 柠檬水找零 - 力扣（LeetCode）

 

只需要维护两种金额的数量，5，10。

有如下三种情况：

• 情况一：账单是5，直接收下。
• 情况二：账单是10，消耗一个5，增加一个10
• 情况三：账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

 退出条件：1、5块钱小于0则返回false   2、循环完整结束返回true

我的代码：

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        if(bills[0] != 5) return false;//第一个不是5必定不成功
        int five = 0;
        int ten = 0;
        for(int bill : bills)
        {
            if(bill == 5)
            {
                five++;
            }
            else if(bill == 10)
            {
                five--;
                ten++;
            }
            else
            {
                if(ten != 0)
                {
                    //优先找零10快
                    ten--;
                    five--;
                }
                else
                {
                    five -= 3;
                }
            }
            if(five < 0) return false;//只要5块为负则表示不成功
        }
        return true;
    }
};