ວິທີແກ້ໄຂກ້ວຍກິນກ້ວຍກິນ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ເຟສບຸກ
ການຄົ້ນຫາຖານສອງ

ບັນຫາບັນຫາ

ໃນບັນຫາ "ກ້ວຍກິນກ້ວຍ" ພວກເຮົາໄດ້ຮັບຂະ ໜາດ n ເຊິ່ງປະກອບມີ ຈຳ ນວນກ້ວຍໃນແຕ່ລະເສົາ. ໃນ ໜຶ່ງ ຊົ່ວໂມງ Koko ສາມາດກິນໄດ້ເກືອບທຸກກ້ວຍ K. ຖ້າກະຕ່າບັນຈຸກ້ວຍນ້ອຍກວ່າ K ໃນກໍລະນີດັ່ງກ່າວຖ້າວ່າ Koko ຈົບກ້ວຍທັງ ໝົດ ຂອງເສົານັ້ນແລ້ວນາງກໍ່ບໍ່ສາມາດເລີ່ມກິນກ້ວຍຈາກເສົາອື່ນໃນຊົ່ວໂມງດຽວກັນ.

Koko ຕ້ອງການກິນກ້ວຍທັງ ໝົດ ພາຍໃນ H ຊົ່ວໂມງ. ພວກເຮົາຄວນຈະຊອກຫາຄ່າຕ່ ຳ ສຸດຂອງ K.

ຍົກຕົວຢ່າງ

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

ຄໍາອະທິບາຍ: 

ການແກ້ໄຂ leetcode ກັບ koko ກິນກ້ວຍ

Koko ຈະກິນກ້ວຍໃນທາງນີ້ຈະກິນກ້ວຍທັງ ໝົດ ພາຍໃນ 6 ຊົ່ວໂມງ:

ຊົ່ວໂມງ ທຳ ອິດ: 23

ຊົ່ວໂມງທີສອງ: 7

ຊົ່ວໂມງທີສາມ: 11

ຊົ່ວໂມງສີ່: 23

ຊົ່ວໂມງຫ້າ: 4

ຊົ່ວໂມງຫົກ: 20

ວິທີການແກ້ໄຂກ້ວຍກິນ ໝາກ ກ້ວຍ Leetcode Solution

ສິ່ງ ທຳ ອິດແລະ ສຳ ຄັນທີ່ສຸດໃນການແກ້ໄຂບັນຫານີ້ແມ່ນການ ນຳ ເອົາການສັງເກດ. ນີ້ແມ່ນການສັງເກດບາງຢ່າງ ສຳ ລັບໄລຍະຊອກຫາຂອງພວກເຮົາ:

  1. Koko ຕ້ອງກິນກ້ວຍຢ່າງ ໜ້ອຍ ໜຶ່ງ ກ້ວຍຕໍ່ຊົ່ວໂມງ. ສະນັ້ນນີ້ແມ່ນຄ່າຕ່ ຳ ສຸດຂອງ K. ໃຫ້ຊື່ວ່າມັນ ເລີ່ມຕົ້ນ
  2. ພວກເຮົາສາມາດ ຈຳ ກັດ ຈຳ ນວນກ້ວຍສູງສຸດທີ່ Koko ສາມາດກິນໄດ້ໃນ ໜຶ່ງ ຊົ່ວໂມງເຖິງ ຈຳ ນວນກ້ວຍທີ່ສຸດໃນຖັງທີ່ອອກຈາກເສົາທັງ ໝົດ. ສະນັ້ນນີ້ແມ່ນມູນຄ່າສູງສຸດຂອງ K. ໃຫ້ຊື່ວ່າມັນເປັນ ສິ້ນສຸດ.

ຕອນນີ້ພວກເຮົາມີໄລຍະເວລາຄົ້ນຫາຂອງພວກເຮົາ. ສົມມຸດວ່າຂະ ໜາດ ຂອງໄລຍະຫ່າງແມ່ນ ຄວາມຍາວ ແລະ ຈຳ ນວນເສົາແມ່ນ n.  ວິທີການທີ່ໂງ່ຈ້າອາດແມ່ນການກວດສອບແຕ່ລະຄ່າໃນແຕ່ລະໄລຍະ. ຖ້າວ່າ ສຳ ລັບຄຸນຄ່າຂອງກັອກໂກສາມາດກິນກ້ວຍທັງ ໝົດ ໃນຊົ່ວໂມງ H ປະສົບຜົນ ສຳ ເລັດແລ້ວຈຶ່ງເລືອກເອົາຕ່ ຳ ສຸດ. ຄວາມສັບສົນຂອງເວລາ ສຳ ລັບວິທີການທີ່ໂງ່ຈ້າຈະເປັນ Length * n ໃນກໍລະນີຮ້າຍແຮງທີ່ສຸດ.

ພວກເຮົາສາມາດປັບປຸງຄວາມສັບສົນຂອງເວລາໂດຍການ ນຳ ໃຊ້ຖານສອງຄົ້ນຫາແທນທີ່ Linear Search.

ຄວາມສັບສົນທີ່ໃຊ້ເວລາການນໍາໃຊ້ ການຄົ້ນຫາຖານສອງ ແນວທາງຈະເປັນທ່ອນ (ຄວາມຍາວ) * 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 * log (W)) ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງປະຕິບັດການຄົ້ນຫາຖານສອງລະຫວ່າງ ໜຶ່ງ ຫາ W ເຊິ່ງເວລານີ້ແມ່ນໃຊ້ເວລາ logW ແລະ ສຳ ລັບແຕ່ລະຄ່າ, ໃນການຄົ້ນຫາຖານສອງ, ພວກເຮົາ ກຳ ລັງຜ່ານການຈັດລຽງຕາມແຖວ. ດັ່ງນັ້ນອາເລກະທູ້ແມ່ນເວລາທີ່ໃຊ້ logW ເຊິ່ງມັນເຮັດໃຫ້ເວລາສັບສົນ n * logW. ທີ່ນີ້ n ແລະ W ແມ່ນ ຈຳ ນວນເສົາແລະ ຈຳ ນວນກ້ວຍສູງສຸດໃນຖັງ.

ຄວາມສັບສົນໃນອະວະກາດ

ຄວາມສັບສົນໃນພື້ນທີ່ຂອງລະຫັດຂ້າງເທິງແມ່ນ O (1) ເພາະວ່າພວກເຮົາ ກຳ ລັງໃຊ້ຕົວແປເພື່ອເກັບ ຄຳ ຕອບ.

ເອກະສານ