贪心的本质是选择每一阶段的局部最优从而达到全局最优。1.分发饼干每一步都做到局部最优从而实现全局最优难怪说贪心没有模板也没有什么使用的特定条件自己想的时候我根本不会觉得这道题是使用了贪心我甚至会以为这是模拟。整体思路很简单就是饼干尺寸大的既可以满足小胃口的孩子也可以满足大胃口的孩子所以要优先满足大胃口的孩子这样能保证每一次选择都是满足了最多孩子的胃口先将两个数组都排序然后循环看最大的尺寸能不能满足孩子胃口能就result。2.摆动序列因为局部最优可以得到全局最优所以应该就是贪心。考虑三种情况第一种是上下坡中有平坡所以在这种情况就要考虑pre0 的时候否则就会导致情况漏选一开始没注意到这个细节错了好几次。第二种情况是数组只有两个的情况因为我们从第一种情况推出的curnums[i1]-[i]要有三个数字所以我们可以在他的前面加一个一样的数字造成一个小平坡和升坡。最后一个情况就是在单调中有平坡这样之前的代码会导致重复计数所以不能实时更新pre要在坡度有变化的时候再更新。3-最大子序数和这道题确实一看到就想的是暴力解题贪心也可解因为局部最优在于每一步都不取小于零的数则可以取到总体最优。for(inti0;inums.size();i){countnums[i];if(countresult){// 取区间累计的最大值相当于不断确定最大子序终止位置resultcount;}if(count0)count0;// 相当于重置最大子序起始位置因为遇到负数一定是拉低总和}通过比对count和result的大小来判断要不要加入新的子数。4-买卖股票的最佳时机 II这题最主要的是要意识到利润是可以拆开来的我一开始想的是一天买一天卖然后看完题解我以为我错了但是我按照我的方法和题解的都写了一遍都能过。我再仔细看一下其实我的方法和题解是一样的但是题解的更简洁。题解展示的是把每一天的利润都算出来把正利润加上去如下for(inti1;iprices.size();i){resultmax(prices[i]-prices[i-1],0);}很简洁而我想的for(inti0;iprices.size()-1;i){if(prices[i1]prices[i]){resultprices[i1]-prices[i];}}其实仔细看这两个代码是等价的只是我一开始没想这么深并且题解用了一个max比我的更简洁。5-跳跃游戏思路确实不好想问题在一开始会纠结要跳几步。这道题的解法是看范围范围有没有覆盖到最后一个元素如果有则可以到达。所以核心代码入下for(inti0;icover;i){// 注意这里是小于等于covercovermax(inums[i],cover);if(covernums.size()-1)returntrue;// 说明可以覆盖到终点了}6-跳跃游戏2和1的差别在这个要的是几步能到达不是能不能到达题解给了两种思路都是贪心。贪心没什么具体的模版我做的时候也没感到是贪心。但是我有一个问题时我一开始看到题目我忘记1是不用纠结跳几步而是看范围的了。所以这道题也只要看覆盖范围第一个下标覆盖范围如果到不了最后就看第二个下标第二个不行也要加一再看第三个下标。而不是看第一个下标覆盖最后的范围然后再加这样就会漏掉中间大的跳跃数。7-K 次取反后最大化的数组和这题比较简单我直接做没有看题解的想法是先数出k有几个如果刚好相等就直接改成正数相加起来如果大于就分正负找出最好结果如果小于就把最大的几个改成正数。但是我写的时候发现非常繁琐而且不好实现。然后我就去看了题解其实思路是没有什么问题的但是题解给的答案很明显简洁了很多。因为题解一开始就根据绝对值把数字从大到小排好了就不用像我一开始那样再去循环找最小的或者最大的这样好做很多。而且题解一开始不用去数k有几个直接根据排好的顺序在满足k大于0并且当前数字小于0的情况下就可以把它变为正数同时k–。题解有说这里用了两次贪心但说实话做的时候确实没感觉就感觉是在顺着模拟。8-加油站这道题我一开始想的就是循环一个个算过去可以转一圈的就是起点但是这样容易超时而且代码也不够简洁然后就看题解。题解给了两种写法一种是全局出发情况一如果gas的总和小于cost总和那么无论从哪里出发一定是跑不了一圈情况二rest[i] gas[i]-cost[i]为一天剩下的油i从0开始计算累加到最后一站如果累加没有出现负数说明从0出发油就没有断过那么0就是起点。情况三如果累加的最小值是负数汽车就要从非0节点出发从后向前看哪个节点能把这个负数填平能把这个负数填平的节点就是出发节点。这种解法也很巧妙但我觉得法二的贪心更好理解也更巧妙设计一个curSum和一个sum两个都加上gas[i]-cost[i]如果存在curSum小于0的情况则说明起点不会再前i个里最后循环结束一圈如果sum0就说明不存在这样一个起点。9-分发糖果难点在双方向贪心很容易顾头不顾尾我做的时候不太有头绪有一点模糊的感觉但又不知道要怎么写所以直接看题解了。题解给了两层贪心先从前到后再从后到前一次。这个理论还挺简单的但是写起来不是很好写因为很细节循环的过程范围什么的。// 从前向后for(inti1;iratings.size();i){if(ratings[i]ratings[i-1])candyVec[i]candyVec[i-1]1;}// 从后向前for(intiratings.size()-2;i0;i--){if(ratings[i]ratings[i1]){candyVec[i]max(candyVec[i],candyVec[i1]1);}max取当前值和后一个分发的糖果数1之间的较大值。10-柠檬水找零这道题简单很多只要考虑三种情况收到5元收到10元和收到20元分开讨论写清楚就好了这题的贪心体现在找零20的时候优先找零一张10一张5没有才找零三张5. 贪心算法集合
贪心的本质是选择每一阶段的局部最优从而达到全局最优。1.分发饼干每一步都做到局部最优从而实现全局最优难怪说贪心没有模板也没有什么使用的特定条件自己想的时候我根本不会觉得这道题是使用了贪心我甚至会以为这是模拟。整体思路很简单就是饼干尺寸大的既可以满足小胃口的孩子也可以满足大胃口的孩子所以要优先满足大胃口的孩子这样能保证每一次选择都是满足了最多孩子的胃口先将两个数组都排序然后循环看最大的尺寸能不能满足孩子胃口能就result。2.摆动序列因为局部最优可以得到全局最优所以应该就是贪心。考虑三种情况第一种是上下坡中有平坡所以在这种情况就要考虑pre0 的时候否则就会导致情况漏选一开始没注意到这个细节错了好几次。第二种情况是数组只有两个的情况因为我们从第一种情况推出的curnums[i1]-[i]要有三个数字所以我们可以在他的前面加一个一样的数字造成一个小平坡和升坡。最后一个情况就是在单调中有平坡这样之前的代码会导致重复计数所以不能实时更新pre要在坡度有变化的时候再更新。3-最大子序数和这道题确实一看到就想的是暴力解题贪心也可解因为局部最优在于每一步都不取小于零的数则可以取到总体最优。for(inti0;inums.size();i){countnums[i];if(countresult){// 取区间累计的最大值相当于不断确定最大子序终止位置resultcount;}if(count0)count0;// 相当于重置最大子序起始位置因为遇到负数一定是拉低总和}通过比对count和result的大小来判断要不要加入新的子数。4-买卖股票的最佳时机 II这题最主要的是要意识到利润是可以拆开来的我一开始想的是一天买一天卖然后看完题解我以为我错了但是我按照我的方法和题解的都写了一遍都能过。我再仔细看一下其实我的方法和题解是一样的但是题解的更简洁。题解展示的是把每一天的利润都算出来把正利润加上去如下for(inti1;iprices.size();i){resultmax(prices[i]-prices[i-1],0);}很简洁而我想的for(inti0;iprices.size()-1;i){if(prices[i1]prices[i]){resultprices[i1]-prices[i];}}其实仔细看这两个代码是等价的只是我一开始没想这么深并且题解用了一个max比我的更简洁。5-跳跃游戏思路确实不好想问题在一开始会纠结要跳几步。这道题的解法是看范围范围有没有覆盖到最后一个元素如果有则可以到达。所以核心代码入下for(inti0;icover;i){// 注意这里是小于等于covercovermax(inums[i],cover);if(covernums.size()-1)returntrue;// 说明可以覆盖到终点了}6-跳跃游戏2和1的差别在这个要的是几步能到达不是能不能到达题解给了两种思路都是贪心。贪心没什么具体的模版我做的时候也没感到是贪心。但是我有一个问题时我一开始看到题目我忘记1是不用纠结跳几步而是看范围的了。所以这道题也只要看覆盖范围第一个下标覆盖范围如果到不了最后就看第二个下标第二个不行也要加一再看第三个下标。而不是看第一个下标覆盖最后的范围然后再加这样就会漏掉中间大的跳跃数。7-K 次取反后最大化的数组和这题比较简单我直接做没有看题解的想法是先数出k有几个如果刚好相等就直接改成正数相加起来如果大于就分正负找出最好结果如果小于就把最大的几个改成正数。但是我写的时候发现非常繁琐而且不好实现。然后我就去看了题解其实思路是没有什么问题的但是题解给的答案很明显简洁了很多。因为题解一开始就根据绝对值把数字从大到小排好了就不用像我一开始那样再去循环找最小的或者最大的这样好做很多。而且题解一开始不用去数k有几个直接根据排好的顺序在满足k大于0并且当前数字小于0的情况下就可以把它变为正数同时k–。题解有说这里用了两次贪心但说实话做的时候确实没感觉就感觉是在顺着模拟。8-加油站这道题我一开始想的就是循环一个个算过去可以转一圈的就是起点但是这样容易超时而且代码也不够简洁然后就看题解。题解给了两种写法一种是全局出发情况一如果gas的总和小于cost总和那么无论从哪里出发一定是跑不了一圈情况二rest[i] gas[i]-cost[i]为一天剩下的油i从0开始计算累加到最后一站如果累加没有出现负数说明从0出发油就没有断过那么0就是起点。情况三如果累加的最小值是负数汽车就要从非0节点出发从后向前看哪个节点能把这个负数填平能把这个负数填平的节点就是出发节点。这种解法也很巧妙但我觉得法二的贪心更好理解也更巧妙设计一个curSum和一个sum两个都加上gas[i]-cost[i]如果存在curSum小于0的情况则说明起点不会再前i个里最后循环结束一圈如果sum0就说明不存在这样一个起点。9-分发糖果难点在双方向贪心很容易顾头不顾尾我做的时候不太有头绪有一点模糊的感觉但又不知道要怎么写所以直接看题解了。题解给了两层贪心先从前到后再从后到前一次。这个理论还挺简单的但是写起来不是很好写因为很细节循环的过程范围什么的。// 从前向后for(inti1;iratings.size();i){if(ratings[i]ratings[i-1])candyVec[i]candyVec[i-1]1;}// 从后向前for(intiratings.size()-2;i0;i--){if(ratings[i]ratings[i1]){candyVec[i]max(candyVec[i],candyVec[i1]1);}max取当前值和后一个分发的糖果数1之间的较大值。10-柠檬水找零这道题简单很多只要考虑三种情况收到5元收到10元和收到20元分开讨论写清楚就好了这题的贪心体现在找零20的时候优先找零一张10一张5没有才找零三张5.