მიანიჭეთ ქუქი-ფაილების Leetcode ამოხსნა


Რთული ტური Easy
ხშირად ეკითხებიან Amazon
ხარბ

პრობლემა მიანიჭეთ ქუქი-ფაილებს Leetcode Solution გთავაზობთ ორ მასივს. Ერთერთი მასივები წარმოადგენს ნამცხვრების ზომას, ხოლო მეორე ბავშვების სიხარბეს წარმოადგენს. პრობლემა აცხადებს, რომ თქვენ ხართ ბავშვების მშობელი და გსურთ, რომ ბავშვების მაქსიმალური რაოდენობა კმაყოფილი იყოს. ბავშვისთვის მხოლოდ ერთი ფუნთუშა შეგიძლიათ. იპოვნეთ ბავშვების შინაარსის მაქსიმალური რაოდენობა. ჯერ რამდენიმე მაგალითი ავიღოთ.

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

განმარტება: ჩვენ გვყავს ორი ქუქი-ფაილის ზომის 1 თითო და სამი ბავშვი, განსხვავებული შინაარსის მნიშვნელობით. ჩვენ შეგვიძლია გავაკეთოთ მხოლოდ ერთი ბავშვის შინაარსი, რომელსაც სიხარბის მნიშვნელობა აქვს 1. ვინაიდან დანარჩენ ორ ბავშვს უფრო დიდი ქუქი-ფაილები სჭირდება.

მიანიჭეთ ქუქი-ფაილების Leetcode ამოხსნა

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

განმარტება: ჩვენ შეგვიძლია ორივე ბავშვის შინაგანი განცდა მოვახდინოთ, რადგან ქუქი – ფაილები, რომლებიც გვაქვს, უფრო დიდია ან საჭირო ზომის ტოლია. ამრიგად, გამომავალი არის 2.

მიდგომა მიანიჭეთ ქუქი-ფაილების Leetcode Solution

პრობლემა მიანიჭეთ ქუქი-ფაილებს Leetcode Solution გვთხოვს იპოვოთ ბავშვების მაქსიმალური რაოდენობა, თუ შეგვიძლია მხოლოდ ერთი ქუქი-ჩანაწერი მივცეთ ბავშვს. ამრიგად, საუკეთესო მიდგომაა ხარბად შეეცადოთ, რომ მინიმუმ ხარბი ბავშვი გრძნობდეს შინაარსს ყველაზე მცირე ზომის ფუნთუშებით, რომლის გამოყენებაც შეიძლება. ამ პროცესის სიმულაციის მიზნით, დალაგებულია ორივე მოცემული მასივი და ვცდილობთ ბავშვებს მივაკუთვნოთ ქუქი-ფაილები. თუ ჩვენ არ შეგვიძლია მიმდინარე ქუქი-ფაილის მიკუთვნება ახლანდელ ბავშვს, მაშინ ვცდილობთ შემდეგ ქუქი-ფაილს, სანამ არ დააკმაყოფილებთ ამჟამინდელ ბავშვს. იმიტომ, რომ თუ ვერ ვკმაყოფილებთ ამჟამინდელ ბავშვს, ვერ დავაკმაყოფილებთ მომდევნო ბავშვებს ამჟამინდელი ფუნთუშა.

კოდი

C ++ კოდი Cookies 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

ჯავის კოდი Cookies 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 წარმოადგენს მასივში ელემენტების რაოდენობას.