前往
大廳
主題

LeetCode - 455. Assign Cookies 解題心得

Not In My Back Yard | 2020-10-26 00:00:05 | 巴幣 0 | 人氣 312

題目連結:


題目意譯:
假設你是位超棒的父母,而你想要給你的孩子們一些餅乾。但是,對於每個孩子你最多只應給他們一塊餅乾。

每個孩子 i 有個貪心因數 g[i],其代表可使他們滿足的餅乾之最小的大小。且每塊餅乾 j 有大小 s[j]。如果 s[j] ≧ g[i],則我們可以將餅乾 j 分配給小孩 i ,且小孩將會心滿意足。你的目標是最大化感到滿足的小孩之數量,並且輸出該數量。

限制:
1 ≦ g.length ≦ 3 × 10 ^ 4
0 ≦ s.length ≦ 3 × 10 ^ 4
1 ≦ g[i] 、 s[j] ≦ 2 ^ 31 - 1


範例測資:
範例 1:
輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋: 你有 3 個小孩還有 2 塊餅乾。三個小孩的貪心因數分別為 1 、 2 、 3 。
而且雖然你有 2 塊餅乾,但因為它們的大小皆為 1 ,因此你只能滿足貪心因數為 1 的那一個小孩。
所以你需要輸出 1 。

範例 2:
輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋: 你有 2 個小孩還有 3 塊餅乾。兩個小孩的貪心因數分別為 1 、 2。
你有 3 塊餅乾,且它們的大小足以滿足所有小孩。
因此,你需要輸出 2 。


解題思維:
可以看到盡量地將較大的餅乾分配給貪心因數較大的小孩,可以使滿足的小孩數量最大化。因為如果將大餅乾給了貪心因數較低的小孩,則原本可以得到該餅乾的那個貪心因數較大的小孩很有可能就拿不到餅乾了。

因此我們將所有餅乾 s 按照大小由大到小排序、所有小孩依照貪心因數 g 大小由大到小排序。接著用兩個指標 Pcookie 、 Pchild 分別指向最大的餅乾和貪心因數最大的小孩。

初始化一變數 C = 0 ,代表滿足的小孩個數。

重複以下步驟直到 Pcookie(或是 Pchild)已經掃過所有的餅乾(或小孩):
判斷 s[Pcookie](目前的小孩)是否大於或等於 g[Pchild](目前的餅乾)。如果是,則代表該餅乾應分配給該名小孩,因此 C 加 1 並將 Pcookie 往下一個較小的餅乾移動、Pchile 往下一個貪心因數較小小孩移動;反之,Pchild 還是要往下一個貪心因數較小的小孩移動(當前的小孩絕對無法拿到餅乾,因為較大的餅乾都無法滿足他)。

最後得出的 C 值即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作