【leetcode刷刷】455.分发饼干 、376. 摆动序列 、53. 最大子序和

本文主要是介绍【leetcode刷刷】455.分发饼干 、376. 摆动序列 、53. 最大子序和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

455.分发饼干

376. 摆动序列

1. 其实贪心的想法，做过一次的话就不会很难想了。但这道题需要考虑的特殊情况比较复杂，包括平台什么的。
2. 最左边和最右边也需要考虑：最左边，添加一个平台。
   • 可以假设，数组最前面还有一个数字，那这个数字应该是什么呢？
   • 之前我们在 讨论 情况一：相同数字连续 的时候， prediff = 0 ，curdiff < 0 或者 >0 也记为波谷。
   • 那么为了规则统一，针对序列[2,5]，可以假设为[2,2,5]，这样它就有坡度了即 preDiff = 0，如图：
3. 单调平坡的情况：我们只需要在 这个坡度 摆动变化的时候，更新 prediff 就行，这样 prediff 在 单调区间有平坡的时候 就不会发生变化，造成我们的误判
4. 动态规划怎么做？

class Solution:def wiggleMaxLength(self, nums: List[int]) -> int:# 求峰值的个数if len(nums) <= 1:return len(nums)curdiff = 0prediff = 0result = 1  # 左侧for i in range(len(nums)-1):curdiff = nums[i+1] - nums[i]   # 后一个和当前的差值if curdiff * prediff <= 0 and curdiff != 0:  # 只有cur出现摆动，才表示+1。prediff=0只出现在开头result += 1prediff = curdiff   # 只在摆动的时候改变prediffreturn result

class Solution:def wiggleMaxLength(self, nums: List[int]) -> int:# dp# dp[i][0] i 作为波峰的最大长度# dp[i][1] i 作为波谷的最大长度dp = []for i in range(len(nums)):dp.append([1, 1])for j in range(i):# nums[i]为波谷if nums[j] > nums[i]:dp[i][1] = max(dp[j][0]+1, dp[i][1])  # j是前面的某个波峰# nums[i]为波峰if nums[j] < nums[i]:dp[i][0] = max(dp[i][0], dp[j][1]+1)return max(dp[-1][0], dp[-1][1])

53. 最大子序和

1. 暴力法比较好写，但是贪心确实挺难想的。。。没有见过的题咋写呢。。。

class Solution:def maxSubArray(self, nums: List[int]) -> int:# 贪心算法result = float('-inf')count = 0for i in range(len(nums)):count += nums[i]result = max(count, result)if count < 0:count = 0return result# 暴力法result = float('-inf')for i in range(len(nums)):count = 0for j in range(i, len(nums)):count += nums[j]result = max(result, count)return result

这篇关于【leetcode刷刷】455.分发饼干 、376. 摆动序列 、53. 最大子序和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---