Նշանակեք բլիթները Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon
Ագահ

Խնդիրը Տեղադրել թխուկները Leetcode Solution- ը տրամադրում է երկու զանգված: Մեկը զանգվածներ ներկայացնում է թխվածքաբլիթների չափը, իսկ մյուսը ՝ երեխաների ագահությունը: Խնդիրն ասում է, որ դուք երեխաների ծնող եք, և ցանկանում եք, որ երեխաների առավելագույն քանակը բավարարված լինի: Երեխային կարող եք տալ միայն մեկ թխվածքաբլիթ: Գտեք երեխաների բովանդակության առավելագույն քանակը: Նախ վերցնենք մի քանի օրինակ:

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

Բացատրություն. Մենք ունենք յուրաքանչյուրի 1 չափսի երկու թխուկ և տարբեր բովանդակության արժեք ունեցող երեք երեխա: Մենք կարող ենք պատրաստել միայն մեկ երեխայի բովանդակություն, որն ունի ագահության արժեք 1. Քանի որ մյուս երկու երեխաները ավելի մեծ թխուկներ են պահանջում:

Նշանակեք բլիթները Leetcode լուծում

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

Բացատրություն. Մենք կարող ենք այնպես անել, որ երեխաներից երկուսն էլ բավարարվածություն զգան, քանի որ մեր ունեցած բլիթներն ավելի մեծ են կամ հավասար են պահանջվող չափերի: Այսպիսով արդյունքը 2 է:

Cookies- ի նշանակման համար Leetcode լուծման մոտեցում

Խնդիրը Տեղադրել Տեղեկանիշներ Leetcode Solution- ը խնդրում է մեզ գտնել երեխաների բովանդակության առավելագույն քանակը, եթե մենք կարողանանք միայն մեկ cookie տալ երեխային: Այսպիսով, լավագույն մոտեցումն այն է, որ ագահորեն փորձել այնպես անել, որ նվազագույն ագահ երեխան գոհ մնա օգտագործվող ամենափոքր թխվածքաբլիթից: Այսպիսով, այս գործընթացը մոդելավորելու համար մենք դասավորում ենք և՛ տրված զանգվածները, և՛ փորձում ենք բլիթները հատկացնել երեխաներին: Եթե ​​մենք չենք կարող ներկայիս cookie- ն վերագրել ներկայիս երեխային, ապա մենք կփորձենք հաջորդ cookie- ն այնքան ժամանակ, քանի դեռ չենք բավարարել ներկայիս երեխային: Քանի որ եթե մենք չենք կարող բավարարել ներկայիս երեխային, մենք չենք կարող բավարարել հաջորդ երեխաներին ներկայիս cookie- ով:

Կոդ

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

Java- ի կոդը ՝ 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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (NlogN), տրված զանգվածները տեսակավորելու համար պահանջվող ժամանակի պատճառով: Այստեղ N- ը ներկայացնում է տրված զանգվածների տարրերի քանակը:

Տիեզերական բարդություն

O (NlogN), տրված զանգվածները տեսակավորելու համար պահանջվող տարածքի պատճառով: Կրկին N- ը ներկայացնում է զանգվածների տարրերի քանակը: