Діти з найбільшою кількістю цукерок з розчином Leetcode


Рівень складності Легко
Часто запитують у Амазонка Bloomberg
масив

У задачі «Діти з найбільшою кількістю цукерок» ми отримуємо цілий ряд цілих чисел, який представляє кількість шоколадних цукерок, які є у деяких дітей, і кілька зайвих цукерок, які можна розподілити будь-яким способом. Тепер нам потрібно знайти:

  • Чи може кожна дитина мати найбільшу кількість шоколадних цукерок після розподілу(або з більшістю, або спільно)?

Нам потрібно надрукувати цю можливість у вигляді логічного вектора.

Приклад

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

Пояснення

1-а дитина: Навіть якби ми дали все додаткові цукерки першій дитині, вона матиме 6 цукерок <7 (5-та дитина). Отже, друкуємо false за це.

2-а дитина: Ми віддаємо всі зайві цукерки цій дитині, враховуючи 9 > 7 (5-та дитина). Отже, друкуємо правда за це.

Так само для третьої, четвертої та п’ятої дитини легко зрозуміти, що у них може бути найбільша кількість цукерок після оптимального розподілу.

Підхід (Жадібний)

У проблемі ми не залежить від нашого вибору, щоб розподілити зайві цукерки. оптимальний спосіб вирішити будь-яку дитину - дати їй усі зайві цукерки, а потім перевірити необхідну умову. Поміркуйте, нам потрібно знайти результат для будь-якого Ith дитина. Тепер максимальна кількість цукерок, яку йому можна дати, дорівнює загальній кількості зайвих цукерок.

Отже, загальна кількість цукерок, якими може володіти Ith дитина = a [i] + зайві цукерки. Якщо це значення більше максимального елемента в масив перед розподілом ми можемо зробити висновок, що ця дитина може отримати найбільше цукерок після розподілу. Оскільки ми вирішили віддати всі зайві цукерки Ith лише дитина, такий підхід є жадібний.

Діти з найбільшою кількістю цукерок з розчином Leetcode

Алгоритм

  1. Знайдіть максимум масиву та збережіть його як maxCandies
  2. Ініціалізуйте логічну форму результат масив
  3. Запустіть цикл від початку масиву до його кінця:
    1. Якщо поточна кількість цукерок Ith дитина + зайві цукерки є більше або дорівнює maxCandies:
      1. Встановіть результат цієї дитини як правда, false інакше
  4. Роздрукуйте результат

Впровадження алгоритму пошуку дітей з найбільшою кількістю цукерок

Програма С ++

#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), Оскільки результат кожної дочірньої дитини ми зберігаємо в окремому масиві.