0


【算法刷题】—7.12二分查找应用,数组处理

  • 🧛‍♂️个人主页:杯咖啡
  • 💡进步是今天的活动,明天的保证!
  • ✨目前正在学习:SSM框架,算法刷题
  • 🙌牛客网,刷算法过面试的神级网站,用牛客你也牛。 👉免费注册和我一起学习刷题👈
  • 🐳希望大家多多支持🥰一起进步呀!
  • 😎Love is the one thing we’are capable of perceiving that transcends time and space. 爱是我们唯一能够感知的可以超越时空维度的事物。-《星际穿越》

✨今日算法三题

1.特殊数组的特征值
2.在D天内送达包裹的能力
3.咒语和药水的成功对数


文章目录


1.特殊数组的特征值

题目描述

在这里插入图片描述

思路详解

看到本题,首先思考需要排序,然后查找,这里为了效率采用二分查找。
假设定义x=(left+riht)/ 2,每次查找到nums中第一个大于等于X的元素下标,判断大于等于X的个数与X的关系,进行分情况修改左右边界。

代码与结果

classSolution{publicintspecialArray(int[] nums){Arrays.sort(nums);int n = nums.length;int left =0, right = n;while(left <= right){int x =(left + right)>>1;int idx =binarySearch(nums, x);// nums中第一个大于等于x的元素位置if(x == n - idx){return x;}elseif(x < n - idx){// 大于等于x的元素太多了,所以下一轮搜索要增大x的取值范围
                left = x +1;}else{// 反之,减少x的取值范围
                right = x -1;}}return-1;}privatestaticintbinarySearch(int[] nums,int x){int left =0, right = nums.length -1;while(left <= right){int mid =(left + right)>>1;int val = nums[mid];if(val >= x){
                right = mid -1;}else{
                left = mid +1;}}return left;}}

在这里插入图片描述

2.在D天内送达包裹的能力

题目描述

在这里插入图片描述

思路详解

假设当船的运载能力为 x 时,我们可以在days 天内运送完所有包裹,那么只要运载能力大于 x,我们同样可以在 days 天内运送完所有包裹:我们只需要使用运载能力为 x时的运送方法即可。

由于必须按照数组weights 中包裹的顺序进行运送,因此我们从数组 weights 的首元素开始遍历,将连续的包裹都安排在同一天进行运送。当这批包裹的重量大于运载能力 x 时,我们就需要将最后一个包裹拿出来,安排在新的一天,并继续往下遍历。当我们遍历完整个数组后,就得到了最少需要运送的天数。

代码与结果

classSolution{publicintshipWithinDays(int[] weights,int days){// 确定二分查找左右边界int left =Arrays.stream(weights).max().getAsInt(), right =Arrays.stream(weights).sum();while(left < right){int mid =(left + right)/2;// need 为需要运送的天数// cur 为当前这一天已经运送的包裹重量之和int need =1, cur =0;for(int weight : weights){if(cur + weight > mid){++need;
                    cur =0;}
                cur += weight;}if(need <= days){
                right = mid;}else{
                left = mid +1;}}return left;}}

在这里插入图片描述

3.咒语和药水的成功对数

题目描述

在这里插入图片描述

思路详解

本题采用二分查找的方法进行解题。
首先我们对药水的数组进行排序,其次我们遍历咒术数组,利用二分查找的思想在药水数组中查找,与成功值最接近的数值,存入到答案数组中。
有个小细节,判断时候1l * power * potions[mid] < success 这样做是为了把数字转化为long型,避免错误哦。

代码与结果

classSolution{publicint[]successfulPairs(int[] spells,int[] potions,long success){int[] ans =newint[spells.length];Arrays.sort(potions);for(int i =0; i < spells.length; i++){int power = spells[i];int left =0;int right = potions.length -1;while(left <= right){int mid = left +(right - left)/2;if(1l* power * potions[mid]< success){
                    left = mid +1;}else{
                    right = mid -1;}}
            ans[i]= potions.length - left;}return ans;}}

在这里插入图片描述


✨总结

今天主要集中在二分查找的应用,希望小伙伴通过今天的习题可以体验到二分查找的好处,可以更加熟练的应用哦!!!!

      原
     
     
      创
     
     
      不
     
     
      易
     
     
      ,
     
     
      还
     
     
      希
     
     
      望
     
     
      各
     
     
      位
     
     
      大
     
     
      佬
     
     
      支
     
     
      持
     
     
      一
     
     
      下
     
    
   
   
    \textcolor{blue}{原创不易,还希望各位大佬支持一下}
   
  
 原创不易,还希望各位大佬支持一下


 
  
   
    
     
      点
     
     
      赞
     
     
      ,
     
     
      你
     
     
      的
     
     
      认
     
     
      可
     
     
      是
     
     
      我
     
     
      创
     
     
      作
     
     
      的
     
     
      动
     
     
      力
     
     
      !
     
    
   
   
    \textcolor{green}{点赞,你的认可是我创作的动力!}
   
  
 点赞,你的认可是我创作的动力!


 
  
   
    
     
      收
     
     
      藏
     
     
      ,
     
     
      你
     
     
      的
     
     
      青
     
     
      睐
     
     
      是
     
     
      我
     
     
      努
     
     
      力
     
     
      的
     
     
      方
     
     
      向
     
     
      !
     
    
   
   
    \textcolor{green}{收藏,你的青睐是我努力的方向!}
   
  
 收藏,你的青睐是我努力的方向!


 
  
   
    
     
      评
     
     
      论
     
     
      ,
     
     
      你
     
     
      的
     
     
      意
     
     
      见
     
     
      是
     
     
      我
     
     
      进
     
     
      步
     
     
      的
     
     
      财
     
     
      富
     
     
      !
     
    
   
   
    \textcolor{green}{评论,你的意见是我进步的财富!}
   
  
 评论,你的意见是我进步的财富!

本文转载自: https://blog.csdn.net/muzi_longren/article/details/125735530
版权归原作者 风铃听雨~ 所有, 如有侵权,请联系我们删除。

“【算法刷题】&mdash;7.12二分查找应用,数组处理”的评论:

还没有评论