网站手机版模板免费下载,衡水网站制作费用,网站建设及运营工作总结,安卓市场应用商店下载代码随想录 什么是贪心
贪心的本质是选择每一阶段的局部最优#xff0c;从而达到全局最优。
这么说有点抽象#xff0c;来举一个例子#xff1a;
例如#xff0c;有一堆钞票#xff0c;你可以拿走十张#xff0c;如果想达到最大的金额#xff0c;你要怎么拿#xff…代码随想录 什么是贪心
贪心的本质是选择每一阶段的局部最优从而达到全局最优。
这么说有点抽象来举一个例子
例如有一堆钞票你可以拿走十张如果想达到最大的金额你要怎么拿
指定每次拿最大的最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果是 有一堆盒子你有一个背包体积为n如何把背包尽可能装满如果还每次选最大的盒子就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。
什么时候用贪心
贪心算法、动态规划、机器学习都属于优化算法。当题目要求最优解的时候基本上都是贪心算法或者动态规划
贪心算法并没有固定的套路。
所以唯一的难点就是如何通过局部最优推出整体最优。
那么如何能看出局部最优是否能推出整体最优呢有没有什么固定策略或者套路呢
不好意思也没有 靠自己手动模拟如果模拟可行就可以试一试贪心策略如果不可行可能需要动态规划。
有同学问了如何验证可不可以用贪心算法呢
最好用的策略就是举反例如果想不到反例那么就试一试贪心吧。
可有有同学认为手动模拟举例子得出的结论不靠谱想要严格的数学证明。
一般数学证明有如下两种方法
数学归纳法反证法
看教课书上讲解贪心可以是一堆公式估计大家连看都不想看所以数学证明就不在我要讲解的范围内了大家感兴趣可以自行查找资料。
面试中基本不会让面试者现场证明贪心的合理性代码写出来跑过测试用例即可或者自己能自圆其说理由就行了。
举一个不太恰当的例子我要用一下11 2但我要先证明11 为什么等于2。严谨是严谨了但没必要。
虽然这个例子很极端但可以表达这么个意思刷题或者面试的时候手动模拟一下感觉可以局部最优推出整体最优而且想不到反例那么就试一试贪心。
贪心一般解题步骤
贪心算法一般分为如下四步
将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解
这个四步其实过于理论化了我们平时在做贪心类的题目 很难去按照这四步去思考真是有点“鸡肋”。
做题的时候只要想清楚 局部最优 是什么如果推导出全局最优其实就够了。
题目
455.分发饼干
455. 分发饼干_侯孟禹的博客-CSDN博客
53. 最大子序和
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路1.因为求最大和第一个数就是正数才能成为优解所以当第一个数是负数的时候就跳过 2.求和时一旦当前和为负数则直接放弃新加上的数肯定是负数从下一个数作为第一个数重新开始。 代码
class Solution {
public:int maxSubArray(vectorint 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(vectorint 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(vectorint 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(vectorint 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(vectorint 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(vectorint 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(vectorint 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[i1]时i 号学生的糖果数量将比 i1号孩子的糖果数量多。
我们遍历该数组两次处理出每一个学生分别满足左规则或右规则时最少需要被分得的糖果数量。每个人最终分得的糖果数量即为这两个数量的最大值。
class Solution {
public:int candy(vectorint ratings) {vectorint 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;}
};
