文档章节

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

BookShu
 BookShu
发布于 2016/11/23 09:29
字数 585
阅读 118
收藏 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
粉丝 31
博文 116
码字总数 86364
作品 0
西安
高级程序员
私信 提问
455. Assign Cookies - LeetCode

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

yysue
07/05
0
0
php-java 桥接问题,以下错误如何修改

php-java 桥接问题,以下错误如何修改 http://blog.sina.com.cn/s/blog_51a5e5f40100cxie.html 安装以上步骤操作 Fatal error: Uncaught [[o:Exception]:"java.lang.Exception: CreateInsta......

zc52406
2013/01/17
1K
1
Valid Palindrome leetcode125

这道题的回文字符串比较特殊的就是还有标点符号和空格等其他字符不在判断范围之内 如果用上java自带的那些类,其实有很多的判断方法: 还有我们可以从头尾开始遍历,如果不匹配就返回false 源...

woshixin
10/11
0
0
739. Daily Temperatures - LeetCode

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

yysue
07/29
0
0
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 栈的 java 实现 2. 队列的 java 实现 1. 用两个栈实现队列 剑指offer:用两个栈实现队列 Leet...

繁著
09/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

计算机系统要素 C5

本章值得一提的是组织计算机的结构。Hack 的指令和数据是分开存储的,因此它的 CPU 有两个 input: IN inM[16], // M value input (M = contents of RAM[A]) instruction[16],...

lionets
11分钟前
0
0
SpringSecurity404需要注意的地方

在使用@RequestMapping的时候路径的值如果写为("auth"),虽然用的时候前面加不加"/"没有区别,但是在配置了SpringSecurity的http.authorizeRequests().antMatchers()时就必须要注意了! 🌰1...

百萬馬力
15分钟前
0
0
10分钟读懂阿里巴巴高级专家在Flutter Live2018的分享

作者:闲鱼技术-宗心 12月4日,google flutter团队宣布第一个flutter正式版本发布。次日,Flutter Live Beijing 会议上,google flutter团队邀请了在这一技术方案中重要的合作伙伴闲鱼团队分...

阿里云官方博客
15分钟前
1
0
RxJava window操作符

原文:https://github.com/Froussios/Intro-To-RxJava/blob/master/Part%204%20-%20Concurrency/3.%20Sequences%20of%20coincidence.md Sequences of coincidence Rx试图避免管道(pipeline)外......

woshixin
22分钟前
1
0
05.Beetl标签函数以及定界符、占位符介绍---《Beetl视频课程》

本期视频实现了博客的详情页面; 内容简介:使用了标签函数layout完成详情功能 一起学beetl目录:https://my.oschina.net/u/1590490?tab=newest&catalogId=6214598 作者:GK #标签函数 layo...

Gavin-King
23分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部