Koko Eating Bananas Leetcode Solution


Рівень складності Medium
Часто запитують у Facebook
Двійковий пошук

Постановка проблеми

У задачі “Коко їсть банани” ми отримуємо масив розміром n, який містить кількість бананів у кожній купі. За одну годину Коко може з’їсти не більше K бананів. Якщо купа містить менше K бананів, у цьому випадку, якщо Коко закінчує всі банани з цієї купи, вона не може почати їсти банани з іншої купи в ту ж годину.

Коко хоче з’їсти всі банани протягом H годин. Ми повинні знайти мінімальне значення K.

Приклад

piles = [30,11,23,4,20], H = 6
23

Пояснення: 

leetcode рішення для коко їсти банани

Коко буде їсти банани таким чином, щоб з'їсти всі банани за 6 годин:

Перша година: 23

Друга година: 7

Третя година: 11

Четверта година: 23

П’ята година: 4

Шоста година: 20

Підхід до рішення Koko Eating Bananas Leetcode

Перше і найважливіше для вирішення цієї проблеми - це виявлення спостережень. Ось кілька спостережень за нашим інтервалом пошуку:

  1. Коко повинен з'їдати щонайменше один банан на годину. Отже, це мінімальне значення К., назвемо його як Start
  2. Ми можемо обмежити максимальну кількість бананів, які Коко може з’їсти за одну годину, максимальною кількістю бананів у купі з усіх куп. Отже, це максимальне значення К., назвемо його як Кінець.

Тепер у нас є інтервал пошуку. Припустимо, розмір інтервалу дорівнює довжина а кількість паль - n.  Наївним підходом може бути перевірка кожного значення в інтервалі. якщо для цього значення K Koko може з’їсти всі банани за годину H, тоді виберіть мінімум з них. Складність часу для наївного підходу в найгіршому випадку складе Length * n.

Ми можемо покращити часову складність, використовуючи Бінарний пошук замість Лінійного пошуку.

Складність часу з використанням Двійковий пошук підхід буде log (Length) * n.

Реалізація

Код C ++ для Koko Eating Bananas

#include <bits/stdc++.h>
using namespace std; 
       int minEatingSpeed(vector<int>& pile, int hour) {
        int left = 1, right = *max_element(pile.begin(),pile.end());;
        while (left < right) {
            int mid = (left + right) / 2, total = 0;
            for (int p : pile) total += (p + mid - 1) / mid;
            if (total > hour) left = mid + 1; else right = mid;
        }
        return left;
    }
int main() 
{ 
 vector<int> arr = {30,11,23,4,20}; 
 int H=6;                               
 cout<<minEatingSpeed(arr,H)<<endl;
 return 0;
}
23

Код Java для Koko Eating Bananas

import java.util.Arrays; 
public class Tutorialcup {
    public static int minEatingSpeed(int[] piles, int H) {
        int left = 1, right =Arrays.stream(piles).max().getAsInt();
        while (left < right) {
            int mid = (left + right) / 2, total = 0;
            for (int p : piles) total += (p + mid - 1) / mid;
            if (total > H) left = mid + 1; else right = mid;
        }
        return left;
    }
  public static void main(String[] args) {
    int [] arr = {30,11,23,4,20}; 
     int H=6; 
    int ans= minEatingSpeed(arr,H);
    System.out.println(ans);
  }
}
23

Аналіз складності розчину для вживання бананів Leetcode

Часова складність

Часова складність вищевказаного коду становить O (n * журнал (W)) оскільки ми виконуємо двійковий пошук між одиницею та W, це займає час logW, і для кожного значення у двійковому пошуку ми обходимо масив купи. Отже, масив паль обходить logW разів, і це ускладнює час n * logW. Тут n і W - кількість куп і максимальна кількість бананів в купі.

Космічна складність

Складність простору наведеного коду становить O (1) тому що ми використовуємо лише змінну для зберігання відповіді.

посилання