Open azl397985856 opened 2 years ago
**
贪心
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int numOfChildren = g.length, numOfCookies = s.length;
int count = 0;
for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
while (j < numOfCookies && g[i] > s[j]) {
j++;
}
if (j < numOfCookies) {
count++;
}
}
return count;
}
}
Time O(nlogn) SpaceO(N)
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int numOfChildren = g.length, numOfCookies = s.length;
int count = 0;
for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
while (j < numOfCookies && g[i] > s[j]) {
j++;
}
if (j < numOfCookies) {
count++;
}
}
return count;
}
Complexity Time: O(mlogm + nlogn), sorting uses nlogn, and traversing is n, so total is nlogn Space: O(logm + logn), used for sorting
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
//排序孩子
sort(g.begin(),g.end());
//排序饼干
sort(s.begin(),s.end());
int child = 0,cookie =0;
while(child < g.size() && cookie < s.size()){
if(g[child]<=s[cookie]) child++;
cookie++;
}
return child;
}
};
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort(reverse = True)
s.sort(reverse = True)
i,j = 0,0
gl,sl = len(g),len(s)
res = 0
while i < gl and j < sl:
if s[j] >= g[i]:
j += 1
res += 1
i += 1
return res
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
i = j = res =0
while i < len(g) and j < len(s):
if(g[i] <= s[j]):
res += 1
i += 1
j += 1
else:
j += 1
return res
var findContentChildren = function(g, s) {
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
let count = 0;
for(let i = 0, j = 0; i < g.length && j < s.length; i++, j++) {
while(j < s.length && g[i] > s[j]) {
j++;
}
if(j < s.length) {
count++;
}
}
return count
};
糖果数组和小孩满足数组都从小到大排序,然后遍历每一个小孩,如果当前糖果能够满足孩子,则糖果数量减一,当孩子询问完之后,总糖果数减去剩余糖果数就是发出去的糖果数量,也就是满足的孩子数量
class Solution {
public int findContentChildren(int[] g, int[] s) {
if (g == null || s == null || g.length == 0) {
throw new IllegalArgumentException();
}
Arrays.sort(g);
Arrays.sort(s);
int m = g.length, n = s.length;
if (n == 0) return 0;
int pg = m - 1, ps = n - 1;
while (ps >= 0 && pg >= 0) {
if (s[ps] >= g[pg--]) {
ps--;
}
}
return n - ps - 1;
}
}
func findContentChildren(g []int, s []int) (ans int) { sort.Ints(g) sort.Ints(s) n, m := len(g), len(s) for i, j := 0, 0; i < n && j < m; i++ { for j < m && g[i] > s[j]{ j++ }
if j < m {
ans++
j++
}
}
return
}
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int numOfChildren = g.length, numOfCookies = s.length;
int count = 0;
for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
while (j < numOfCookies && g[i] > s[j]) {
j++;
}
if (j < numOfCookies) {
count++;
}
}
return count;
}
}
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int start = 0, count = 0;
for(int i = 0; i < s.length && start < g.length ; i++){
if(s[i] >= g[start]){
start++;
count++;
}
}
return count;
}
}
class Solution {
public int findContentChildren(int[] g, int[] s) {
if (s.length == 0) {
return 0;
}
Arrays.sort(g);
Arrays.sort(s);
int len = g.length;
int idx = s.length - 1;
int res = 0;
for (int i = len - 1; i >= 0; i--) {
if (idx < 0) {
break;
}
if (g[i] <= s[idx]) {
res++;
idx--;
}
}
return res;
}
}
var findContentChildren = function(g, s) {
g.sort((a, b) => a - b);
s.sort((a, b) => a - b);
const numOfChildren = g.length, numOfCookies = s.length;
let count = 0;
for (let i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
while (j < numOfCookies && g[i] > s[j]) {
j++;
}
if (j < numOfCookies) {
count++;
}
}
return count;
};
class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: g.sort();s.sort l=min(len(g),len(s)) count=j=0 while j < l: if(g[j] <= s[j]): count += 1 j += 1 else: j += 1 return count
C++ Code:
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int gleft =0;
int sleft =0;
int count =0;
while(gleft< g.size() && sleft< s.size())
{
if(g[gleft]<=s[sleft])
{
count++;
gleft++;
sleft++;
}
else
sleft++;
}
return count;
}
};
思路:排序 + 贪心 代码: class Solution(object): def findContentChildren(self, g, s): """ :type g: List[int] :type s: List[int] :rtype: int """ g.sort() s.sort() n, m = len(g), len(s) i = j = count = 0
while i < n and j < m:
while j < m and g[i] > s[j]:
j += 1
if j < m:
count += 1
i += 1
j += 1
return count
复杂度分析: 时间复杂度:O(nlogn) 空间复杂度:O(1)
难度简单443
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 i
,都有一个胃口值 g[i]
,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j
,都有一个尺寸 s[j]
。如果 s[j] >= g[i]
,我们可以将这个饼干 j
分配给孩子 i
,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
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;
int res = 0;
while(i < g.size() && j < s.size()){
// 若满足条件
if(g[i] <= s[j]){
res++;
i++;
j++;
}
else{
// 切换到下一个饼干
j++;
}
}
return res;
}
};
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int result = 0;
int i = 0, j = 0;
for (; i<s.length && j<g.length; i++) {
if (s[i] >= g[j]) {
result++;
j++;
}
}
return result;
}
}
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
if not g or not s:
return 0
g.sort()
s.sort()
res = 0
gi = 0
si = 0
# try the current cookie and child first, if succeed, try next child and next cookie, if not try next cookie
while gi < len(g) and si < len(s):
if g[gi] <= s[si]:
gi += 1
si += 1
res += 1
else:
si += 1
return res
Time Complexity: O(NlogN)
Space Complexity: depend on the sorting algo
455. 分发饼干
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/assign-cookies/
前置知识
暂无
题目描述