875. Koko Eating Bananas & 1760. Minimum Limit of Balls in a Bag
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: 4Example 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30Example 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23Constraints:
1 <= piles.length <= 104piles.length <= h <= 1091 <= piles[i] <= 109
My Solutions:
题目要求找到可以让koko在管理员发现之前把所有香蕉吃完、且每次吃的数量最少的方案。每次最少只吃一个。每次最多可以吃到每个pile的最大值。因此，在1和最大值中，做binary search，找到一个最小的可以吃完并且不被发现的方案。
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int max = -1, min = 1;
for (int p : piles) {
max = Math.max(max, p);
}
while (min + 1 < max) {
int mid = min + (max - min) / 2;
if (canFinishEatingBeforeGuardReturns(mid, piles, h)) max = mid;
else min = mid;
}
// 先检查左边，因为想要让koko每次尽量少吃
if (canFinishEatingBeforeGuardReturns(min, piles, h)) return min;
return max;
}
private boolean canFinishEatingBeforeGuardReturns(int num, int[] piles, int h) {
int hours = 0;
for (int p : piles) {
hours += p / num;
if (p % num != 0) hours++;
}
if (hours <= h) return true;
else return false;
}
}Minimum Limit of Balls in a Bag
You are given an integer array nums where the ith bag contains nums[i] balls. You are also given an integer maxOperations.
You can perform the following operation at most maxOperations times:
Take any bag of balls and divide it into two new bags with a positive number of balls.
For example, a bag of
5balls can become two new bags of1and4balls, or two new bags of2and3balls.
Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations.
Return the minimum possible penalty after performing the operations.
Example 1:
Input: nums = [9], maxOperations = 2
Output: 3
Explanation:
- Divide the bag with 9 balls into two bags of sizes 6 and 3. [9] -> [6,3].
- Divide the bag with 6 balls into two bags of sizes 3 and 3. [6,3] -> [3,3,3].
The bag with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.Example 2:
Input: nums = [2,4,8,2], maxOperations = 4
Output: 2
Explanation:
- Divide the bag with 8 balls into two bags of sizes 4 and 4. [2,4,8,2] -> [2,4,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,4,4,4,2] -> [2,2,2,4,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
The bag with the most number of balls has 2 balls, so your penalty is 2, and you should return 2.Constraints:
1 <= nums.length <= 1051 <= maxOperations, nums[i] <= 109
My Solutions:
和koko吃香蕉有些类似。最理想的情况是每个袋子里只有一个球，最不理想的情况是不做任何移动，惩罚数是袋子里最多球的数量。因此，在1和最大值中，做binary search，找到一个最小的惩罚数，且需要移动的次数不超过maxOperation。
如果袋子里的球n小于惩罚数mid，则不需要做移动。如果n大于惩罚数，则需要操作(n-1)/mid次，才能让袋子里的球平均放在很多袋子里，每个袋子里球的数量都小于等于mid。比如mid=3
6
3,3
1
7
3,3,1
2
8
3,3,2
2
class Solution {
public int minimumSize(int[] nums, int maxOperations) {
int max = -1, min = 1;
for (int n : nums) max = Math.max(max, n);
while (min + 1 < max) {
int mid = min + (max - min) / 2;
if (canDoIt(nums, mid, maxOperations)) max = mid;
else min = mid;
}
// 先检查左边，因为想要惩罚的数尽量的小
if (canDoIt(nums, min, maxOperations)) return min;
return max;
}
private boolean canDoIt(int[] nums, int mid, int maxOperations) {
int moves = 0;
for (int n : nums) {
if (n > mid) moves += (n - 1) / mid;
}
if (moves > maxOperations) return false;
else return true;
}
}Last updated