Open azl397985856 opened 1 year ago
class Solution {
public int findContentChildren(int[] g, int[] s) {
// 1. 对两个数组进行排序
Arrays.sort(g);
Arrays.sort(s);
// 2. 记录满足的孩子数量
int child = 0;
int cookie = 0;
// 3. 遍历饼干数组
while (cookie < s.length && child < g.length ) {
if (s[cookie] >= g[child]) {
child++;
}
cookie++;
}
return child;
}
}
贪心,选大饼干先满足胃口大的
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
s.sort(reverse=True)
g.sort(reverse=True)
si,gi=0,0
count=0
#当孩子没有满足且饼干还有剩余
while si<len(s) and gi<len(g):
#如果饼干值大于孩子的胃口值,证明可以满足孩子的胃口
if s[si]>=g[gi]:
count+=1
si+=1#饼干分完
gi+=1#开始满足下一个孩子
return count
复杂度分析
class Solution:
def findContentChildren(self, g, s):
g.sort()
s.sort()
child_index = 0
cookie_index = 0
count = 0
while child_index < len(g) and cookie_index < len(s):
if s[cookie_index] >= g[child_index]:
count += 1
child_index += 1
cookie_index += 1
return count
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
# 将胃口和饼干排序
g.sort()
s.sort()
n = len(g) # 孩子的数量
m = len(s) # 饼干的数量
res = 0 # 记录结果
for i in range(m):
# 从胃口小的开始喂
if res < n and g[res] <= s[i]:
res += 1
return res
#假设胃口 m,n=len(g),len(s)
#时间复杂度为排序的时间O(nlogn+mlogm)+遍历复杂度O(m+n)
#空间复杂度为排序的空间O(logm+logn)
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
#基本思想,用最大的饼干满足胃口最大的孩子
s.sort(reverse=True)
g.sort(reverse=True)
cnt = 0
i,j = 0,0
while i<len(g) and j<len(s):
if g[i]<=s[j]:
cnt+=1
j+=1
i+=1
return cnt
class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int:
s.sort(reverse=True)
g.sort(reverse=True)
cnt = 0
i,j = 0,0
while i<len(g) and j<len(s):
if g[i]<=s[j]:
cnt+=1
j+=1
i+=1
return cnt
455. 分发饼干
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/assign-cookies/
前置知识
暂无
题目描述