LeetCode algorithm learning – binary search – love to eat the banana Ke

Hello everyone today to share with you the next LeetCode medium difficulty of the title “Love to eat bananas”](leetcode-cn.com/problems/co…)

Here is mainly to share ideas and comments, for you to better understand the problem solution, the code part is to refer to LeetCode translated into javascript code,

The title

Coco likes to eat bananas. There are N piles of bananas here and piles[I] piles of bananas in pile I. The guards have left and will be back in hours.

Coco can decide how fast she eats the banana, in roots per hour. Every hour, she will choose a pile of bananas and eat K of them. If the pile of bananas is less than K, she will eat all the bananas in the pile, and then she will not eat any more bananas for an hour.

Coco likes to eat slowly, but still wants to eat all the bananas before the guards get back.

Returns the minimum speed K at which she can eat all bananas in H hours (K is an integer).

Example 1: Input: Piles = [3,6,7,11], H = 8 Output: 4 Example 2: Input: PILES = [30,11,23,4,20], H = 5 Output: 30 Example 3: Input: Piles = [30,11,23,4,20], H = 6Copy the code

Analysis of the

1. There are N piles of bananas to piles[I] and if there are less than K bananas to piles it takes an hour so the amount of time to piles is Math.ceil(PILES [I]/k)

2. Since the guards will return in hours, the total time taken is t<=H

3. The required value is the minimum speed K, so T must be as large as possible.

4. K is at least 1 without considering H and at most math.max (Piles)

There are two ways to do it

1. The method of violence

2. Binary search

Solution a:Violence law

Train of thought1.K belong to [1,max(piles)]
2.Iterate to find the smallest K */var minEatingSpeed = function (piles, h) {
  let maxSpeed = Math.max(... piles);// Find the range of k values
  for (let k = 1; k <= maxSpeed; k++) {
    let t = 0;
    // It takes a lot of time to figure it out
    for (let j = 0; j < piles.length; j++) {
      t += Math.ceil(piles[j] / k);
    }
    // Return the minimum value of k when the condition is met
    if (t <= h) {
      returnk; }}};/* Complexity time O(n^2) space O(1) */
Copy the code

Method 2:dichotomy

Train of thought1.Since K belongs to [1,max(piles)]
2.[1, Max (Piles)] is an ascending array and it was one of the lookups that gave us the idea of dichotomy3.But the dichotomous cyclic condition here is no longerwhile(l < = r) insteadwhile(pass(mid)), we use this function to determine whether k is on the left or the right */var minEatingSpeed = function (piles, h) {
  let l = 0;
  let r = Math.max(... piles);while (l <= r) {
    const mid = Math.floor(l + (r - l) / 2);
    // Since k is the minimum value, so if passed, then k can be smaller, so the right side of the convergence interval
    if (pass(mid)) {
      r = mid - 1;
    } else {
      l = mid + 1; }}return l;

  // Obtain the condition of passing
  function pass(mid) {
    let t = 0;
    for (let j = 0; j < piles.length; j++) {
      t += Math.ceil(piles[j] / mid);
    }

    // Return true if the condition is met and false otherwise
    returnt <= h; }};/* complexity time O(nlogn) space O(1) */
Copy the code

conclusion

So this is a question about how to use dichotomous search, and you need to understand the relationships between the three k H Piles in order to understand how to use dichotomous search

You can look at a column I share (front-end algorithm) there are more questions about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me a like, thank you very much

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Part of the material in this article comes from the network. If there is infringement, please contact delete, [email protected]