本文主要是介绍代码随想录算法训练营第三十四天 | 理论基础、455.分发饼干、376、摆动序列、53.最大子序和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
理论基础
455.分发饼干
思路
代码
376.摆动序列
思路
代码
53.最大子序和
思路
代码
理论基础
代码随想录
455.分发饼干
代码随想录
思路
可以是大饼干优先满足大胃口,也可以是小饼干优先满足小胃口。
代码
class Solution:def findContentChildren(self, g, s):g.sort() # 将孩子的贪心因子排序s.sort() # 将饼干的尺寸排序index = 0for i in range(len(s)): # 遍历饼干if index < len(g) and g[index] <= s[i]: # 如果当前孩子的贪心因子小于等于当前饼干尺寸index += 1 # 满足一个孩子,指向下一个孩子return index # 返回满足的孩子数目
376.摆动序列
代码随想录
思路
真就像Carl哥说的那样:
贪心算法其实就是没有什么规律可言,所以大家了解贪心算法 就了解它没有规律的本质就够了。
不用花心思去研究其规律, 没有思路就立刻看题解。
基本贪心的题目 有两个极端,要不就是特简单,要不就是死活想不出来。
我连用什么方式来判断这个是正,下个是负,或者这个是负,下个是正都不会。。。(每日崩溃1/1),其实就是用两个变量来存储。计算波峰的次数,具体可以看链接。
代码
class Solution:def wiggleMaxLength(self, nums):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.最大子序和
代码随想录
思路
贪心真的很逆天,一点思路都没有,暴力法最后十个用例过不了的。。。Carl点拨了一下我觉得很有道理,一个负数加一个正数肯定比0加一个正数要小,所以就是从头开始遍历起,不断计算累计和,如果累计和是负数,前面那一整段就不要了,直接0加后面的数,从后面开始重新算。
代码
class Solution:def maxSubArray(self, nums):result = float('-inf') # 初始化结果为负无穷大count = 0for i in range(len(nums)):count += nums[i]if count > result: # 取区间累计的最大值(相当于不断确定最大子序终止位置)result = countif count <= 0: # 相当于重置最大子序起始位置,因为遇到负数一定是拉低总和count = 0return result
这篇关于代码随想录算法训练营第三十四天 | 理论基础、455.分发饼干、376、摆动序列、53.最大子序和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!