代码随想录算法训练营 Day31 贪心算法1

本文主要是介绍代码随想录算法训练营 Day31 贪心算法1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Day31 贪心算法1

理论基础

贪心算法的本质：找到每个阶段的局部最优，从而去推导全局最优

贪心的两个极端：要么觉得特别简单，要么觉得特别难

贪心无套路
不像二叉树、递归，有固定模式

贪心题目的思考方式
做题的时候，想到局部最优是什么，然后能够推出全局最优，且想不到反例，就可以试一下贪心

455.分发饼干

思路

局部最优：用最小的饼干尺寸满足最小胃口的孩子
全局最优：根据饼干尺寸从小到大一步步满足孩子胃口，满足就分配，不满足就用下一个
for循环遍历所有的饼干，判断如果满足，指向孩子胃口的指针加一，结果加一

尝试写代码：

class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:s.sort()g.sort()result = 0child = 0for i in range(len(s)):if child < len(g) and s[i] >= g[child]:result += 1child += 1return result

成功通过

根据代码随想录
局部最优：每次找到一个大的饼干，满足胃口大的小孩
全局最优：可以喂饱的小孩子的数量最大
局部最优好像可以推出全局最优，且找不到反例

代码要点：

1. for循环控制小孩胃口
2. if和index控制饼干
3. 外面for循环遍历胃口，里面遍历饼干，不可以颠倒

大饼干满足大胃口：

class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:s.sort()g.sort()result = 0index = len(s) - 1for i in range(len(g) - 1, -1, -1):if index >= 0 and g[i] <= s[index]:result += 1index -= 1return result

376. 摆动序列

思路

局部最优：找到当前的满足摆动序列的元素
全局最优：每一个组成字序列的元素都满足摆动序列
通过删除不满足的数，使得最终的nums数组为摆动序列

尝试写代码：

class Solution:def wiggleMaxLength(self, nums: List[int]) -> int:index = 0if len(nums) <= 1:return len(nums)while index < len(nums):if index == 1:if nums[index] == nums[index - 1]:del nums[index]continueelif nums[index - 1] - nums[index - 2] < 0 and nums[index] - nums[index - 1] < 0:del nums[index]continueelif nums[index - 1] - nums[index - 2] > 0 and nums[index] - nums[index - 1] > 0:del nums[index]continueindex += 1return len(nums)

测试用例通过，但结果不对

根据代码随想录：
要点：

1. 画图，需要删除的是单调坡上的元素
2. 局部最优：单调坡中的元素删除
3. 全局最优：得到最长的摆动序列
4. 其实没有必要真的具体删除元素，因为题目求的是长度，因此只需要遇到摆动就加一，然后返回数值就行
5. 判断峰值：prediff和curdiff一大一小
6. 特殊情况：需要考虑遇到平坡的情况，在判断prediff时，包含0
7. 特殊情况：如果总长度只有两个元素，默认两个元素的前面有个平坡，result一开始为1，即包含最后一个摆动，这样就可以将这种情况加入整体逻辑中
8. 特殊情况：单调坡中有平坡，因此prediff只在有摆动的时候，才改变

最终代码：

class Solution:def wiggleMaxLength(self, nums: List[int]) -> int:prediff = 0curdiff = 0result = 1if len(nums) == 1:return 1for i in range(len(nums) - 1):curdiff = nums[i + 1] - nums[i]if (prediff >= 0 and curdiff < 0) or (prediff <= 0 and curdiff > 0):result += 1prediff = curdiffreturn result

总结：
我一开始的思路只是顺着序列遍历比较，没有考虑到整体情况，因此可能会漏掉一些数，导致结果不对。代码随想录是通过画图，将所有的数值放在一起比较，发现峰值不能删，这样结果是可靠的

53. 最大子序和

思路

不知道怎么样算局部最优

根据代码随想录
本题也可以用动规来做

要点：

1. 如果当前的连续和为负数，再加后面的数只会让和最小
2. 局部最优：连续和为负数时，选择下一个数为新起点重新计算
3. 全局最优：找到最大连续子数组的和
4. 每次记录时，用result记录局部最大

最终代码：

class Solution:def maxSubArray(self, nums: List[int]) -> int:result = float('-inf')count = 0for i in range(len(nums)):count += nums[i]if count > result:result = countif count < 0:count = 0return result

这篇关于代码随想录算法训练营 Day31 贪心算法1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---