算法第26天 | 贪心算法、455.分发饼干、376. 摆动序列、 53. 最大子序和

弹性算法理论基础

想清楚 局部最优 是什么，如果可以推导出全局最优，那就是正确的贪心算法

455. 分发饼干

题目

思路与解法

class Solution:def findContentChildren(self, g: List[int], s: List[int]) -> int:res = 0i = 0j = 0g.sort()s.sort()while i < len(s) and j < len(g):if s[i] >= g[j]:res += 1j += 1i += 1return res

376. 摆动序列

题目

思路与解法

没太懂，但是不想细想了

class Solution:def wiggleMaxLength(self, nums: List[int]) -> int:if len(nums) <= 1:return len(nums)  # 如果数组长度为0或1，则返回数组长度curDiff = 0  # 当前一对元素的差值preDiff = 0  # 前一对元素的差值result = 1  # 记录峰值的个数，初始为1（默认最右边的元素被视为峰值）for 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 += 1  # 峰值个数加1preDiff = curDiff  # 注意这里，只在摆动变化的时候更新preDiffreturn result  # 返回最长摆动子序列的长度

53. 最大子序和

题目

思路与解法

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