貪心算法 簡介
- 局部最優(yōu)
整體最優(yōu)
455. 分發(fā)餅干
- 思路
- example
- 你的目標是盡可能滿足越多數(shù)量的孩子，并輸出這個最大數(shù)值。
- 可以全部餅干都分給一個人涣达。
- 每個孩子最多只能給一塊餅干截亦，餅干只能整個給辨图。
- g[i]: 第i個人胃口值
- s[j]: 第j個餅干尺寸
- g[i] <= s[j]: 第i個人可以吃第j個餅干蒂破。
- 貪心：兩個思路：（大餅干分小胃口可能造成“浪費”：小餅干可能沒用上）
- 胃口小先分小餅干稀颁，或者胃口大后分大餅干 （小孩視角）
- 小餅干給小胃口芬失，或者大餅干給大胃口 （餅干視角）
- 需要對g,s進行排序
- 選定視角 （雙指針，單層循環(huán)）
- 小孩胃口
- 餅干
-
注意循環(huán)順序（逆序峻村？）的選取 (餅干視角麸折，順序更好；小孩視角粘昨，逆序更好）
- 復(fù)雜度. 時間：O(m+n), 空間: O(1)
# 每一步喂一個小孩
# 這里比較麻煩垢啼，需要嵌套j-循環(huán)。
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 中作為 擺動序列 的 最長子序列的長度 吞瞪。
- 子序列 可以通過從原始序列中刪除一些（也可以不刪除）元素來獲得馁启，剩下的元素保持其原始順序。
- 貪心法
- 差分數(shù)列：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], 可以假設(shè)數(shù)組為[1,1,2],這樣pre初始化為0芍秆。
- 復(fù)雜度. 時間：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結(jié)尾為高峰的擺動子列最長長度
- dp[i][1]: ith結(jié)尾為低谷的擺動子列最長長度
- 時間:
, 可以做到
如果優(yōu)化內(nèi)部搜索惯疙。
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. 最大子數(shù)組和
- 思路
- example
- 請你找出一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素), 返回其最大和。
- 滑動窗口, DP, (也可以用貪心來解釋）
- 考慮以ith結(jié)尾的連續(xù)子數(shù)組的最大和dp[i]
- 如果dp[i-1] < 0, 則dp[i] = nums[i] (只考慮當前一個數(shù))
- 如果dp[i-1]>=0, 則dp[i] = dp[i-1] + nums[i]
- 或者dp[i] = max(nums[i], dp[i-1] + nums[i])
- 可空間優(yōu)化
- 注意不能根據(jù)nums[i-1]的正負來判斷妖啥。
- 復(fù)雜度. 時間：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
- 分治法
- 分三種情況：左半部結(jié)果霉颠，右半部結(jié)果，“中間結(jié)果”：橫跨中心的連續(xù)子數(shù)組的結(jié)果
TBA
