沈無奇 ·簡單難度貪心算法實(shí)戰(zhàn)
在 leetcode 上貪心算法相關(guān)的編程題比較多，本節(jié)以及接下來的一節(jié)都會(huì)選擇使用 leetcode 習(xí)題來幫助我們鞏固和實(shí)戰(zhàn)貪心算法。本節(jié)會(huì)選擇一些標(biāo)簽為簡單的題目，而在下一節(jié)中會(huì)選擇標(biāo)簽為中級(jí)和困難的編程題。
1. 分發(fā)餅干
這是 leetcode 上算法部分第 455 題，為簡單編程題。題目描述如下：
你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個(gè)孩子最多只能給一塊餅干。對每個(gè)孩子 ，都有一個(gè)胃口值 $g_i $，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 ，都有一個(gè)尺寸 。如果 $s_j >= g_i $，我們可以將這個(gè)餅干 分配給孩子 ，這個(gè)孩子會(huì)得到滿足。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個(gè)最大數(shù)值。
注意：你可以假設(shè)胃口值為正。一個(gè)小朋友最多只能擁有一塊餅干。
示例1：
輸入: [1,2,3], [1,1]
輸出: 1
解釋: 你有三個(gè)孩子和兩塊小餅干，3個(gè)孩子的胃口值分別是：1,2,3。雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。所以你應(yīng)該輸出1。
示例2：
輸入: [1,2], [1,2,3]
輸出: 2
解釋: 你有兩個(gè)孩子和三塊小餅干，2個(gè)孩子的胃口值分別是1,2。你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。所以你應(yīng)該輸出2。
這里的解題思路也是非常清晰的：**同樣也是貪心的思路，我們將孩子和餅干的胃口分別從小到大進(jìn)行排序，從最小的餅干和第一個(gè)孩子開始。餅干指針一直向后執(zhí)行，找到一個(gè)餅干滿足孩子胃口，則孩子指針向后移動(dòng)一位，同時(shí)滿足的孩子數(shù)加1，如此執(zhí)行直到孩子或者餅干的指針走完即可。**這樣的一個(gè)盡可能最小餅干滿足最小胃口的策略其實(shí)就是貪心思路。
按照上面的思路，題解第一步就是對孩子的胃口和餅干分別進(jìn)行排序，從小達(dá)到：
g.sort()
s.sort()
接下來就是實(shí)現(xiàn)餅干滿足小孩，我們分別給小孩的胃口數(shù)組、餅干數(shù)組設(shè)置初始化指針，然后初始化一個(gè)滿足小孩數(shù)的變量：
id1, id2, count = 0, 0, 0
接下來就是遍歷餅干數(shù)組和移動(dòng)小孩胃口數(shù)組指針。如果餅干尺寸大于等于當(dāng)前小孩胃口，則滿足小孩，count 數(shù)加1，同時(shí)餅干和小孩胃口數(shù)組指針分別后移一位；如果餅干尺寸小于小孩胃口，則只有餅干指針后移一位。如此，直到最后餅干或者小孩的指針指到最后循環(huán)結(jié)束：
# 循環(huán)，當(dāng)其中一個(gè)列表掃描完畢后結(jié)束
while id1 < len(g) and id2 < len(s):
if g[id1] <= s[id2]:
# 滿足孩子，孩子指針+1，同時(shí)結(jié)果+1
id1 += 1
count += 1
# 餅干指針+1，無論是滿足和不滿足孩子，都要往后走一位
id2 += 1
最后我們完整給出實(shí)現(xiàn)上述題解的方法，如下：
def findContentChildren(g, s):
# 使用貪心策略，先排序，最小胃口孩子對應(yīng)最小能滿足的餅干
g.sort()
s.sort()
id1, id2, count = 0, 0, 0
while id1 < len(g) and id2 < len(s):
# 一次循環(huán)，當(dāng)其中一個(gè)列表掃描完畢后結(jié)束
if g[id1] <= s[id2]:
# 滿足孩子，孩子指針+1，同時(shí)結(jié)果+1
id1 += 1
count += 1
# 餅干指針+1，無論是滿足和不滿足孩子，都要往后走一位
id2 += 1
return count
2. 檸檬水找零
這是 leetcode 上算法部分第 860 題，為簡單編程題。題目描述如下：
在檸檬水?dāng)偵?，每一杯檸檬水的售價(jià)為 5 美元。顧客排隊(duì)購買你的產(chǎn)品，（按賬單 bills 支付的順序）一次購買一杯。每位顧客只買一杯檸檬水，然后向你付 5 美元、10 美元或 20 美元。你必須給每個(gè)顧客正確找零，也就是說凈交易是每位顧客向你支付 5 美元。
注意：一開始你手頭沒有任何零錢。如果你能給每位顧客正確找零，返回 true ，否則返回 false 。
示例1：
輸入：[5,5,5,10,20]
輸出：true
解釋：
前 3 位顧客那里，我們按順序收取 3 張 5 美元的鈔票。
第 4 位顧客那里，我們收取一張 10 美元的鈔票，并返還 5 美元。
第 5 位顧客那里，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票。
由于所有客戶都得到了正確的找零，所以我們輸出 true。
示例2：
輸入：[5,5,10]
輸出：true
示例3：
輸入：[10,10]
輸出：false
示例4：
輸入：[5,5,10,10,20]
輸出：false
解釋：前 2 位顧客那里，我們按順序收取 2 張 5 美元的鈔票。對于接下來的 2 位顧客，我們收取一張 10 美元的鈔票，然后返還 5 美元。對于最后一位顧客，我們無法退回 15 美元，因?yàn)槲覀儸F(xiàn)在只有兩張 10 美元的鈔票。由于不是每位顧客都得到了正確的找零，所以答案是 false。
看到這題，沒啥好說的。首先依次掃描收入的鈔，此時(shí)會(huì)有如下三種情況：
- 如果收到的是 5 元，直接放入 5 元列表中；
- 如果收到的是 10 元，看看 5 元列表是否還有剩余；
- 如果沒有 5 元?jiǎng)t無法找零，返回 False；
- 否則找零 5 元，減少一個(gè) 5 元列表元素，增加1個(gè)10元列表的元素；
- 對于收到的是 20 元，必須先找 10 元，然后剩下的再找 5 元；
首先定義存放5元和10元的數(shù)組，20元不會(huì)用于找零，所以不用記錄：
remain_5 = []
remain_10 = []
根據(jù)上面思路，我們可以簡單寫以下收到5元和10元的邏輯：
for i in range(len(bills)):
# 假設(shè)遍歷第i個(gè)鈔票
if bills[i] == 5:
# 5元錢，直接收入
remain_5.append(1)
elif bills[i] == 10:
# 對于10元找零，只需要找零5元即可
if not remain_5:
# 沒有5元，直接返回False
return False
# 減去一個(gè)5元
remain_5.pop()
# 加上一個(gè)10元
remain_10.append(1)
else:
# 對于20元的處理
pass
對于20元的處理，我們只需要定義一個(gè)找零數(shù)：res = 15。首先找零10元，如果有10元，則減去一個(gè)10元，同時(shí)剩余找零也要減去10：
remain = 15
# 如果有10元，先用一個(gè)10元
if len(remain_10) >= 1:
remain -= 10
remain_10.pop()
接下來找5元，每找零一個(gè)5元，則5元數(shù)需要減一，同時(shí)剩余找零數(shù)也要減去5,，直到 remain_5 數(shù)組為空或者 remain<=0 結(jié)束：
while len(remain_5) > 0 and remain > 0:
remain -= 5
remain_5.pop()
如果能找零，則 remain 最后應(yīng)該為0，那么我們可以判斷，如果剩余的 remain > 0，則表明最后無法找零；否則找零成功
if remain > 0:
return False
在 20 元找零那里之所以能用貪心思想是因?yàn)?strong>找零的 15 元減去 10 元正好等于 5 元，如果我先找 5 元?jiǎng)t會(huì)出現(xiàn)這樣的情況：**剩余 2 個(gè) 5 元和 1 個(gè) 10 元，如果先找 5 元，則有 2 個(gè) 5 元，最后的 10 元無法完成找零。**最后整個(gè)處理柃檬水找零問題的 Python 方法如下：
def lemonadeChange(bills):
remain_5 = []
remain_10 = []
for i in range(len(bills)):
if bills[i] == 5:
# 5元錢，直接收入
remain_5.append(1)
elif bills[i] == 10:
# 10元找零5元
if not remain_5:
return False
remain_5.pop()
remain_10.append(1)
else:
# 對于20元錢找零15元，貪心策略，盡可能找零10元，10元不夠在找5元
remain = 15
# 如果有10元，先用一個(gè)10元
if len(remain_10) >= 1:
remain -= 10
remain_10.pop()
# 這里存在2種情況，上面找了10元，就剩下5元要找；沒有10元，就會(huì)一直找5元
while len(remain_5) > 0 and remain > 0:
remain -= 5
remain_5.pop()
# 如果最后還沒找完，且5元數(shù)組為空，則無法完成找零，直接返回False
if remain > 0:
return False
# 走到這一步，可以返回True
return True
3. 兩地調(diào)度
這是 leetcode 上算法部分第 1029 題，為簡單編程題。題目描述如下：
公司計(jì)劃面試 2N 人。第 i 人飛往 A 市的費(fèi)用為 costs[i][0]，飛往 B 市的費(fèi)用為 costs[i][1]。返回將每個(gè)人都飛到某座城市的最低費(fèi)用，要求每個(gè)城市都有 N 人抵達(dá)。
示例：
輸入：[[10,20],[30,200],[400,50],[30,20]]
輸出：110
解釋：
第一個(gè)人去 A 市，費(fèi)用為 10。
第二個(gè)人去 A 市，費(fèi)用為 30。
第三個(gè)人去 B 市，費(fèi)用為 50。
第四個(gè)人去 B 市，費(fèi)用為 20。
最低總費(fèi)用為 10 + 30 + 50 + 20 = 110，每個(gè)城市都有一半的人在面試。
Tips：
1 <= costs.length <= 100；costs.length為偶數(shù)；1 <= costs[i][0], costs[i][1] <= 1000。
這道題需要認(rèn)真思考下，對于貪心的算法而言我們要首先確定貪心的值。
我們的值并不是拿去城市的費(fèi)用值來做貪心，這里要非常注意，因?yàn)槊總€(gè)人必須兩個(gè)城市中選擇去一個(gè)，如果去了 A 市就不能去 B 市；反之，去了 B 市就不能去 A 市。
可以很容易想到我們貪心的值應(yīng)該是候選人去 A 市和 B 市花費(fèi)的差值，接著將列表元素按照相應(yīng)的差值從小到大進(jìn)行排列，前 N 個(gè)人去 A 市，后 N 個(gè)人去 B 市，這便是這道題最精妙的解題思路，是不是很有意思？有了上面的貪心過程，那么 Python 實(shí)現(xiàn)便呼之欲出：
def twoCitySchedCost(self, costs):
min_costs = 0
N = len(costs) // 2
# 調(diào)用python的排序函數(shù)，排序值為相應(yīng)差值
costs.sort(key=lambda x:x[0]-x[1])
# 排序后的前半部分人去A市
min_costs += sum([costs[i][0] for i in range(N)])
# 后半部分人去B市
min_costs += sum(costs[i][1] for i in range(N, 2 * N))
return min_costs
可以看到，這里算法的時(shí)間復(fù)雜度為 ，在問題規(guī)模 N 非常大時(shí)，主要的時(shí)間消耗在于快排方法 (sort) 那里。
4. 小結(jié)
本小節(jié)主要是進(jìn)行貪心算法實(shí)戰(zhàn)，在 leetcode 上選擇 3 道簡單題進(jìn)行實(shí)戰(zhàn)訓(xùn)練。這里的題目比較基礎(chǔ)，貪心算法運(yùn)用并不復(fù)雜。接下來我們將挑戰(zhàn)中級(jí)和困難題，進(jìn)一步應(yīng)用貪心算法解決題目。
2025 imooc.com All Rights Reserved |