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
成功通过
根据代码随想录
局部最优：每次找到一个大的饼干，满足胃口大的小孩
全局最优：可以喂饱的小孩子的数量最大
局部最优好像可以推出全局最优，且找不到反例
代码要点：
- for循环控制小孩胃口
- if和index控制饼干
- 外面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)
测试用例通过，但结果不对
根据代码随想录：
要点：
- 画图，需要删除的是单调坡上的元素
- 局部最优：单调坡中的元素删除
- 全局最优：得到最长的摆动序列
- 其实没有必要真的具体删除元素，因为题目求的是长度，因此只需要遇到摆动就加一，然后返回数值就行
- 判断峰值：prediff和curdiff一大一小
- 特殊情况：需要考虑遇到平坡的情况，在判断prediff时，包含0
- 特殊情况：如果总长度只有两个元素，默认两个元素的前面有个平坡，result一开始为1，即包含最后一个摆动，这样就可以将这种情况加入整体逻辑中
- 特殊情况：单调坡中有平坡，因此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. 最大子序和
思路
不知道怎么样算局部最优
根据代码随想录
本题也可以用动规来做
要点：
- 如果当前的连续和为负数，再加后面的数只会让和最小
- 局部最优：连续和为负数时，选择下一个数为新起点重新计算
- 全局最优：找到最大连续子数组的和
- 每次记录时，用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
