贪心算法一般分为如下四步:
局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩。
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
s.sort()
g.sort()
count = 0
sum = 0
for _g in g:
while sum < len(s):
if _g <= s[sum]:
count += 1
s[sum] = -1
break
sum += 1
return count
class Solution:
def findContentChildren(self, g, s):
g.sort() # 将孩子的贪心因子排序
s.sort() # 将饼干的尺寸排序
index = 0
for i in range(len(s)): # 遍历饼干
if index < len(g) and g[index] <= s[i]: # 如果当前孩子的贪心因子小于等于当前饼干尺寸
index += 1 # 满足一个孩子,指向下一个孩子
return index # 返回满足的孩子数目
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
if len(nums) <= 1:
return len(nums)
pre_diff = 0 #前一对元素的差值
cur_diff = 0 #当前一对元素的差值
count = 1 # 记录峰值
for i in range(len(nums) - 1):
cur_diff = nums[i + 1] -nums[i]
if (pre_diff >= 0 and cur_diff < 0) or (pre_diff <= 0 and cur_diff > 0):
count += 1
pre_diff = cur_diff
return count
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 使用额外列表来解决
dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1, len(nums)):
if dp[i - 1] > 0:
dp[i] = dp[i - 1] + nums[i]
else:
dp[i] = nums[i]
return max(dp)
def maxSubArray1(self, nums: List[int]) -> int:
# 使用滑动窗口来解决 关键点就是每次比较的和知否大于当前的数值
cur = nums[0]
temp = 0
for _num in nums:
temp += _num
# 如果临时值大于当前窗口的最大值 重新赋值
if temp > cur:
cur = temp
# 如果不小于0的哇,怎么累加都不会小于刚加的那个值了!
if temp < 0:
temp = 0
return cur