当前位置:网站首页>【LeetCode-455】方法饼干
【LeetCode-455】方法饼干
2022-08-11 05:30:00 【Ring*】
6.10 方法饼干【455】
6.10.1 题目描述
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >=g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
6.10.2 方法一:排序+贪心
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;
}
}
复杂度分析
6.10.3 my answer—排序
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int n = g.length + s.length;
int p1=0,p2=0;
int sum =0;
for(int i = 0;i<n;i++){
if(p1==g.length || p2 == s.length)break;
if(s[p2]>=g[p1]){
// 第p2+1块饼干满足第p1+1个孩子
sum++;
p1++;
p2++;
}else{
// 不满足该孩子则后移一位选取饼干大一点的
p2++;
}
}
return sum;
}
}
边栏推荐
猜你喜欢
随机推荐
使用adb命令管理应用
精彩联动 | OpenMLDB Pulsar Connector原理和实操
经纬度求距离
Day 80
mysql basic summary
【LeetCode-74】搜索二维矩阵
C语言预处理
一文看懂注解与反射
微信小程序启动页的实现
Simple mine sweeping in C language (with source code)
Day 70
Tinker接入全流程---配置篇
mk文件介绍
Visual studio2019 configuration uses pthread
编译异常解决
本地服务配置内网穿透实现微信公众号整合
Fourth Paradigm OpenMLDB optimization innovation paper was accepted by VLDB, the top international database association
Day 69
Day 76
C语言-6月12日-字符替换问题,将一个‘ ’替换为2个‘#’