Присвояване на бисквитки Leetcode Solution


Ниво на трудност Лесно
Често задавани в Амазонка
Лаком

Проблемът Присвояване на бисквитки Leetcode Solution предлага с два масива. Един от масиви представлява размера на бисквитките, а другият представлява алчността на децата. Проблемът гласи, че вие ​​сте родител на деца и искате максималният брой деца да бъде доволен. Можете да дадете само една бисквитка на дете. Намерете максималния брой деца с съдържание. Нека вземем първо няколко примера.

g = [1,2,3], s = [1,1]
1

Обяснение: Имаме две бисквитки с размер 1 всяка и три деца с различни стойности на съдържанието. Можем да направим само едно дете съдържание, което има алчност стойност 1. Тъй като другите две деца се нуждаят от по-големи бисквитки.

Присвояване на бисквитки Leetcode Solution

g = [1,2], s = [1,2,3]
2

Обяснение: Можем да накараме и двете деца да се чувстват доволни, защото бисквитките, които имаме, са по-големи или равни на необходимите размери. По този начин изходът е 2.

Подход за присвояване на бисквитки Leetcode Solution

Проблемът Assign Cookies Leetcode Solution ни изисква да намерим максималния брой деца, съдържащи се, ако можем да дадем само една бисквитка на дете. По този начин най-добрият подход е алчно да се опитате да накарате най-малко алчното дете да се почувства доволно от най-малката бисквитка, която може да се използва. Така че, за да симулираме този процес, ние сортираме и двата масива и се опитваме да присвоим бисквитките на децата. Ако не можем да присвоим текущата бисквитка на текущото дете, тогава опитваме следващата бисквитка, докато не удовлетворим текущото дете. Защото, ако не можем да задоволим настоящото дете, не можем да задоволим и следващите деца с текущата бисквитка.

код

C ++ код за решение за присвояване на бисквитки Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int numberOfChildren = g.size(), numberOfCookies = s.size();
    int cookie = 0, answer = 0;
    for(int i=0;i<numberOfChildren && cookie<numberOfCookies;){
        if(s[cookie] >= g[i]){
            i++;
            answer++;
        }
        cookie++;
    }
    return answer;
}

int main(){
    vector<int> g = {1, 2, 3};
    vector<int> s = {1, 1};

    cout<<findContentChildren(g, s);
}
1

Java код за Присвояване на бисквитки Leetcode Solution

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
    public static int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int numberOfChildren = g.length;
        int numberOfCookies = s.length;
        int cookie = 0, answer = 0;
        for(int i=0;i<numberOfChildren && cookie<numberOfCookies;){
            if(s[cookie] >= g[i]){
                i++;
                answer++;
            }
            cookie++;
        }
        return answer;
    }
 
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] g = {1, 2, 3};
    int[] s = {1, 1};
 
    System.out.println(findContentChildren(g, s));
  }
}
1

Анализ на сложността

Сложност във времето

O (NlogN), поради времето, необходимо за сортиране на дадените масиви. Тук N представлява броя на елементите в дадени масиви.

Сложност на пространството

O (NlogN), поради мястото, необходимо за сортиране на дадените масиви. Отново N представлява броя на елементите в масивите.