Go語(yǔ)言題解LeetCode455分發(fā)餅干示例詳解

更新時(shí)間：2022年12月30日 11:11:46 作者：劉09k11

這篇文章主要為大家介紹了Go語(yǔ)言題解LeetCode455分發(fā)餅干示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目描述

原題鏈接 :

455. 分發(fā)餅干 - 力扣（LeetCode） (leetcode-cn.com)

假設(shè)你是一位很棒的家長(zhǎng)，想要給你的孩子們一些小餅干。但是，每個(gè)孩子最多只能給一塊餅干。

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

示例 1:

輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋: 
你有三個(gè)孩子和兩塊小餅干，3個(gè)孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應(yīng)該輸出1。

示例 2:

輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋: 
你有兩個(gè)孩子和三塊小餅干，2個(gè)孩子的胃口值分別是1,2。
你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。
所以你應(yīng)該輸出2.

提示：

1 <= g.length <= 3 * 10^4

0 <= s.length <= 3 * 10^4

1 <= g[i], s[j] <= 2^31 - 1

思路分析

其實(shí)這道題真的很像田忌賽馬，我們這么想，我們要打敗一堆小朋友，其中有上等小朋友，中等小朋友，下等小朋友。

而我們有上等餅干，中等餅干，下等餅干，小朋友只有吃了足夠大的餅干才會(huì)被打敗，我們?cè)撛趺醋觯?/p>

答案一定是要，要用最上等的餅干打敗最厲害的小朋友，不然就是一種浪費(fèi)（如果你用上等餅干打敗下等小朋友，那么誰(shuí)來(lái)打敗上等小朋友？）

其實(shí)這也是貪心思想，想法有了，就剩下實(shí)現(xiàn)代碼了，代碼如下

AC 代碼

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(s.begin(),s.end(),greater<int>());
        sort(g.begin(),g.end(),greater<int>());
        int i=0,j=0,ans=0;
        while(i<s.size()&&j<g.size())
        {
            if(s[i]>=g[j])
            {
                ++ans;++i;++j;
            }
            else
            ++j;
        }
        return ans;
    }
};

分發(fā)餅干貪心算法

解題思路

先對(duì)兩個(gè)數(shù)組排序

從后開始遍歷g，使得大餅干給胃口大的孩子

局部最優(yōu)就是胃口大的孩子匹配大的餅干

代碼

class Solution {
    public int findContentChildren(int[] g, int[] s) {//s:餅干
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int start = s.length - 1;//餅干數(shù)量
        for(int index = g.length - 1; index >= 0; index--){
            if(start >= 0 && g[index] <= s[start]){
                count++;
                start--;
            }
        }
        return count;
    }
}

以上就是Go語(yǔ)言題解LeetCode455分發(fā)餅干示例詳解的詳細(xì)內(nèi)容，更多關(guān)于Go題解分發(fā)餅干的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: