LeetCode:455.Assign Cookies分配ビスケット
LeetCode:455.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.
もしあなたが素晴らしい両親で、あなたの子供にビスケットをあげたいとしたら.しかし、子供一人一人にビスケットをあげるべきです.どの子iにも貪欲な因子giがあり、これは子供が満足しているビスケットの最小サイズです.そして、各ビスケットjの大きさはsjである.sj>=giの場合、ビスケットjを子iに割り当てることができ、子供iは満足します.満足できる子供の数を最大化し、最大数を出力することを目標としています.
注意:貪欲因子は常に正であると仮定できます.1人の子供に複数のクッキーを割り当てることはできません.例1:入力:[1,2,3],[1,1]出力:1説明:子供3人とクッキー2人です.3人の子供の貪欲な因子は1,2,3です.ビスケットが2つあっても、大きさが1なので、子供の貪欲因子を1に満たすしかありません.出力1が必要です.例2:入力:[1,2],[1,2,3]出力:2説明:子供2人とクッキー3人です.2人の子供の貪欲な因子は1,2です.すべての子供を満たすのに十分な大きさのビスケットが3つあります.2を出力する必要があります.
貪欲な思想は、操作のたびに局所的に最適であり、最後に得られた結果がグローバルに最適であることを保証する.
すべての子供は満足度を持っていて、すべてのビスケットはすべて1つの大きさがあって、自由ビスケットの大きさは1人の子供の満足度より大きくて、この子はやっと満足を得ることができます.最も満足できる子供の数を解く.
このテーマは2組のarrayをあげて、1組は子供の貪欲な因子(食欲値)を代表して、もう1組はビスケットの大きさを代表します.できるだけ多くの子供にビスケットを配布し、ビスケットの大きさは子供の食欲を満たすことができます.大きなビスケットを小さな食欲を満たす子供にはできません.選択しない限り.できるだけクッキーを食欲のある子供に送ります.まず2つのarrayを並べ直し、小さいものから大きいものまで並べ替えます.それからビスケットarrayを遍歴して、満足できる子供を見つけて、クッキーを送って、彼のindexを覚えて、今度は直接次の子供から探します.
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.
もしあなたが素晴らしい両親で、あなたの子供にビスケットをあげたいとしたら.しかし、子供一人一人にビスケットをあげるべきです.どの子iにも貪欲な因子giがあり、これは子供が満足しているビスケットの最小サイズです.そして、各ビスケットjの大きさはsjである.sj>=giの場合、ビスケットjを子iに割り当てることができ、子供iは満足します.満足できる子供の数を最大化し、最大数を出力することを目標としています.
注意:貪欲因子は常に正であると仮定できます.1人の子供に複数のクッキーを割り当てることはできません.例1:入力:[1,2,3],[1,1]出力:1説明:子供3人とクッキー2人です.3人の子供の貪欲な因子は1,2,3です.ビスケットが2つあっても、大きさが1なので、子供の貪欲因子を1に満たすしかありません.出力1が必要です.例2:入力:[1,2],[1,2,3]出力:2説明:子供2人とクッキー3人です.2人の子供の貪欲な因子は1,2です.すべての子供を満たすのに十分な大きさのビスケットが3つあります.2を出力する必要があります.
貪欲な思想は、操作のたびに局所的に最適であり、最後に得られた結果がグローバルに最適であることを保証する.
すべての子供は満足度を持っていて、すべてのビスケットはすべて1つの大きさがあって、自由ビスケットの大きさは1人の子供の満足度より大きくて、この子はやっと満足を得ることができます.最も満足できる子供の数を解く.
import java.util.Arrays;
import java.util.Scanner;
public class AssignCookies {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int gi = sc.nextInt();//gi>=si
int si = sc.nextInt();
int aa[] = new int[gi];//greed factor
int bb[] = new int[si];
for(int k=0;k
このテーマは2組のarrayをあげて、1組は子供の貪欲な因子(食欲値)を代表して、もう1組はビスケットの大きさを代表します.できるだけ多くの子供にビスケットを配布し、ビスケットの大きさは子供の食欲を満たすことができます.大きなビスケットを小さな食欲を満たす子供にはできません.選択しない限り.できるだけクッキーを食欲のある子供に送ります.まず2つのarrayを並べ直し、小さいものから大きいものまで並べ替えます.それからビスケットarrayを遍歴して、満足できる子供を見つけて、クッキーを送って、彼のindexを覚えて、今度は直接次の子供から探します.
public class Solution
{
public int findContentChildren(int[] g, int[] s)
{
int res = 0;
int index_g = 0;
Arrays.sort(g);
Arrays.sort(s);
for(int i=0; i< s.length; i++)
{
if(s[i] >= g[index_g])
{
res++;
index_g++;
if(index_g >= g.length)
break;
}
}
return res;
}
}