LeetCode #455 Assign Cookies 分配餅乾

Klook.com
文章觀看次數: 84

英文原文如下

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.

中文翻譯

假設你是一個很棒的家長並且想要給你的小孩一些餅乾。但，每個小孩最多只能給一塊餅乾。

每個孩子 i 有一個貪婪因子 g[i]，表示孩子滿足的最小餅乾尺寸；而每塊餅乾 j 有一個尺寸 s[j]。如果 s[j] >= g[i]，我們可以把餅乾 j 分配給孩子 i，這樣孩子 i 就會滿足。你的目標是滿足最多孩子並輸出其數量。

範例及題目限制

解題思路

在這一題中，我們就是要滿足那些貪婪的小孩(!?)

首先，我們會先將尺寸以及小孩的貪婪因子各自排序

再來，我們會針對餅乾尺寸去做一個foreach (因為餅乾分完就分完了，故以它為底去迴圈)

並用一個 i 表示目前輪到的小孩的索引

要是迴圈中餅乾的尺寸大於目前小孩的貪婪因子，則會 i+=1 (當前這位滿足了)

除了餅乾全部分完的狀況外，還需另外判斷每個小孩都拿完餅乾的狀態 (i==g.Length)

C# 解決方案

方案1

public class Solution {
    public int FindContentChildren(int[] g, int[] s) {
        Array.Sort(g);
        Array.Sort(s);

        int i=0;
        foreach(var sItem in s){
            if(sItem>=g[i]){
                i+=1;
            }
            if(i==g.Length){
                return i;
            }
        }
        return i;
    }
}

想要寫成雙指標的寫法也是可以的

public class Solution {
    public int FindContentChildren(int[] g, int[] s) {
        Array.Sort(g);
        Array.Sort(s);
        
        int i = 0;  
        int j = 0;  

        while (i < g.Length && j < s.Length) {
            if (s[j] >= g[i]) {
                i++;
            }
            j++;
        }

        return i;
    }
}

Java解決方案

方案1

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int i=0;
        for(int sItem : s){
            if(sItem>=g[i]){
                i+=1;
            }
            if(i==g.length){
                return i;
            }
        }
        return i;
    }
}

Python3 解決方案

方案1

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()

        i=0

        for sItem in s:
            if(sItem>=g[i]):
                i+=1
            
            if(i==len(g)):
                return i
        
        return i

結論

還管他們滿不滿意!! 直接大家都拿一樣大小的餅乾不就好了嗎 🍪🍪🍪

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡收藏文章或幫我點個廣告，那都是對我的支持

⭐大力徵求合作邀約或是友站夥伴 ➡ 附上 2023網站回顧

題目連結 : Assign Cookies – LeetCode

一些隨機的LeetCode文章

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *