贪心算法-

代码随想录

什么是贪心

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

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

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

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

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

再举一个例子如果是 有一堆盒子，你有一个背包体积为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]会返回空，正确返回-1int 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++) { // 注意这里是小于等于covercover = 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;}
};