接练题

贪心算法没有固定的套路通常根据做题人的做题经验才能写出贪心算法。

且算法有难度并不总是简单的。

贪心算法是一种常识思想需要在做题中慢慢感觉和领悟。

分发饼干

分发饼干是一道贪心算法的启蒙题但是实际上我三道题都未能自己做出来对贪心算法一无所知。

题目大意是将一些饼干分发给一些小孩子们小孩子们胃口各不相同且每个孩子只能喂食一块饼干要求是饼干的尺寸大于等于孩子的胃口值求最多可以使几个孩子吃饱解题的思路是我们可以创建一个变量count来记述我们已经满足了几个孩子然后将孩子数组和饼干数组分别排序使它们变得有序方便操作用一个循环控制两个变量当满足时候让饼干下标和孩子下标分别往后走count自增不满足只让饼干下标向后走这样的原因是两数组有序那么满足这个孩子的饼干如果存在那么只可能在后面的饼干而如果连这个孩子都无法满足那肯定后面的孩子也无法满足。

这就是排序的好处如果不排序那一个孩子需要遍历全部饼干同样也要遍历所有孩子这样会严重影响代码效率时间为O(N^2)。

class

{sort(g.begin(),g.end());sort(s.begin(),s.end());int

count0;for(int

i0,j0;ig.size()js.size();){if(s[j]g[i]){count;i;j;continue;}j;}return

count;}

};排序起初我没有想到但是看了题解我想到了这种方法代码看起来略显冗余下面看一个思路一样但是代码却很精简也不用count来计数的方法。

class

{sort(g.begin(),g.end());sort(s.begin(),s.end());int

index0;for(int

i0;is.size();i){if(indexg.size()g[index]s[i]){index;}}return

index;}

};我们用index来代替count和小孩数组的下标用i来代替饼干下标核心的思路是相同的保证不要越界然后当饼干能够满足小孩index就自增怎么样是不是简洁了不少而且还巧妙的用孩子下标做了返回值。

摆动序列

在做这道题时候特别懵没有任何思路看了题解也很懵后来想了一阵才慢慢明白。

题的大意是求摆动序列可以删除改定序列的若干个元素最后构成一个摆动序列摆动序列的定义是严格按照数字之间的差值在正数和负数之间来回摆动。

实现预判式的在一个序列里删除某些节点而达到拼成最大摆动序列是十分困难的。

我们给出另一种解题思路让我们不用删除节点却起到了删除节点的效果。

具体做法为将一个序列模拟成山峰和山谷的示意图也就是说把这些数都画出来看它们的拐向我们只要拐向一次向上一次向下的那种如果中间是连续向上或者向下亦或者是平的两个相邻数相等我们全都统统不要。

那么如何知道中间要删除这些节点然后还能将删除后的两段连上呢这是十分巧妙的做法我们先定义两个变量一个代表上一次两个数的差值另一个代表的是现在的相邻两个数的差值如果两个差值是有正负变化的前一个差值是0现在的差值是大于0或者小于0的同样符合摆动反过来也是那么就将计数器加1且上一个的差值被改成当前的然后进行下一次的循环。

class

i0;inums.size()-1;i){curnums[i1]-nums[i];if((cur0pre0)||(cur0pre0)){count;precur;}}return

count;}

};还有一些细节需要交代一下首先我们知道如果有摆动序列那么至少要有1个数据来组成该序列所以我们count要从1开始起这是很关键的由于我们让count从1开始那么有几个拐点直接加在一起就是此时最大摆动序列的总长度而为什么要将precur写到if的里面呢如果if没进去我们就不改写前一个差的数值实际上我们可以通过模拟得知这种写法和把它写到外面在一般的测试用例下跑出来的答案是一样的

但是如果碰到了序列走势是向上–平–向上这种情况呢这种情况把pre写在if的外面会使拐点多算一次实际上我们摆动序列是2这样算起来是3所以不能这样写摆动序列的定义不能连续向上即使中间有平也不行况且平本来就不算在内这也是代码的关键所在它模拟出了我们在真实删除数据时是如何将删除后两段又重新链接在一起了由于判断摆动符合我们才改变pre的值所以不符合时候它一直是上一次符合时候的差值当再次符合时进入if我们才改动pre这也就相当于联系起了删除中间节点后两个链条的连接这里的代码虽然简短但是每一步的思路尤其重要建议大家用心去体会其过程的巧妙之处。

最大子数组和

求最大的子数组连续和这道题的题目大意和题目名字相同首先能想到的一种思路是暴力法双for来解决问题一个for循环控制数组起始位置遍历一个控制终点两层遍历后找到最大子数组和是多少返回这种方法貌似以前是可以通过的但是现在不行了直接提交这种暴力解法会提示超时这道题同样我们也是可以用贪心来做出来的。

思路其实很简单我们用sum来记录当前总和再用一个变量result来记录我们历史记录中取到的最大值和它作比较比result大则与之交换而贪的是如果sum小于0直接sum0再从当前位置向后与sum相加再记录而暴力解法中的数组结束位置我们用每次的result判断来代替每一次循环都判断一次也就相当于这一步骤了

class

i0;inums.size();i){sumnums[i];if(sumresult)resultsum;if(sum0)sum0;}return

result;}

};如果数据全是-1呢那它会求得答案为0吗肯定是不会的自行调试便知道在sum0之前由于我们result取得是int里最小的数我们先行进行交换使result-1然后sum0后再加上-1结果还是-1它不可能变成0这也就是为什么要把sum数据写在前面result最小数是为了避免有负数和的产生。

从以上三题中我个人认为求某个条件下的最大的某某数这类题应该是可以考虑用贪心算法做一下的除了第二题有些难想外第一题和第三题实际上确实是“常识”类的解题思路但是有时候确实没有做过的话还是无法做得出来重要的是多多积累和总结第一题实际上我觉得最重要的是排序没有排序我们不可能那么轻易的解出来而不用遍历那么多的数据第二题是运用峰值的巧妙之处求取了最长的摆动序列数据个数第三道题贪的是sum小于0立刻重新计数

为什么当它为负数时候直接sum0了却不从之前数组统计的下一个开始计数而是直接从当前位置向后计数呢因为之前的数相加时候我们已经用resul来记录了这一段数据中最大的数是多少数据是要连续的遍历相加。

还不懂不妨举一个例子例如数据整体序列为{-534-85}我们知道最大子数组和肯定是5那我们看前面走到-5直接跳了出来然后34-8才跳了出来那你说4-8会比34-8还要大吗

肯定不能这是一种情况说明了如果前一个数和后一个数都是正数那么实际上从它的下一个位置开始走不可能找得到比从刚才那个数还大的组合了那有人会说如果前一个数是负数后一个数是正数不就能找的到了吗也同样的可以模拟如果还是{-534-85}那样的话第一个-5遇到了后面直接sum0了如果是{-53-275}那从3向后遍历的和实际上是比从正数7大的很多时候我们都可以用模拟来解决问题。

今天我们完成了分发饼干、摆动序列、最大子数组和三道题相关的思想需要多复习回顾。

接下来我们继续进行算法练习。

希望我的文章和讲解能对大家的学习提供一些帮助。

当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~