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

前言

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

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

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

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

请看代码

class Solution { public int smallestDivisor(int[] nums, int threshold) { // 二分查找的范围从 1 到数组最大值 int l = 1, r = Integer.MAX_VALUE; while (l <= r) { // l <= r int 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  这也是一个向上取整的公式

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.算出有多少堆糖果,加入 数量大于孩子的数量,说明每一堆糖果的数量还可以加,反之,就要削减每一堆糖果的数量

public class Solution { public int maximumCandies(int[] candies, long k) { long sum = 0; // 计算总糖果数 for (int i = 0; i < candies.length; i++) { sum += candies[i]; } // 如果糖果总数小于小孩数，直接返回 0 if (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因子的数量.

代码如下 :

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); } } } 结尾

今天就记录到这里,谢谢大家