django做企业级网站,什么软件推广效果好,百度网盘pc端网页版,做任务领佣金的网站源码455.分发饼干
376. 摆动序列
其实贪心的想法#xff0c;做过一次的话就不会很难想了。但这道题需要考虑的特殊情况比较复杂#xff0c;包括平台什么的。最左边和最右边也需要考虑#xff1a;最左边#xff0c;添加一个平台。 可以假设#xff0c;数组最前面还有一个数字…455.分发饼干
376. 摆动序列
其实贪心的想法做过一次的话就不会很难想了。但这道题需要考虑的特殊情况比较复杂包括平台什么的。最左边和最右边也需要考虑最左边添加一个平台。 可以假设数组最前面还有一个数字那这个数字应该是什么呢之前我们在 讨论 情况一相同数字连续 的时候 prediff 0 curdiff 0 或者 0 也记为波谷。那么为了规则统一针对序列[2,5]可以假设为[2,2,5]这样它就有坡度了即 preDiff 0如图 单调平坡的情况我们只需要在 这个坡度 摆动变化的时候更新 prediff 就行这样 prediff 在 单调区间有平坡的时候 就不会发生变化造成我们的误判动态规划怎么做
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[i1] - nums[i] # 后一个和当前的差值if curdiff * prediff 0 and curdiff ! 0: # 只有cur出现摆动才表示1。prediff0只出现在开头result 1prediff curdiff # 只在摆动的时候改变prediffreturn resultclass 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. 最大子序和
暴力法比较好写但是贪心确实挺难想的。。。没有见过的题咋写呢。。。
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
