Leetcode шийдлийн хамгийн олон тооны чихэртэй хүүхдүүд


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

“Хамгийн олон тооны чихэртэй хүүхдүүд” гэсэн дугаарт зарим хүүхдүүдийн авсан шоколадны тоог илэрхийлсэн бүхэл тоон массив болон ямар ч хэлбэрээр тарааж болох нэмэлт чихрүүдийг бидэнд өгсөн болно. Одоо бид дараахь зүйлийг олох хэрэгтэй.

  • Хүүхэд бүр хамгийн олон тооны шоколад авч чадах уу? түгээлтийн дараа(аль аль нь олонхиороо эсвэл хамтарч)?

Бид энэ боломжийг boolean вектор хэлбэрээр хэвлэх хэрэгтэй.

Жишээ нь

Array = {1 , 4 , 5 , 6 , 7}
Extra = 5
false true true true true

Тайлбар

1-р хүүхэд: Бид бүгдийг өгсөн ч гэсэн эхний хүүхдэд нэмэлт чихэр, 6 чихэртэй болно <7 (5-р хүүхэд). Тиймээс бид хэвлэж байна хуурамч энэ нь.

2-р хүүхэд: Бид бүгдийг өгдөг энэ хүүхдэд нэмэлт чихэр, тоолох болно 9 > 7 (5-р хүүхэд). Тиймээс бид хэвлэж байна үнэн энэ нь.

Үүнтэй адил гурав, дөрөв, тав дахь хүүхдийн хувьд хамгийн оновчтой тараасны дараа хамгийн их чихэр авах боломжтойг харахад хялбар байдаг.

Хандалт (Шунахай)

Асуудлын хувьд бид нэмэлт чихэр тараах сонголтоос хараат бус байдаг. The хамгийн оновчтой Хүүхдэд зориулж шийдэх арга бол бүх нэмэлт чихэр өгч дараа нь шаардлагатай нөхцлийг шалгах явдал юм. Бид ямар ч үр дүнг олох хэрэгтэй ith хүүхэд. Одоо түүнд өгч болох хамгийн их чихэр нь нийт нэмэлт чихэртэй тэнцүү байна.

Тиймээс эзэмших боломжтой чихрийн нийт тоо ith хүүхэд = a [i] + нэмэлт чихэр. Хэрэв энэ утга нь хамгийн их элементээс их байвал массив тараахаасаа өмнө тараасны дараа энэ хүүхэд хамгийн их чихэр авах боломжтой гэж бид дүгнэж болно. Бид бүх нэмэлт чихэр өгөхөөр сонгосон тул ith зөвхөн хүүхэд, энэ арга барил нь шунахай явдал.

Leetcode шийдлийн хамгийн олон тооны чихэртэй хүүхдүүд

Алгоритм

  1. Массивын дээд хэмжээг олж хадгална maxCandies
  2. Boolean эхлүүлэх үр дүн массив
  3. Массивын эхнээс төгсгөл хүртэл давталт ажиллуулна.
    1. Хэрэв одоо байгаа чихрийн тоо ith хүүхэд + нэмэлт чихэр илүү буюу тэнцүү maxCandies:
      1. Энэ хүүхдийн үр дүнг дараах байдлаар тохируулна уу үнэн, хуурамч өөрөөр хэлбэл
  4. Үр дүнг хэвлэ

Хамгийн олон тооны чихэртэй хүүхдүүдийг олох алгоритмын хэрэгжилт

C ++ програм

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

vector <bool> kidsWithCandies(vector <int> &candies , int extraCandies)
{
    int n = candies.size() , maxCandies = 0;
    for(int i = 0 ; i < n ; i++)
        if(candies[i] > maxCandies)
            maxCandies = candies[i];


    vector <bool> result(n);
    for(int i = 0 ; i < n ; i++)
        result[i] = (candies[i] + extraCandies >= maxCandies);

    return result;
}


int main()
{
    vector <int> candies = {1 , 4 , 5 , 6 , 7};
    int extraCandies = 5;
    for(bool x : kidsWithCandies(candies , extraCandies))
        cout << (x ? "true" : "false") << " ";
    cout << '\n';
    return 0;
}

Java програм

class kids_with_candies
{
    public static void main(String args[])
    {
        int[] candies = {1 , 4 , 5 , 6 , 7};
        int extraCandies = 5;
        for(boolean x : kidsWithCandies(candies , extraCandies))
            System.out.print(x + " ");
    }


    static boolean[] kidsWithCandies(int[] candies , int extraCandies)
    {
        int n = candies.length , maxCandies = 0;
        for(int i = 0 ; i < n ; i++)
            if(candies[i] > maxCandies)
                maxCandies = candies[i];

        boolean[] result = new boolean[n];

        for(int i = 0 ; i < n ; i++)
            result[i] = (candies[i] + extraCandies >= maxCandies);

        return result;
    }
}
false true true true true

Хамгийн олон тооны чихэртэй хүүхдийг олох нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N), N = массивын хэмжээ. Бүх массивыг нэг удаа туулахдаа.

Сансрын нарийн төвөгтэй байдал

O (N), Бид хүүхэд бүрийн үр дүнг тусдаа массивт хадгалах болно.