የኮኮ መመገቢያ ሙዝ Leetcode መፍትሔ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ ፌስቡክ
የሁለትዮሽ ፍለጋ

የችግር እሴት

በችግሩ ውስጥ “ኮኮ መብላት ሙዝ” በእያንዳንዱ ክምር ውስጥ የሙዝ ቁጥርን የያዘ የቁጥር n ብዛት ይሰጠናል ፡፡ በአንድ ሰዓት ውስጥ ኮኮ ቢበዛ ኬ ሙዝ መብላት ይችላል ፡፡ በዚህ ጊዜ ክምር ከ K ሙዝ ያነሰ ከሆነ ኮኮ የዚያን ክምር ሙዝ በሙሉ ካጠናቀቀች በተመሳሳይ ሰዓት ከሌላ ክምር ሙዝን መብላት አትችልም ፡፡

ኮኮ ሁሉንም ሙዝ በ H ሰዓታት ውስጥ መብላት ይፈልጋል ፡፡ የ K. ዝቅተኛውን እሴት እናገኛለን ተብሎ ይጠበቃል

ለምሳሌ

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

ማብራሪያ: 

leetcode መፍትሄ ለኮኮ መብላት ሙዝ

ኮኮ ሁሉንም ሙዝ በ 6 ሰዓታት ውስጥ ለመብላት በዚህ መንገድ ሙዝ ይበላል-

የመጀመሪያ ሰዓት: 23

ሁለተኛ ሰዓት 7

ሦስተኛው ሰዓት 11

አራተኛ ሰዓት 23

አምስተኛው ሰዓት 4

ስድስተኛው ሰዓት: 20

ለኮኮ መብላት ሙዝ Leetcode መፍትሄ አቀራረብ

ይህንን ችግር ለመፍታት የመጀመሪያው እና በጣም አስፈላጊው ነገር ምልከታዎችን ማምጣት ነው ፡፡ ለፍለጋ ክፍተታችን ጥቂት ምልከታዎች እነሆ-

  1. ኮኮ በሰዓት ቢያንስ አንድ ሙዝ መብላት አለበት ፡፡ ስለዚህ ይህ የ K. ዝቅተኛው እሴት ነው እንጠራው እንደ መጀመሪያ
  2. ከሁሉም ክምርዎች ውስጥ በአንድ ክምር ውስጥ ከፍተኛውን የሙዝ ብዛት ኮኮ በአንድ ሰዓት ውስጥ መመገብ እንችላለን ፡፡ ስለዚህ ይህ የ K. ከፍተኛው እሴት ነው እስቲ እንጠራው ጨርስ

አሁን የፍለጋ ክፍተታችን አለን ፡፡ የጊዜ ክፍተቱ መጠን ነው እንበል ርዝመት እና የተከመረ ቁጥር ነው n.  የዋህነት አቀራረብ በእያንዲንደ የጊዜ ክፍተት ውስጥ እያንዲንደ እሴትን ሇመፈተሽ ሊሆን ይችላል ፡፡ ለኮ ኮኮ እሴት በ H ሰዓት ውስጥ ሁሉንም ሙዝ በተሳካ ሁኔታ መብላት ከቻለ አነስተኛውን ይምረጡ ፡፡ ለሞኝ አቀራረብ የጊዜ ውስብስብነት በከፋ ሁኔታ ውስጥ ርዝመት * n ይሆናል ፡፡

በመስመራዊ ፍለጋ ምትክ የሁለትዮሽ ፍለጋን በመጠቀም የጊዜ ውስብስብነትን ማሻሻል እንችላለን ፡፡

የጊዜን ውስብስብነት በመጠቀም የሁለትዮሽ ፍለጋ አቀራረብ ምዝግብ ማስታወሻ (ርዝመት) * 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

ለኮኮ መብላት ሙዝ የጃቫ ኮድ

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

የኮኮ መመገቢያ ሙዝ የሌትኮድ መፍትሄ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ከላይ ያለው ኮድ የጊዜ ውስብስብነት ነው ኦ (n * ምዝግብ ማስታወሻ (W)) በአንዱ እና በ W መካከል የሁለትዮሽ ፍለጋን ስለምናካሂድ ይህ የምዝግብ ማስታወሻ ጊዜ ይወስዳል እና ለእያንዳንዱ እሴት በሁለትዮሽ ፍለጋ ውስጥ የቁለሎችን ስብስብ እናቋርጣለን ፡፡ ስለዚህ የተቆለሉ ድርድር ጊዜውን ውስብስብ ያደርገዋል n * logW ያደርገዋል ፡፡ እዚህ n እና W የተቆለሉ ቁጥሮች እና በአንድ ክምር ውስጥ ከፍተኛው የሙዝ ብዛት ናቸው ፡፡

የቦታ ውስብስብነት

ከላይ ያለው ኮድ የቦታ ውስብስብነት ነው ኦ (1) ምክንያቱም መልሱን ለማከማቸት የምንጠቀምበት ተለዋዋጭ ብቻ ነው ፡፡

ማጣቀሻዎች