贪心算法 简介
- 局部最优
整体最优
455. 分发饼干
- 思路
- example
- 你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
- 可以全部饼干都分给一个人。
- 每个孩子最多只能给一块饼干，饼干只能整个给。
- g[i]: 第i个人胃口值
- s[j]: 第j个饼干尺寸
- g[i] <= s[j]: 第i个人可以吃第j个饼干。
- 贪心：两个思路：（大饼干分小胃口可能造成“浪费”：小饼干可能没用上）
- 胃口小先分小饼干，或者胃口大后分大饼干 （小孩视角）
- 小饼干给小胃口，或者大饼干给大胃口 （饼干视角）
- 需要对g,s进行排序
- 选定视角 （双指针，单层循环）
- 小孩胃口
- 饼干
-
注意循环顺序（逆序？）的选取 (饼干视角，顺序更好；小孩视角，逆序更好）
- 复杂度. 时间：O(m+n), 空间: O(1)
# 每一步喂一个小孩
# 这里比较麻烦，需要嵌套j-循环。
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
res = 0
j = 0 # j: 饼干index
for i in range(len(g)): # i: 小孩胃口index
while j < len(s) and g[i] > s[j]: # 找到符合胃口的最小饼干
j += 1
# jth饼干 喂 ith小孩
if j < len(s):
res += 1
j += 1
return res
- 稍微不同的写法
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
res = 0
j = 0 # j: 饼干index
i = 0 # i: 小孩胃口index
while i < len(g) and j < len(s):
while j < len(s) and g[i] > s[j]: # 找到符合胃口的最小饼干
j += 1
# jth饼干 喂 ith小孩
if j < len(s):
res += 1
i += 1
j += 1
return res
-
饼干视角 （饼干顺序遍历，饼干小了可以直接跳过）
- 小饼干给胃口小
- 更简洁
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
res = 0
j = 0 # j: 饼干index
i = 0 # i: 小孩胃口index
for j in range(len(s)):
if i < len(g) and s[j] >= g[i]: # jth饼干喂给ith小孩
res += 1
i += 1 # 下一个小孩
# 否则jth饼干没用，直接下一个饼干
return res
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
# Greedy：大饼干给大胃口
s.sort() # 饼干大小排序
g.sort() # 胃口大小排序
i, j = len(g)-1, len(s)-1
res = 0
while j >= 0 and i >= 0:
while i >= 0 and g[i] > s[j]: # 注意越界检查
i -= 1
# now g[i] <= s[j], 饼干j可以给小孩i
if i >= 0: # 确保能找到满足要求的小孩i
res += 1
j -= 1
i -= 1
return res
- 大给大，小给小
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
if len(g) == 0 or len(s) == 0:
return 0
g.sort()
s.sort()
res = 0
j = len(s)-1
i = len(g)-1
while j >=0 and i>= 0:
if s[j] >= g[i]:
res += 1
j -= 1
i -= 1
else:
i -= 1
return res
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
m, n = len(g), len(s)
if m == 0 or n == 0:
return 0
cnt = 0
g.sort()
s.sort()
j, i = n-1, m-1
while j >= 0 and i >= 0:
if s[j] >= g[i]:
cnt += 1
j -= 1
i -= 1
else:
i -= 1
return cnt
376. 摆动序列
- 思路
- example
- 返回 nums 中作为 摆动序列 的 最长子序列的长度 。
- 子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
- 贪心法
- 差分数列：e.g., [+,+,-,+,-,-,+], ans = 5
- 注意差分==0的情况：[0,+,+,-], ans = 2
- 维护两个符号指针 pre, cur
- pre<=0, cur>0: res += 1
- pre>=0, cur<0: res += 1
- 比如nums = [1,2], 可以假设数组为[1,1,2],这样pre初始化为0。
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
n = len(nums)
pre_diff = 0
res = 1
for i in range(1, n):
cur_diff = nums[i] - nums[i-1]
if cur_diff > 0:
cur_diff = 1
elif cur_diff < 0:
cur_diff = -1
# else: cur_diff = 0
if (pre_diff <= 0 and cur_diff > 0) or (pre_diff >= 0 and cur_diff < 0):
res += 1
pre_diff = cur_diff # 不能放在外面, 比如 +,0,+ 情况
return res
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 1
res = 0
pre = 0
for i in range(1, n):
diff = nums[i] - nums[i-1]
if diff == 0:
continue
elif diff > 0:
cur = 1
if cur != pre:
res += 1
pre = cur
else:
cur = -1
if cur != pre:
res += 1
pre = cur
return res + 1
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
n = len(nums)
if n <= 1:
return n
res = 1
pre = 0 # pre sign:
for i in range(1, n):
cur = nums[i] - nums[i-1]
if cur > 0:
if pre <= 0:
res += 1
pre = cur
elif cur < 0:
if pre >= 0:
res += 1
pre = cur
# else: pre does not change
return res
- DP 方法
- dp[i][0]: ith结尾为高峰的摆动子列最长长度
- dp[i][1]: ith结尾为低谷的摆动子列最长长度
- 时间:
, 可以做到
如果优化内部搜索。
class Solution:
def wiggleMaxLength(self, nums: List[int]) -> int:
dp = [[1] * 2 for _ in range(len(nums))]
res = 1
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i][0] = max(dp[j][0], dp[j][1]+1)
res = max(res, dp[i][0])
if nums[i] < nums[j]:
dp[i][1] = max(dp[j][1], dp[j][0]+1)
res = max(res, dp[i][1])
return res
# or return max(dp[-1][0], dp[-1][1])
53. 最大子数组和
- 思路
- example
- 请你找出一个具有最大和的连续子数组（子数组最少包含一个元素), 返回其最大和。
- 滑动窗口, DP, (也可以用贪心来解释）
- 考虑以ith结尾的连续子数组的最大和dp[i]
- 如果dp[i-1] < 0, 则dp[i] = nums[i] (只考虑当前一个数)
- 如果dp[i-1]>=0, 则dp[i] = dp[i-1] + nums[i]
- 或者dp[i] = max(nums[i], dp[i-1] + nums[i])
- 可空间优化
- 注意不能根据nums[i-1]的正负来判断。
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
dp = [0 for _ in range(n)]
dp[0] = nums[0]
res = dp[0]
for i in range(1, n):
dp[i] = max(dp[i-1] + nums[i], nums[i])
res = max(res, dp[i])
return res
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
cur_sum, res = 0, -float('inf')
for i in range(len(nums)):
cur_sum = max(cur_sum + nums[i], nums[i])
res = max(res, cur_sum)
return res
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
dp = [0 for _ in range(n)]
dp[0] = nums[0]
res = dp[0]
for i in range(1, n):
if dp[i-1] < 0:
dp[i] = nums[i]
else:
dp[i] = dp[i-1] + nums[i]
res = max(res, dp[i])
return res
- 分治法
- 分三种情况：左半部结果，右半部结果，“中间结果”：横跨中心的连续子数组的结果
TBA
