day31 算法 贪心算法1

本文主要是介绍day31 算法 贪心算法1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

455 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

思路

尽可能满足大胃的小孩，遍历小孩，让小孩匹配饼干（胃大的不满足跳过下一个）
或者尽可能满足小饼干给小胃，遍历小饼干，让饼干匹配小孩

大饼干匹配
def findContentChildren(g:list,s:list)->int:g.sort()	#小孩s.sort()	#饼干index=len(s)-1result=0for i in range(len(g)-1,-1,-1):if index>=0 and s[index]>=g[i]:result+=1index-=1return result
小饼干匹配
def findContentChildren(g:list,s:list)->int:g.sort()s.sort()index=0for i in range(len(s))：if index<len(g) and s[i]>=g[index]:index+=1return index

376 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

# 贪心
def wiggleMaxLength(nums:list)->int:if len(nums)<=1:return len(nums)result=1curDiff=0preDiff=0for i in range(len(nums)-1):curDiff=nums[i+1]-nums[i]if curDiff*preDiff<=0 and curDiff!=0: #也可以写成 if (preDiff<=0 and curDiff>0) or (preDiff>=0 and curDiff<0):result+=1preDiff=curDiffreturn result 
#动态规划
def wiggleMaxLength(nums:list):if len(nums)<=1:return len(nums)up=down=1for i in range(1,len(nums)):if nums[i]>nums[i-1]:up=down+1elif nums[i]<nums[i-1]:dowm=up+=1return max(up,down)def wiggleMaxLength(nums:list):dp=[]for i in range(len(nums)):dp.append([1,1])for j in range(i):if nums[j]>nums[i]:dp[i][1]=max(dp[i][1],dp[j][0]+1) # 待理解if nums[j]<nums[i]dp[i][0]=max(dp[i][0],dp[j][1]+1)return max(dp[-1][0],dp[-1][0])

53 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

暴力
def maxSubArray(nums:list)->int:result=float('-inf')count=0for i in range(len(nums)):count=0for j in range(i,len(nums)):count+=nums[j]result=max(count,result)return result贪心
def maxSunArray(nums):result=float('-inf')count=0for i in range(len(nums)):count+=nums[i]if count>result:result=countif count<=0: #重置最大子序列count=0return result

这篇关于day31 算法 贪心算法1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---