Koko ငှက်ပျောသီး Leetcode ဖြေရှင်းချက်စားခြင်း


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Facebook က
Binary Search

ပြstatementနာကြေညာချက်

ပြokoနာတွင်“ ကိုကိုစားသောငှက်ပျောသီး” ပြpနာ၌ပုံတစ်ပုံစီတွင်ငှက်ပျောသီးအရေအတွက်ပါဝင်သောအရွယ်အစား n ကိုကျွန်ုပ်တို့အားပေးထားသည်။ တစ်နာရီအတွင်းကိုကိုကိုသည်ငှက်ပျောသီးအများဆုံးစားနိုင်သည်။ အကယ်၍ Koko သည်ထိုအမှု၌ K သည်ငှက်ပျောသီးထက်နည်းပါက Koko သည်ထိုပုံပေါ်ရှိငှက်ပျောသီးအားလုံးကိုပြီးအောင်လုပ်လျှင်ထိုအချိန်တွင်ပင်သူသည်အခြားပုံတစ်ပုံမှငှက်ပျောသီးကိုမစားနိုင်တော့ပါ။

ကိုကိုကိုသည် H နာရီအတွင်းငှက်ပျောသီးအားလုံးကိုစားချင်သည်။ ကျွန်ုပ်တို့သည် K. ၏အနည်းဆုံးတန်ဖိုးကိုရှာရမည်။

နမူနာ

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

ရှင်းလင်းချက်: 

ငှက်ပျောသီးစားသုံးခြင်းကိုကိုကိုမှ leetcode ဖြေရှင်းနည်း

၆ နာရီအတွင်း Koko သည်ငှက်ပျောသီးကိုဤနည်းဖြင့်စားလိမ့်မည်။

ပထမနာရီ - ၂၃

ဒုတိယနာရီ - ၇

တတိယနာရီ - ၁၁

စတုတ္ထနာရီ - ၂၃

ပဉ္စမနာရီ - ၄

ဆဌမနာရီ - ၂၀

Koko သည်ငှက်ပျောသီး Leetcode Solution ကိုစားသုံးခြင်းအတွက်ချဉ်းကပ်နည်း

ဤပြproblemနာကိုဖြေရှင်းရန်ပထမနှင့်အရေးကြီးဆုံးမှာလေ့လာတွေ့ရှိချက်များကိုထုတ်ယူရန်ဖြစ်သည်။ ဤတွင်ကျွန်ုပ်တို့၏ရှာဖွေခြင်းကြားခံအတွက်အနည်းငယ်လေ့လာတွေ့ရှိချက်များဖြစ်သည်။

  1. ကိုကိုကိုသည်တစ်နာရီလျှင်အနည်းဆုံးငှက်ပျောတစ်ကောင်စားရမည်။ ဒီတော့ဒါကအနည်းဆုံး K. ရဲ့တန်ဖိုး စတင်
  2. ကျွန်ုပ်တို့သည်တစ်နာရီအတွင်းကိုကိုကိုးစားသုံးနိုင်သောအမြင့်ဆုံးငှက်ပျောအရေအတွက်ကိုအကန့်အသတ်ဖြင့်သာချုပ်နှောင်ထားနိုင်သည်။ ဒီတော့ဒါကအကြီးဆုံး K. ရဲ့တန်ဖိုးပါ အဆုံး။

ယခုငါတို့ရှာဖွေရေးကြားကာလရှိသည်။ ကြားကာလ၏အရွယ်အစားသည်ဆိုပါစို့ အရှည် နှင့်လိပ်ခေါင်းအရေအတွက်ဖြစ်ပါတယ် n.  အဆိုပါနုံချဉ်းကပ်ကာလအတွင်းတန်ဖိုးတစ်ခုချင်းစီကိုစစ်ဆေးဖို့ဖြစ်နိုင်ပါတယ်။ အကယ်၍ K တန်ဖိုး၏တန်ဖိုးသည် H နာရီအတွင်းငှက်ပျောသီးအားလုံးကိုအစာစားနိုင်လျှင်၎င်းသည်အနည်းဆုံးကိုရွေးပါ။ အဆိုးဆုံးချဉ်းကပ်မှုအတွက်အချိန်ရှုပ်ထွေးမှုသည်အရှည် * n ဖြစ်သည်။ အဆိုးဆုံးအခြေအနေဖြစ်သည်။

Linear Search နေရာတွင် Binary Search ကိုအသုံးပြုခြင်းအားဖြင့်ကျွန်ုပ်တို့သည်အချိန်ရှုပ်ထွေးမှုကိုတိုးတက်စေနိုင်သည်။

ကိုအသုံးပြု။ အချိန်ရှုပ်ထွေး Binary Search ချဉ်းကပ်မှု * အရှည် * be log ဖြစ်လိမ့်မည်။

အကောင်အထည်ဖော်ရေး

Koko သည်ငှက်ပျောသီးစားရန်အတွက် 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 သည်ငှက်ပျောသီးစားရန်အတွက် 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

Koko သည် Bananas Leetcode Solution ကိုစားသုံးခြင်း၏ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အထက်ပါကုဒ်၏အချိန်ရှုပ်ထွေးသည် အို (n * log (W)) အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည်တ ဦး တည်းနှင့် W အကြား binary search ကိုလုပ်ဆောင်နေသောကြောင့်၎င်းသည် logW အချိန်နှင့်တန်ဖိုးတစ်ခုစီအတွက် binary search တွင်ကျွန်ုပ်တို့သည် piles ခင်းကျင်းခြင်းကိုဖြတ်သန်းနေသည်။ ဒါကြောင့် piles ခင်းကျင်းမှုသည် logW ကြိမ်ဖြတ်သန်းသွားသည်။ ၎င်းသည်အချိန်ရှုပ်ထွေးမှု n * logW ကိုဖြစ်ပေါ်စေသည်။ ဤတွင် n နှင့် W သည်လိပ်ခေါင်းအရေအတွက်နှင့်စုစုပေါင်းငှက်ပျောသီးအများဆုံးအရေအတွက်ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အပေါ်ကကုဒ်ရဲ့ရှုပ်ထွေးမှုက အို (၁) ဘာလို့လဲဆိုတော့ငါတို့ကအဖြေကိုသိမ်းဖို့ variable တစ်ခုပဲသုံးတယ်။

ကိုးကား