刷题日记——部分二分算法题目分享

前言

咱们紧跟上一期结合时间复杂度浅谈二分法的好处, 并分享部分二分题目(将持续更新题目,绝对值你一个收藏)-CSDN博客

笔者接着分享一些刷过的关于二分算法的题目.

第一题

1283. 使结果不超过阈值的最小除数 - 力扣（LeetCode）

这道题就是典型的二分查找答案,我们通过二分算法,找到最小的适配题意的值,但是具体到写法就不是简单的背模板了,不然笔者也不会分享

请看代码

java">class Solution {public int smallestDivisor(int[] nums, int threshold) {// 二分查找的范围从 1 到数组最大值int l = 1, r = Integer.MAX_VALUE;while (l <= r) {  // l <= rint mid = l + (r - l) / 2;  // 防止溢出int sum = 0;for (int i = 0; i < nums.length; i++) {// 模拟向上取整sum += (nums[i] + mid - 1) / mid;}if (sum <= threshold) {r = mid - 1;  // 如果和小于等于 threshold，说明 mid 可以是一个合适的除数，继续寻找更小的除数} else {l = mid + 1;  // 如果和大于 threshold，说明 mid 太小，需要增大除数}}return l;  // 返回找到的最小除数}
}

我们这里需要手动模拟一个向上取整

因为

Math.ceil 不适用于整数运算：Math.ceil 是用于浮点数的，而你是对整数进行操作的。实际上，你可以用 (num + d - 1) / d 来模拟向上取整，因为这对于整数来说就等于向上取整。

(num + d - 1) / d 这也是一个向上取整的公式

java"> if (sum <= threshold) {r = mid - 1;  // 如果和小于等于 threshold，说明 mid 可以是一个合适的除数，继续寻找更小的除数} else {l = mid + 1;  // 如果和大于 threshold，说明 mid 太小，需要增大除数}}

第二题 2226. 每个小孩最多能分到多少糖果 - 力扣（LeetCode）

这道题是要求我们给小孩子分糖果, 要求糖果的数量要一样 ,但是没有要求要把糖果瓜分干净.

本人的思路大致如下

1.先算出糖果的总数,如果总数甚至比小孩子的人数少,那么,直接return 0 就好了

2.假设没有限制条件,那么,每个孩子最多可以分 sum/k 个糖果,这就是我们二分算法的右边界,最好的条件下也只能分 sum/k个.

3.取中间值,然后遍历 candies数组,算出每个元素的糖果,分 mid 数量堆,能分出来多少堆糖果

4.算出有多少堆糖果,加入数量大于孩子的数量,说明每一堆糖果的数量还可以加,反之,就要削减每一堆糖果的数量

java">public class Solution {public int maximumCandies(int[] candies, long k) {long sum = 0;// 计算总糖果数for (int i = 0; i < candies.length; i++) {sum += candies[i];}// 如果糖果总数小于小孩数，直接返回 0if (sum < k) {return 0;}// 二分查找的边界int l = 1;int r = (int) (sum / k); // 最大的可能糖果数为总糖果数除以小孩数while (l <= r) {int mid = l + (r - l) / 2; // 中间值long kid = 0;// 计算可以分配的子堆数量for (int i = 0; i < candies.length; i++) {kid += candies[i] / mid; // 每堆糖果可以分成 candies[i] / mid 个小堆}if (kid < k) {r = mid -1;   //小于 ,说明要削减数量} else {l = mid +1 ; // 大于,可以增加数量}}return r; // 返回最大糖果数}
}

第三题6.求阶乘 - 蓝桥云课

这一题二分是一种辅助手段,可以减少我们的复杂度, 本题的核心思想还是检查一个数的5因子的数量.

代码如下 :

java">import java.util.Scanner;public class Demo6
{static  long k;static  long  cal(long num){long x = 0;while(num!=0)// 5 作为因子,能推测出有几个0结尾{x+=num/5;num/=5;}return x;// 算出有几个0结尾}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);k = scanner.nextLong();long l = 1;long r =Long.MAX_VALUE-1;while(l<r){long mid = l+(r-l)/2;long n = cal(mid);if(n>=k)// 如果 n>=k 说明目前的数字比较大,或者还有更小更合适的{r = mid;}else// 目前的数字不行,需要增大{l = mid+1;}}if(cal(r) != k){System.out.println(-1);}else{System.out.println(r);}}
}