Күүкийг Leetcode шийдлийг оноох


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны
Шунахай

Leetcode Solution күүкийг хуваарилах асуудал нь хоёр массиваар хангаж өгдөг. Ийн нэг массивууд жигнэмэгийн хэмжээг, нөгөө нь хүүхдүүдийн шуналыг харуулдаг. Асуудал нь таныг хүүхдүүдийн эцэг эх гэдгийг илэрхийлж байгаа бөгөөд та хамгийн их тооны хүүхдүүдийг сэтгэл хангалуун байлгахыг хүсч байна. Та хүүхдэд нэг л жигнэмэг өгөх боломжтой. Хүүхдүүдийн хамгийн их агуулгыг олох. Эхлээд цөөн хэдэн жишээг авч үзье.

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

Тайлбар: Бидэнд тус бүр 1 хэмжээтэй хоёр жигнэмэг, агуулгын өөр утгатай гурван хүүхэд байна. Бид зөвхөн хүүхдийн хувьд ганцхан шуналын утгыг агуулсан контент хийж болно. Нөгөө хоёр хүүхэд нь илүү том жигнэмэг шаарддаг тул.

Күүкийг Leetcode шийдлийг оноох

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

Тайлбар: Бидэнд байгаа жигнэмэг нь шаардлагатай хэмжээнээс их эсвэл тэнцүү тул бид хоёуланд нь хоёуланд нь сэтгэл ханамжийг мэдрүүлж чадна. Тиймээс гаралт нь 2 байна.

Cookies Leetcode Solution-ийг оноох арга

Cookies Leetcode Solution-ийг оноох асуудал нь хэрэв бид хүүхдэд ганц жигнэмэг өгөх боломжтой бол хамгийн их тооны хүүхдийн агуулгыг олохыг биднээс хүсдэг. Тиймээс хамгийн сайн хандлага бол хамгийн бага шуналтай хүүхдэд ашиглаж болох хамгийн жижиг жигнэмэгээр сэтгэл хангалуун байлгахыг хичээх явдал юм. Тиймээс энэ үйл явцыг дууриахын тулд бид өгөгдсөн массивыг хоёуланг нь эрэмбэлж, күүкийг хүүхдүүдэд хуваарилахыг хичээдэг. Хэрэв бид одоогийн жигнэмэгийг одоогийн хүүхдэд хуваарилж чадахгүй бол бид одоо байгаа хүүхдээ хангах хүртэл дараагийн жигнэмэгийг туршиж үзээрэй. Учир нь бид одоогийн хүүхдээ хангаж чадахгүй бол дараагийн хүүхдүүдийг одоогийн жигнэмэгээр хангаж чадахгүй.

код

Cookies Leetcode Solution-ийг онооход зориулсан C ++ код

#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-ийг оноох Java код

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 нь массив дахь элементийн тоог илэрхийлнэ.