2022/01/20 - 875. Koko Eating Bananas

运用了二分查找法，稍微根据题目变动一点点。

Description¶

875. Koko Eating Bananas

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 Output: 4

Example 2:

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

Example 3:

Input: [1,1,1,999999999] Output: 142857143

这道题呢稍微有点 tricky，我一开始想的是找到话费的时间刚好等于h的数值就行了，结果[1,1,1,999999999]输入瞬间打我脸，所以我就想，如果数字非常大的情况下，肯定是会有很多种输出结果是一样，而这道题是要找最小的那个值，所以当我计算到total值等于h的时候，无脑将right = mid - 1，然后继续尝试，直到left和right相等的时候，就是最小值啦。

Solution¶

ScalaJava

object Solution {
    def minEatingSpeed(piles: Array[Int], h: Int): Int = {
        val dummy = piles.sorted
        val k = dummy(dummy.length - 1)
        var left = 1
        var right = k
        while (left <= right) {
        val mid = (left + right) / 2
        var total: Int = 0
        for (i <- piles) {
            total = total + (if (i % mid > 0) i / mid + 1 else i / mid)
        }
        if (total == h) {
            right = mid - 1
        } else if (total > h) {
            left = mid + 1
        } else {
            right = mid - 1
        }
        }
        right + 1
    }
}

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        // 首先找到piles中的最大值
        int right = 0;
        for (int p : piles) {
            right = Math.max(right, p);
        }
        int left = 1;
        // 二分查找
        while (left <= right) {
            int total = 0;
            int mid = (left + right) / 2;
            for (int p : piles) {
                total += p % mid > 0 ? p / mid + 1 : p / mid;
            }
            if (total == h) {
                right = mid - 1;
            } else if (total > h) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right + 1;
    }
}

2022/01/20 - 875. Koko Eating Bananas

Description¶

Solution¶

评论