კოკო ბანანის ჭამა Leetcode Solution


Რთული ტური საშუალო
ხშირად ეკითხებიან Facebook
ორობითი ძებნა

პრობლემის განცხადება

პრობლემის ”კოკო ბანანის ჭამა” მოცემულია n ზომის მასივი, რომელიც შეიცავს ბანანის რაოდენობას თითოეულ წყობაში. ერთ საათში კოკოს შეუძლია ჭამოს მაქსიმუმ K ბანანი. თუკი poko შეიცავს K– ზე ნაკლებ ბანანს, ამ შემთხვევაში, თუ კოკო ამ წყობის ყველა ბანანს დაასრულებს, მაშინ იმავე საათში მას არ შეუძლია დაიწყოს სხვა pile– დან ბანანის ჭამა.

კოკოს სურს ჭამოს ყველა ბანანი H საათში. ჩვენ უნდა ვიპოვნოთ K– ს მინიმალური მნიშვნელობა.

მაგალითი

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

განმარტება: 

leetcode გადაწყვეტა კოკოს ჭამა ბანანი

კოკო ბანანს შეჭამს ამ გზით, რათა 6 საათში შეჭამოს ყველა ბანანი:

პირველი საათი: 23

მეორე საათი: 7

მესამე საათი: 11

მეოთხე საათი: 23

მეხუთე საათი: 4

მეექვსე საათი: 20

მიდგომა კოკოს ბანანის ჭამის Leetcode Solution- ისადმი

ამ პრობლემის გადასაჭრელად პირველი და ყველაზე მთავარია დაკვირვების გამოტანა. აქ მოცემულია რამდენიმე დაკვირვება ჩვენი ძიების ინტერვალისთვის:

  1. კოკომ საათში უნდა ჭამოს მინიმუმ ერთი ბანანი. ეს არის K.– ს მინიმალური მნიშვნელობა, მოდით დავასახელოთ ასე დაიწყე
  2. ჩვენ შეგვიძლია შევზღუდოთ ბანანის მაქსიმალური რაოდენობა, რომელსაც კოკო ერთ საათში ჭამს, ყველა გროვიდან ბანანის მაქსიმალური რაოდენობით. ეს არის K.- ის მაქსიმალური მნიშვნელობა, მოდით დავასახელოთ ეს ბოლო

ახლა ჩვენ გვაქვს ჩვენი ძიების ინტერვალი. დავუშვათ, ინტერვალის ზომაა სიგრძე და გროვების რაოდენობაა n.  გულუბრყვილო მიდგომა შეიძლება იყოს ინტერვალის თითოეული მნიშვნელობის შემოწმება. თუ K Koko– ს შეუძლია ამ ბანკში ბანანის ჭამა H საათში წარმატებით, აარჩიეთ მინიმალური. გულუბრყვილო მიდგომის დროის სირთულე უარეს შემთხვევაში იქნება სიგრძე * n.

ჩვენ შეგვიძლია გავაუმჯობესოთ დროის სირთულე ორობითი ძიების გამოყენებით ხაზოვანი ძიების ნაცვლად.

დროის სირთულე იყენებს ორობითი ძებნა მიდგომა იქნება log (სიგრძე) * n.

განხორციელება

C ++ კოდი კოკო ბანანის ჭამისთვის

#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 კოდი კოკო ბანანის ჭამისთვის

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 Solution

დროის სირთულე

ზემოთ მოცემული კოდის სირთულეა O (n * ჟურნალი (W)) რადგან ჩვენ ვასრულებთ ორობით ძიებას ერთსა და W- ს შორის, ამას logW დრო სჭირდება და თითოეული მნიშვნელობისთვის, ორობითი ძიებისას, ჩვენ ვათვალიერებთ piles მასივს. Piles მასივი გადის logW– ჯერ, რაც დროის სირთულეს ქმნის n * logW. აქ n და W არის გროვების რიცხვი და ბანანის მაქსიმალური რაოდენობა წყობაში.

კოსმოსური სირთულის

ზემოთ მოცემული კოდის სივრცის სირთულეა O (1) რადგან პასუხის შესანახად ვიყენებთ მხოლოდ ცვლადს.

ლიტერატურა