Koko Eating Bananas Leetcode Solution

cuqquldamaq Facebook LinkedIn Bufer Reddit Tumblr

Mündəricat

Problem bəyanat

“Koko Yemək Bananası” problemində bizə hər yığındakı banan sayını ehtiva edən n ölçülü bir sıra verilir. Bir saat ərzində Koko ən çox K banan yeyə bilər. Əgər xovda K banandan az varsa, o zaman Koko bu xovludakı bütün bananları bitirirsə, o zaman başqa bir xovdan banan yeməyə eyni saatda başlaya bilməz.

Koko bütün bananları H saat ərzində yemək istəyir. K-nin minimum dəyərini tapmalıyıq.

misal

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

Explanation:

Koko, 6 saat ərzində bütün bananları yemək üçün bu şəkildə banan yeyəcək:

İlk saat: 23

İkinci saat: 7

Üçüncü saat: 11

Dördüncü saat: 23

Beşinci saat: 4

Altıncı saat: 20

Koko Eating Bananas Leetcode Solution üçün yanaşma

Bu problemi həll etmək üçün ilk və ən vacib şey müşahidələr aparmaqdır. Axtarış aralığımız üçün bir neçə müşahidələr:

Koko saatda ən az bir banan yeməlidir. Yəni bu K.-nın minimum dəyəri start
Kokonun bir saatda yeyə biləcəyi maksimum banan sayını, yığın içərisindəki yığındakı maksimum banan sayına qədər məhdudlaşdıra bilərik. Yəni bu K.-nın maksimum dəyəri Axırıncı.

İndi axtarış aralığımız var. Fərz edək ki, intervalın ölçüsüdür Uzunluq və yığınların sayı n. Sadəlövh yanaşma intervaldakı hər bir dəyəri yoxlamaq ola bilər. K Kokonun bu dəyəri üçün H saatda bütün bananları uğurla yeyə bilərsə, minimumunu seçin. Sadəlövh yanaşma üçün zaman mürəkkəbliyi ən pis halda Uzunluq * n olacaqdır.

Xətti Axtarış yerinə İkili Axtarışdan istifadə edərək zamanın mürəkkəbliyini yaxşılaşdıra bilərik.

Zamanın mürəkkəbliyi İkili axtarış yanaşma log olacaq (Uzunluq) * n.

Həyata keçirilməsi

Koko Eating Bananas üçün C ++ kodu

#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;
}

Koko Eating Bananas üçün Java kodu

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);
  }
}

Koko Yemək Banan Leetcode Həllinin Mürəkkəblik Analizi

Zaman mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (n * log (W)) bir ilə W arasında ikili axtarış apardığımız üçün logW vaxtı tələb olunur və hər bir dəyər üçün ikili axtarışda yığınlar dizisini keçirik. Beləliklə, yığınlar kütləsi zamanın mürəkkəbliyini n * logW edən logW dəfə keçir. Burada n və W yığın sayları və bir yığındakı maksimum banan sayıdır.

Kosmik mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki cavabı saxlamaq üçün yalnız dəyişəndən istifadə edirik.

References