代码随想录
什么是贪心
贪心的本质是选择每一阶段的局部最优,从而达到全局最优。
这么说有点抽象,来举一个例子:
例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿?
指定每次拿最大的,最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果是 有一堆盒子,你有一个背包体积为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;}
};