“This is the seventh day of my participation in the First Challenge 2022.

describe

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8 piles: 4Copy the code

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30
Copy the code

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23
Copy the code

Note:

1 <= piles.length <= 10^4
piles.length <= h <= 10^9
1 <= piles[i] <= 10^9
Copy the code

parsing

Koko likes eating bananas. There were n piles of bananas and pile I had [I] bananas. The guards are gone. They’ll be back in a few hours.

Koko can determine the rate at which she eats bananas at k per hour. Every hour she would choose a pile of bananas and eat k bananas from that pile. If there are less than k bananas in the pile, she will eat all of them and will not eat any more bananas for that hour. Koko likes to eat slowly, but still wants to finish the banana before the guards return. Returning the minimum integer k allows her to eat all the bananas in h hours.

The simple way to use violence was to read that if the length of the piles was equal to H, we could only eat Max piles per hour and go straight back to Max piles. Otherwise we calculated sum(piles)//h, the smallest possible value for result, and kept adding up to one to see if it would be done in exactly P hours. There had to be a number to fit the problem, so we just returned result.

But this is bound to run out of time because the constrained piles have a 10^4 length and each value piles[I] has a maximum of 10^9, meaning this solution will run out of time with a worst-case complexity of O(10^4 * 10^9).

answer

 class Solution(object):
    def minEatingSpeed(self, piles, h):
        """
        :type piles: List[int]
        :type h: int
        :rtype: int
        """
        if h == len(piles):
            return max(piles)
        
        result = sum(piles)//h
        while result > 0:
            tmp = 0
            for p in piles:
                tmp += (p // result + (0 if p % result == 0 else 1))
            if tmp == h:
                return result
            result += 1           	      
		
Copy the code

The results

Time Limit Exceeded
Copy the code

parsing

In fact, from the thought above, it was clear that the best thing to read through the piles was to find out how fast they could eat bananas per hour, k, and we could use a dichotomy because the slowest speed must have been one banana per hour and the fastest must have been Max bananas per hour, Therefore, we use dichotomy to locate k, the slowest number of bananas to eat within h hours. The overall code framework is the same as the above, and only mn, Mx and mid used in dichotomy need to be constantly changed.

When the time complexity was O(nlogm), N was the length of the piles and M was the Max, the key to the test was the dichotomous values.

answer

class Solution(object):
    def minEatingSpeed(self, piles, h):
        """
        :type piles: List[int]
        :type h: int
        :rtype: int
        """
        if h == len(piles):
            return max(piles)
        mn = 1
        mx = max(piles)
        while mn < mx:
            mid = (mx + mn) // 2
            time = 0
            for p in piles:
                time += p // mid + (0 if p%mid==0 else 1)
            if time <= h:
                mx = mid
            else:
                mn = mid + 1
        return mn
Copy the code

The results

Given in the linked list. Memory Usage: 10000 ms Given in the Python online submissions for Koko Eating Bananas.Copy the code

The original link

Leetcode.com/problems/ko…

Your support is my biggest motivation