Քաղցրավենիքի ամենամեծ թվով երեխաներ Leetcode լուծում


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

«Ամենաշատ կոնֆետներ ունեցող երեխաներ» խնդրում մեզ տրված է մի ամբողջ շարք, որը ներկայացնում է որոշ երեխաների ստացած շոկոլադների քանակը և որոշ լրացուցիչ կոնֆետներ, որոնք կարող են բաժանվել ցանկացած ձևով: Այժմ մենք պետք է գտնենք.

  • Յուրաքանչյուր երեխա կարո՞ղ է ունենալ ամենամեծ քանակությամբ շոկոլադները բաշխումից հետո(կա՛մ մեծամասնությամբ, կա՛մ համատեղ):

Մենք պետք է այս հնարավորությունը տպենք բուլյան վեկտորի տեսքով:

Օրինակ

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

բացատրություն

1-ին երեխա: Նույնիսկ եթե մենք տանք բոլորին լրացուցիչ կոնֆետներ առաջին երեխային, այն կունենա 6 կոնֆետ <7 (5-րդ երեխա): Այսպիսով, մենք տպում ենք սուտ դրա համար.

2-րդ երեխաՄենք տալիս ենք բոլորին հավելյալ կոնֆետներ այս երեխային ՝ իր հաշվարկը դնելով 9 > 7 (5-րդ երեխա): Այսպիսով, մենք տպում ենք ճիշտ դրա համար.

Նմանապես, երրորդ, չորրորդ և հինգերորդ երեխաների համար հեշտ է տեսնել, որ նրանք կարող են ունենալ ամենամեծ քանակությամբ կոնֆետներ օպտիմալ բաշխումից հետո:

Մոտեցում (ագահ)

Խնդիրի մեջ մենք անկախ ենք լրացուցիչ կոնֆետներ բաժանելու մեր ընտրությունից: Ի օպտիմալ childանկացած երեխայի որոշում կայացնելու միջոց կլինի դրան տալ բոլոր լրացուցիչ կոնֆետները, ապա ստուգել անհրաժեշտ պայմանը: Հաշվի առեք, որևէ մեկի արդյունքը պետք է գտնենք ith երեխա Այժմ կոնֆետների առավելագույն քանակը, որը կարող է տրվել դրան, հավասար է ընդհանուր լրացուցիչ կոնֆետների:

Հետեւաբար, կոնֆետների ընդհանուր քանակը, որոնք կարող են ունենալ ith երեխա = a [i] + լրացուցիչ կոնֆետներ: Եթե ​​այս արժեքն ավելի մեծ է, քան առավելագույն տարրում դասավորություն բաշխումից առաջ մենք կարող ենք եզրակացնել, որ բաշխելուց հետո այս երեխան կարող է ունենալ ամենաշատ կոնֆետները: Քանի որ մենք նախընտրում ենք բոլոր լրացուցիչ կոնֆետները տալ ith միայն երեխան է, այս մոտեցումն է ագահ.

Քաղցրավենիքի ամենամեծ թվով երեխաներ Leetcode լուծում

Ալգորիթմ

  1. Գտեք զանգվածի առավելագույնը և պահեք այն ինչպես maxCandies
  2. Նախաձեռնեք բուլյան արդյունք դասավորություն
  3. Runանգի մեկնարկից մինչև դրա վերջը գործարկեք մի օղակ.
    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

Ամենաշատ կոնֆետներ ունեցող երեխաներին գտնելու բարդության վերլուծություն

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

ՎՐԱ), N = զանգվածի չափը: Երբ մենք մեկ անգամ անցնում ենք ամբողջ զանգվածը:

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

ՎՐԱ), Քանի որ յուրաքանչյուր երեխայի արդյունքը մենք խնայում ենք առանձին զանգվածում: