貪心算法
貪心選擇：
通過(guò)一系列的局部最優(yōu)解達(dá)到整體最優(yōu)解。前提：
必須證明貪心選擇可以達(dá)到最優(yōu)解：先證明整體最優(yōu)解是從貪心選擇開(kāi)始的，然后做了貪心選擇后問(wèn)題可以簡(jiǎn)化成子問(wèn)題，最后用數(shù)學(xué)歸納法證明通過(guò)每一步的貪心選擇最終可以得到一個(gè)最優(yōu)解。做法：
從頂向下，迭代把問(wèn)題簡(jiǎn)化成小規(guī)模的子問(wèn)題。
從問(wèn)題的某一個(gè)初始解出發(fā)一步一步地進(jìn)行，根據(jù)某個(gè)優(yōu)化測(cè)度，每一步都要確保能獲得局部最優(yōu)解。每一步只考慮一個(gè)數(shù)據(jù)，他的選取應(yīng)該滿足局部?jī)?yōu)化的條件。若下一個(gè)數(shù)據(jù)和部分最優(yōu)解連在一起不再是可行解時(shí)，就不把該數(shù)據(jù)添加到部分解中，直到把所有數(shù)據(jù)枚舉完，或者不能再添加算法停止-
過(guò)程
- 建立數(shù)學(xué)模型來(lái)描述問(wèn)題；
- 把求解的問(wèn)題分成若干個(gè)子問(wèn)題；
- 對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解；
- 把子問(wèn)題的解局部最優(yōu)解合成原來(lái)解問(wèn)題的一個(gè)解。
最優(yōu)子結(jié)構(gòu)：
當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。-
貪心/動(dòng)態(tài)規(guī)劃
-
貪心算法的每一次操作都對(duì)結(jié)果產(chǎn)生直接影響，
動(dòng)態(tài)規(guī)劃則不是。 -
貪心算法對(duì)每個(gè)子問(wèn)題的解決方案都做出選擇，不能回退；
動(dòng)態(tài)規(guī)劃則會(huì)根據(jù)以前的選擇結(jié)果對(duì)當(dāng)前進(jìn)行選擇，有回退功能。 -
貪心一般是一維問(wèn)題，
動(dòng)態(tài)規(guī)劃主要運(yùn)用于二維或三維問(wèn)題。
-
貪心算法的每一次操作都對(duì)結(jié)果產(chǎn)生直接影響，
1221. 分割平衡字符串
在一個(gè)「平衡字符串」中，'L' 和 'R' 字符的數(shù)量是相同的。
給出一個(gè)平衡字符串 s，請(qǐng)你將它分割成盡可能多的平衡字符串。
返回可以通過(guò)分割得到的平衡字符串的最大數(shù)量。
1 <= s.length <= 1000
s[i] = 'L' 或 'R'
輸入：s = "RLRRLLRLRL"
輸出：4
解釋：s 可以分割為 "RL", "RRLL", "RL", "RL", 每個(gè)子字符串中都包含相同數(shù)量的 'L' 和 'R'。
- 匹配
class Solution:
def balancedStringSplit(self, s: str) -> int:
balance = 0
res = 0
for i in s:
if i == 'R':
balance += 1
elif i == 'L':
balance -= 1
if balance == 0:
res += 1
return res
- 棧
初始入棧一個(gè)數(shù)據(jù)，后續(xù)如果發(fā)現(xiàn)與棧頂數(shù)據(jù)一致，則入棧，不一致則出棧
直接判斷棧中數(shù)據(jù)是否為0，為0則說(shuō)明成功匹配一個(gè)數(shù)據(jù)，此時(shí)平衡字符串?dāng)?shù)量+1
class Solution:
def balancedStringSplit(self, s: str) -> int:
# 通過(guò)隊(duì)列操作，當(dāng)棧中數(shù)量減到0時(shí) + 1
result = 0
stack = []
for x in s:
if len(stack) > 0:
stack.append(x) if stack[0] == x else stack.pop()
result += 1 if len(stack) == 0 else 0
else:
stack.append(x)
return result
455. 分發(fā)餅干
假設(shè)你是一位很棒的家長(zhǎng)，想要給你的孩子們一些小餅干。但是，每個(gè)孩子最多只能給一塊餅干。對(duì)每個(gè)孩子 i ，都有一個(gè)胃口值 gi ，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j ，都有一個(gè)尺寸 sj 。如果 sj >= gi ，我們可以將這個(gè)餅干 j 分配給孩子 i ，這個(gè)孩子會(huì)得到滿足。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個(gè)最大數(shù)值。
注意：
你可以假設(shè)胃口值為正。
一個(gè)小朋友最多只能擁有一塊餅干。
輸入: [1,2,3], [1,1]
輸出: 1
解釋:
你有三個(gè)孩子和兩塊小餅干，3個(gè)孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應(yīng)該輸出1。
排序然后逐個(gè)比較，先讓胃口小的滿足
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
# 胃口g list g[i] > 0
# 尺寸s list
# 一人一塊
# 輸出最多能滿足多少
g.sort()
s.sort()
res = 0
for gg in g:
for ss in s:
if gg <= ss:
res += 1
s.remove(ss)
break
return res
用指針優(yōu)化, 降低復(fù)雜度
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
# 胃口g list g[i] > 0
# 尺寸s list
# 一人一塊
# 輸出最多能滿足多少
g.sort()
s.sort()
gi = 0
si = 0
while gi < len(g) and si < len(s):
if g[gi] <= s[si]:
gi += 1
si += 1
else:
si += 1
return gi
# gi實(shí)際和被滿足的人數(shù)一樣
435. 無(wú)重疊區(qū)間
給定一個(gè)區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。
注意:
可以認(rèn)為區(qū)間的終點(diǎn)總是大于它的起點(diǎn)。
區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒(méi)有相互重疊。
輸入: [ [1,2], [2,3], [3,4], [1,3] ]
輸出: 1
解釋: 移除 [1,3] 后，剩下的區(qū)間沒(méi)有重疊。
轉(zhuǎn)換思路，從給出區(qū)間集合中最多能選幾個(gè)不重疊的，剩下的就是需要去掉的
- 按結(jié)束時(shí)間升序排序
- 遍歷判斷當(dāng)前區(qū)間是否滿足開(kāi)始的時(shí)間>=上次結(jié)束時(shí)間
- 每次選擇結(jié)束時(shí)間最早的
- 更新結(jié)束時(shí)間
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
intervals = sorted(intervals, key=lambda x:x[1])
# intervals.sort(key=self.takeSecond)
picked = 0 # 選出的不重疊區(qū)間
end = - float('inf') # 結(jié)束初始值負(fù)無(wú)窮
for i in intervals:
if i[0] >= end:
picked += 1
end = i[1]
return len(interval) - picked
先升序排序是關(guān)鍵點(diǎn)！
321. 拼接最大數(shù)
Reference
[1] ?？拓澬乃惴?/a>
[2]詳解貪心算法（Python實(shí)現(xiàn)貪心算法典型例題）
[3] leetcode 貪心算法
