題目描述

假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。

對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j，都有一個尺寸 s[j] 。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數(shù)量的孩子，并輸出這個最大數(shù)值。【題目來源:力扣(leetcode)】

貪心算法

貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以前的過程不會影響以后的狀態(tài)，只與當前狀態(tài)有關。簡單地說，貪心算法就是通過找到局部最優(yōu)解的規(guī)律從而推出整個完整的規(guī)律，以從局部最優(yōu)達到整體最優(yōu)。

對于該題

要使餅干的效率達到最大，我們需要盡可能的滿足使當前存在最大的餅干分給胃口最大的小朋友，直到餅干全部分發(fā)或者現(xiàn)有的餅干大小無法滿足剩余的小朋友的胃口。這就達到了整體最優(yōu)。

代碼

class Solution:

? ? def findContentChildren(self, g: List[int], s: List[int]) -> int:

? ? ? ? count = 0

? ? ? ? g.sort(reverse=True)

? ? ? ? s.sort(reverse=True)

? ? ? ? lenght = min(len(g),len(s))

? ? ? ? while len(s) !=0 and len(g) != 0:

? ? ? ? ? ? if s[0] >= g[0]:

? ? ? ? ? ? ? ? s.pop(0)

? ? ? ? ? ? ? ? g.pop(0)

? ? ? ? ? ? ? ? count += 1

? ? ? ? ? ? elif s[0] < g[0]:

? ? ? ? ? ? ? ? g.pop(0)

? ? ? ? return count