Koko Bananas Leetcode шийдэл


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Facebook-ийн
Хоёртын хайлт

Асуудлын мэдэгдэл

"Коко идэх гадил жимсний" асуудалд бид овоолго бүрийн гадил жимсний тоог агуулсан n хэмжээтэй массивыг өгсөн болно. Нэг цагийн дотор Коко хамгийн ихдээ K гадил идэж болно. Хэрэв овоолго нь К гадилаас бага хэмжээтэй байвал Коко бүх овоолгын гадилыг дуусгаж дуусгасан тохиолдолд тэр нэг цагт өөр овоолгоос гадил идэж чадахгүй.

Коко бүх гадил жимсийг H цагийн дотор идэхийг хүсдэг. Бид K-ийн хамгийн бага утгыг олох ёстой.

Жишээ нь

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

Тайлбар: 

гадил жимсийг идэх коко уусмал

Коко бүх гадил жимсийг 6 цагийн дотор идэхийн тулд гадил жимсийг ийм аргаар идэх болно.

Эхний цаг: 23

Хоёр дахь цаг: 7

Гурав дахь цаг: 11

Дөрөв дэх цаг: 23

Тавдугаар цаг: 4

Зургаа дахь цаг: 20

Коко идэх гадил жимсний Leetcode шийдлийн арга

Энэ асуудлыг шийдэх хамгийн эхний бөгөөд хамгийн чухал зүйл бол ажиглалт хийх явдал юм. Бидний хайлтын интервалд хэдэн ажиглалт оруулав.

  1. Коко цагт дор хаяж нэг гадил жимсний идэх ёстой. Тэгэхээр энэ бол K.-ийн хамгийн бага утга юм Start
  2. Коко нэг цагийн дотор идэж болох хамгийн их хэмжээний гадил жимсний тоог бид бүх овоолгоос овоолсон гадилын тоогоор хязгаарлаж болно. Тэгэхээр энэ бол K.-ийн хамгийн их утга юм Төгсгөл.

Одоо хайлтын интервалтай боллоо. Интервалын хэмжээ нь гэж бодъё Урт ба овоолгын тоо n.  Гэнэн хандлага нь интервал дахь утга тус бүрийг шалгах явдал байж болох юм. Хэрэв К Кокогийн үнэ цэнийн хувьд бүх гадил жимсийг H цагт амжилттай идэж чадвал хамгийн бага хэмжээг нь сонгоорой. Гэнэн хандлагын цаг хугацааны нарийн төвөгтэй байдал нь хамгийн муу тохиолдолд урт * n байх болно.

Шугаман хайлтын оронд Binary Search ашиглан цаг хугацааны нарийн төвөгтэй байдлыг сайжруулах боломжтой.

Ашиглан цаг хугацааны нарийн төвөгтэй байдал Хоёртын хайлт хандалт нь бүртгэл (Урт) * n байх болно.

Хэрэгжүүлэх

Koko Eating Bananas-д зориулсан 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

Koko Eating Bananas-д зориулсан 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 шийдлийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

Дээрх кодын цаг хугацааны нарийн төвөгтэй байдал нь O (n * log (W)) Учир нь бид нэг ба W-ийн хооронд хоёртын хайлт хийж байгаа тул logW хугацаа шаардагдах бөгөөд хоёртын хайлтанд утга бүрийн хувьд овоолгын массивыг дайрч байна. Овоолгын массивыг logW удаа дамжуулж цаг хугацааны нарийн төвөгтэй байдлыг n * logW болгодог. Энд n ба W нь овоолгын тоо ба овоолсон гадилын хамгийн их тоо юм.

Сансрын нарийн төвөгтэй байдал

Дээрх кодын орон зайн нарийн төвөгтэй байдал нь O (1) Учир нь бид хариултыг хадгалахын тулд зөвхөн хувьсагч ашиглаж байна.

Ашигласан материал