455.分发饼干
376. 摆动序列
- 其实贪心的想法,做过一次的话就不会很难想了。但这道题需要考虑的特殊情况比较复杂,包括平台什么的。
- 最左边和最右边也需要考虑:最左边,添加一个平台。
- 可以假设,数组最前面还有一个数字,那这个数字应该是什么呢?
- 之前我们在 讨论 情况一:相同数字连续 的时候, prediff = 0 ,curdiff 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 = 0
prediff = 0
result = 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 += 1
prediff = curdiff # 只在摆动的时候改变prediff
return 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. 最大子序和
- 暴力法比较好写,但是贪心确实挺难想的。。。没有见过的题咋写呢。。。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 贪心算法
result = float('-inf')
count = 0
for i in range(len(nums)):
count += nums[i]
result = max(count, result)
if count 0:
count = 0
return result
# 暴力法
result = float('-inf')
for i in range(len(nums)):
count = 0
for j in range(i服务器托管网, len(nums))服务器托管网:
count += nums[j]
result = max(result, count)
return result
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
服务器托管网 Qt PCL学习(一):环境搭建 Qt PCL学习(二):点云读取与保存 Qt PCL学习(三):点云滤波服务器托管,北京服务器托管,服务器租用服务器托管网 http://www.fwqtg.net相关推荐: 【Langchain Agent研究…