Koko กินกล้วย Leetcode Solution


ระดับความยาก กลาง
ถามบ่อยใน Facebook
การค้นหาแบบไบนารี

คำชี้แจงปัญหา

ในโจทย์ "กล้วยกินโกโก้" เราจะได้รับอาร์เรย์ขนาด n ซึ่งมีจำนวนกล้วยในแต่ละกอง ในหนึ่งชั่วโมง Koko สามารถกินกล้วย K ได้มากที่สุด ถ้ากองมีกล้วยน้อยกว่า K ในกรณีนั้นถ้า Koko กินกล้วยทั้งหมดของกองนั้นเสร็จเธอก็จะไม่สามารถเริ่มกินกล้วยจากกองอื่นได้ในชั่วโมงเดียวกัน

แป้งโกะอยากกินกล้วยให้หมดภายในชั่วโมง เราควรจะหาค่าต่ำสุดของ K

ตัวอย่าง

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

คำอธิบาย: 

วิธีแก้ปัญหา leetcode เพื่อ koko กินกล้วย

Koko จะกินกล้วยด้วยวิธีนี้เพื่อกินกล้วยทั้งหมดใน 6 ชั่วโมง:

ชั่วโมงแรก: 23

ชั่วโมงที่สอง: 7

ชั่วโมงที่สาม: 11

ชั่วโมงที่สี่: 23

ชั่วโมงที่ห้า: 4

ชั่วโมงที่หก: 20

แนวทางสำหรับ Koko Eating Bananas Leetcode Solution

สิ่งแรกและสำคัญที่สุดในการแก้ปัญหานี้คือการตั้งข้อสังเกต ข้อสังเกตบางประการสำหรับช่วงเวลาการค้นหาของเรามีดังนี้:

  1. แป้งโกะต้องกินกล้วยอย่างน้อยหนึ่งลูกต่อชั่วโมง นี่คือค่าต่ำสุดของ K ขอตั้งชื่อเป็น เริ่มต้น
  2. เราสามารถ จำกัด จำนวนกล้วยสูงสุดที่ Koko สามารถกินได้ในหนึ่งชั่วโมงถึงจำนวนกล้วยสูงสุดในกองจากกองทั้งหมด นี่คือค่าสูงสุดของ K. ขอตั้งชื่อเป็น ปลาย

ตอนนี้เรามีช่วงการค้นหาของเรา สมมติว่าขนาดของช่วงเวลาคือ ความยาว และจำนวนกองคือ n.  วิธีการที่ไร้เดียงสาอาจเป็นการตรวจสอบแต่ละค่าในช่วงเวลา ถ้า Koko สามารถกินกล้วยทั้งหมดในชั่วโมง H ได้สำเร็จให้เลือกจำนวนขั้นต่ำ ความซับซ้อนของเวลาสำหรับวิธีการที่ไร้เดียงสาจะเป็น Length * n ในกรณีที่เลวร้ายที่สุด

เราสามารถปรับปรุงความซับซ้อนของเวลาได้โดยใช้ Binary Search แทน Linear Search

ความซับซ้อนของเวลาโดยใช้ การค้นหาแบบไบนารี แนวทางจะเป็น 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

การวิเคราะห์ความซับซ้อนของ Koko Eating Bananas Leetcode Solution

ความซับซ้อนของเวลา

ความซับซ้อนของเวลาของรหัสข้างต้นคือ O (n * บันทึก (W)) เนื่องจากเราทำการค้นหาไบนารีระหว่างหนึ่งถึง W ซึ่งต้องใช้เวลา logW และสำหรับแต่ละค่าในการค้นหาไบนารีเรากำลังข้ามอาร์เรย์ของกอง ดังนั้นอาร์เรย์ของเสาเข็มจึงข้าม logW ครั้งทำให้เวลามีความซับซ้อน n * logW n และ W คือจำนวนกองและจำนวนกล้วยสูงสุดในกอง

ความซับซ้อนของพื้นที่

ความซับซ้อนของช่องว่างของรหัสข้างต้นคือ O (1) เนื่องจากเราใช้เพียงตัวแปรในการจัดเก็บคำตอบ

อ้างอิง