題目:

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

給定兩個陣列,一個表示各餅乾的分量(s),一個表示各孩童的食量(g)
一個孩童最多只能拿一個餅乾,算出這些餅乾最多能餵飽幾個孩童

這題我採用雙指標的作法

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g=sorted(g)
        s=sorted(s)
        
        i=0
        j=0
        while i<len(g) and j<len(s):
            if g[i]<=s[j]:
                i=i+1
            j=j+1
                
        return i

先將兩個陣列進行排序
將份量小的餅乾優先和食量小的孩童配對
才能達成分配餅乾的最大效益

設好兩個指標(i,j),i在孩童食量陣列,j在餅乾份量陣列
若當前的餅乾能餵飽當前的孩童(g[i]<=s[j])
i,j都+1去找下一個孩童跟下一個餅乾配對

反之若餅乾餵不飽孩童
j+1往下去找下一個更大的餅乾好餵飽這個孩童

如此持續到孩童都被餵飽或餅乾都被用完
此時的i剛好表示餵飽的孩童的數量
最後執行時間166ms(faster than 96.87%)

今天也先更一題就好

那我們下題見