Доделите решење за колачиће Леетцоде


Ниво тешкоће Лако
Често питани у амазонка
Похлепан

Проблем Додељивање колачића Леетцоде Солутион пружа са два низа. Један од низови представља величину колачића, а друга представља похлепу деце. Проблем наводи да сте родитељ деце и желите да максимални број деце буде задовољан. Детету можете дати само један колачић. Пронађите максималан број садржајне деце. Узмимо прво неколико примера.

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

Објашњење: Имамо два колачића величине 1 сваки и троје деце са различитим вредностима садржаја. Можемо да направимо само једно дете садржаја који има похлепну вредност 1. Будући да су за двоје друге деце потребни већи колачићи.

Доделите решење за колачиће Леетцоде

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

Објашњење: Можемо да обоје деце учинимо да се осећају задовољно јер су колачићи које имамо већи или једнаки потребним величинама. Тако је излаз 2.

Приступ за доделу Леетцоде решења за колачиће

Проблем Додељивање колачића Леетцоде Солутион тражи да пронађемо максималан број подређених садржаја ако детету можемо дати само један колачић. Стога је најбољи приступ похлепно покушати да најмање похлепно дете осети задовољство најмањим колачићем који се може користити. Дакле, да бисмо симулирали овај процес, сортирамо оба дата низа и покушавамо да доделимо колачиће деци. Ако не можемо доделити тренутни колачић тренутном детету, онда покушавамо следећи колачић док не удовољимо тренутном детету. Јер ако не можемо да задовољимо тренутно дете, не можемо да задовољимо ни следећу децу са тренутним колачићем.

код

Ц ++ код за Доделите колачиће Леетцоде Солутион

#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

Јава код за Додела колачића Леетцоде решење

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

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

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

О (НлогН), због времена потребног за сортирање задатих низова. Овде Н представља број елемената у датим низовима.

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

О (НлогН), због простора потребног за сортирање задатих низова. Поново Н представља број елемената у низовима.