一、使结果不超过阈值的最小除数
给你一个整数数组 nums
和一个正整数 threshold
,你需要选择一个正整数作为除数,然后将数组里每个数都除以它,并对除法结果求和。(除法结果会向上取整 7/3=3)
请你找出能够使上述结果小于等于阈值 threshold
的除数中 最小 的那个。
思路:
使用二分答案来做(有固定模板)
1.
首先先判断一下要求的除数的范围。如果可以根据逻辑推断出来除数的左右边界,就可以减少复杂度。
2.
知道除数的范围之后,就可以使用二分法去查找最小的除数了。每次将mid作为参数传入check()函数中,判断当前这个除数是否满足题目要求,然后再去判断改变哪一个边界。
3.
最后返回left(left可能会不在合理的范围里面,需要判断)。注意:左闭右闭 左闭右开 左开右开 三种写法都可以。
代码:
class Solution {public int smallestDivisor(int[] nums, int threshold) {int maxValue=1;for(int num:nums){if(num>maxValue)maxValue=num;}int left=0;int right=maxValue+1;while(left+1<right){int mid=left+(right-left)/2;if(getSum(nums,mid)>threshold){left=mid;}else{right=mid;}}return right;}public int getSum(int[] nums, int div) {int res = 0;for (int num : nums) {if (num % div == 0)res += num / div;elseres += (num / div) + 1;}return res;}
}
二、二分答案模板:
class Solution {public int smallestDivisor(int[] nums, int threshold) {//1.找到要求变量的左右边界int left=0;int right=maxValue+1;//2.答案一定就在这个范围里面,每次取中间值进行检验。while(left+1<right){int mid=left+(right-left)/2;if(getSum(nums,mid)>threshold){left=mid;}else{right=mid;}}return right;}//3.检验的函数 根据题意来写,一般不会很难public int getSum(int[] nums, int div) {int res = 0;for (int num : nums) {if (num % div == 0)res += num / div;elseres += (num / div) + 1;}return res;}
}
三、制作m束花所需要的最少天数
给你一个整数数组 bloomDay
,以及两个整数 m
和 k
。
现需要制作 m
束花。制作花束时,需要使用花园中 相邻的 k
朵花 。
花园中有 n
朵花,第 i
朵花会在 bloomDay[i]
时盛开,恰好 可以用于 一束 花中。
请你返回从花园中摘 m
束花需要等待的最少的天数。如果不能摘到 m
束花则返回 -1 。
思路:
按照二分答案的模板来进行分析:
第一步:需要考虑出答案所在的范围区间,根据这个条件:1 <= bloomDay[i] <= 10^9(一般可以先进行分析 分析不出来就用题目中给的)
第二步:在所给的范围区间里面进行二分查找。
第三步:需要根据题目要求写一个检验函数:比如在这道题中
需要制作m束花朵,并且每一束必须取连续的k朵花做,但是每一朵花只有在时间>bloomDay[i]才会开。
代码:
class Solution {public int minDays(int[] bloomDay, int m, int k) {// m为需要的花朵数 需要看bloomDay数组里面 在time天的时候有多少朵盛开// 对天数进行二分 最小: 最大:int left = 1;int right = 1000000001;while (left <= right) {int mid = left + (right - left) / 2;if (getFlowers(bloomDay, k, mid) < m) {left = mid + 1;} else {right = mid - 1;}}return left==1000000002?-1:left;}public int getFlowers(int[] bloomDay, int k, int time) {int flowers = 0;int left = 0;int right = 0;while (right < bloomDay.length) {if (bloomDay[right] > time) {left = right + 1;}if (right - left + 1 == k) {flowers++;left = right + 1;}right++;}return flowers;}
}