資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究用 C++ 分配 Cookie
假設我們嘗試給孩子們分發一些餅乾。但是，我們應該給每個孩子不超過一塊餅乾。現在，每個孩子 i 都有一個貪婪度 gi，它是孩子會滿足的餅乾的最小大小；每個餅乾 j 有一個大小 sj。當 sj >= gi 時，我們可以把餅乾 j 分配給孩子 i，孩子 i 就會滿足。我們的目標是最大化滿足孩子的數量，並輸出最大數量。
因此，如果輸入類似於 [1,2]，[1,2,3]，則輸出將是 2，有 2 個孩子和 3 塊餅乾。2 個孩子的貪婪度為 1、2。現在我們有 3 塊餅乾，並且它們的大小足夠滿足所有孩子，因此輸出為 2。
為解決這個問題，我們將按照以下步驟操作 -
對陣列 g 進行排序
對陣列 s 進行排序
i := 0，j = 0
只要 (i < g 的大小且 j < s 的大小) 執行 -
如果 g[i] <= s[j]，則 -
(i 加 1)
(j 加 1)
返回 i
示例
為了更好地理解，我們來看一下以下實現 -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0, j = 0;
while (i < g.size() && j < s.size()) {
if (g[i] <= s[j])
i++;
j++;
}
return i;
}
};
main(){
Solution ob;
vector<int> v = {1,2}, v1 = {1,2,3};
cout << (ob.findContentChildren(v, v1));
}輸入
{1,2}, {1,2,3}輸出
2
更新於：2020 年 6 月 10 日
635 次瀏覽
廣告