文档章节

【LeetCode】455. Assign Cookies (java实现)

BookShu
 BookShu
发布于 2016/11/23 09:29
字数 585
阅读 116
收藏 0

原题链接

https://leetcode.com/problems/assign-cookies/

原题

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note: You may assume the greed factor is always positive. You cannot assign more than one cookie to one child.

Example 1:

Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

题目要求

题目叫“分配饼干”,给定两个数组,分别表示每个小孩期望的饼干尺寸,和每个饼干实际的尺寸。将饼干分配给这些小孩,但分配的饼干尺寸必须不小于小孩期望的饼干尺寸。求出这些饼干最多可以满足几个小孩。

解法

解法:题目比较简单清晰,既然是饼干尺寸不小于期望尺寸,那么我们首先将两个数组先排序。遍历期望尺寸的数组和饼干尺寸的数组,如果饼干尺寸符合则两个数组都向前进一,表示有一个饼干满足了一个小孩;如果饼干尺寸不符合,则饼干数组向前进一,尝试下一个饼干。

public int findContentChildren(int[] g, int[] s) {
    int ret = 0;
    
    Arrays.sort(g);
    Arrays.sort(s);
    
    int i = 0, j = 0;
    while (i < g.length && j < s.length) {
        if (g[i] <= s[j]) {
            ret++;
            i++;
            j++;
        }else if (g[i] > s[j]) {
            j++;
        }
    }
    
    return ret;
}

测试用例:

public static void main(String[] args) {
    Solution so = new Solution();
    {
        int []g = {1, 2, 3};
        int []s = {1, 1};
        assert(so.findContentChildren(g, s) == 1);
    }
    {
        int []g = {1, 2};
        int []s = {1, 2, 3};
        assert(so.findContentChildren(g, s) == 2);
    }
    {
        int []g = {};
        int []s = {};
        assert(so.findContentChildren(g, s) == 0);
    }
}

© 著作权归作者所有

共有 人打赏支持
BookShu
粉丝 30
博文 116
码字总数 86364
作品 0
西安
高级程序员
455. Assign Cookies - LeetCode

Question 455. Assign Cookies Solution 题目大意:数组g的大小表示有几个小孩,每个元素表示小孩的食量,数组s的大小表示有多少个饼干,每个元素的大小表示每个饼干的大小,把饼干分给小孩,每个小...

yysue
07/05
0
0
739. Daily Temperatures - LeetCode

Question 739. Daily Temperatures Solution 题目大意:比今天温度还要高还需要几天 思路:笨方法实现,每次遍历未来几天,比今天温度高,就坐标减 Java实现: Ref 别人实现高效的方法 http...

yysue
07/29
0
0
Top 10 Websites for Advanced Level Java Developers

Stackoverflow Stackoverflow.com is probably the most popular website in the programming world. There are millions of good questions and answers. Learning an API or a programming......

perfectspr
2014/12/11
0
0
299. Bulls and Cows - LeetCode

Question 299. Bulls and Cows Solution 题目大意:有一串隐藏的号码,另一个人会猜一串号码(数目相同),如果号码数字与位置都对了,给一个bull,数字对但位置不对给一个cow,注:数字对与位置对优先...

yysue
07/30
0
0
使用OkHttp模拟登陆LeetCode

前言 网上有很多模拟登陆 LeetCode 的教程,但是基本都是使用 Python 来实现的。作为一个 Java 语言爱好者,因此想用 Java 来实现下。在实现的过程中,也遇到了一些坑点,故在此作为记录。 ...

zxzhang
07/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

day58-20180816-流利阅读笔记-待学习

苹果市值破万亿,iPhone 会涨价吗? Lala 2018-08-16 1.今日导读 苹果教父乔布斯曾经说过:“活着就是为了改变世界。”虽然他在 56 岁时就遗憾离世,但他极具创新和变革的精神早已深埋进苹果...

aibinxiao
29分钟前
4
0
[雪峰磁针石博客]python3快速入门教程1 turtle绘图-2函数

菲波那契序列: >>> # Fibonacci series:... # the sum of two elements defines the next... a, b = 0, 1>>> while b < 10:... print(b)... a, b = b, a+b...112......

python测试开发人工智能安全
今天
0
0
java环境变量配置最正确的方式

原贴:https://blog.csdn.net/qq_40007997/article/details/79784711,十分详细,亲测有效

kitty1116
今天
0
0
49.Nginx防盗链 访问控制 解析php相关 代理服务器

12.13 Nginx防盗链 12.14 Nginx访问控制 12.15 Nginx解析php相关配置(502的问题) 12.16 Nginx代理 扩展 502问题汇总 http://ask.apelearn.com/question/9109 location优先级 http://blog....

王鑫linux
今天
2
0
Nginx防盗链、访问控制、解析php相关配置、Nginx代理

一、Nginx防盗链 1. 编辑虚拟主机配置文件 vim /usr/local/nginx/conf/vhost/test.com.conf 2. 在配置文件中添加如下的内容 { expires 7d; valid_referers none blocked server_names *.tes......

芬野de博客
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部