文档章节

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

BookShu
 BookShu
发布于 2016/11/23 09:29
字数 585
阅读 117
收藏 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
709. To Lower Case - LeetCode

Question 709. To Lower Case Sollution 题目大意:字符串大写转小写 思路: 直接调用Java API函数 字符串转char数组,遍历数组,判断如果大写就转小写 Java实现:...

yysue
08/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

崩溃bug日志总结1

目录介绍 1.1 java.lang.UnsatisfiedLinkError找不到so库异常 1.2 java.lang.IllegalStateException非法状态异常 1.3 android.content.res.Resources$NotFoundException 1.4 java.lang.Ille......

潇湘剑雨
54分钟前
0
0
学习大数据为什么要先学Java?

计算机编程语言有很多,目前用的多一点的就是Java,C++,Python等等。目前大多数学习大数据的人都是选择学习Java,那Java到底好在哪呢?为什么学大数据之前要先学Java呢?我们今天就来分析一...

董黎明
今天
1
0
php删除服务器所有session

php删除服务器所有session踢掉所有在线用户linux 注意:如果要删除服务器上所有session,重启php服务是解决不了问题的,php的session是持久化的。 有效解决办法: 删除 /tmp 下的所有文件(默...

妖尾巴
今天
0
0
Ubuntu18.04 安装最新版WPS

1.手动卸载libreoffice:sudo apt-get remove --purge libreoffice* 2.官网下载WPS和字体: WPS:http://wps-community.org/download.html 字体:http://wps-community.org/download.html?vl......

AI_SKI
今天
4
0
数据结构(算法)-图(深度优先搜索 DFS)

#include <iostream>using namespace std;#define MaxVex 30typedef char VertexType;typedef struct vexNode adjList[MaxVex];struct edgeNode{int adjvex;//邻接点......

ashuo
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部