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

✨今日算法三题

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

文章目录

• ✨今日算法三题
• 1.特殊数组的特征值
• • 题目描述
  • 思路详解
  • 代码与结果
• 2.在D天内送达包裹的能力
• • 题目描述
  • 思路详解
  • 代码与结果
• 3.咒语和药水的成功对数
• • 题目描述
  • 思路详解
  • 代码与结果
• ✨总结

1.特殊数组的特征值

题目描述

思路详解

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

代码与结果

class Solution {    public int specialArray(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;     } else if (x < n - idx) { // 大于等于x的元素太多了，所以下一轮搜索要增大x的取值范围  left = x + 1;     } else { // 反之，减少x的取值范围  right = x - 1;     } } return -1;    } private static int binarySearch(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 时，我们就需要将最后一个包裹拿出来，安排在新的一天，并继续往下遍历。当我们遍历完整个数组后，就得到了最少需要运送的天数。

代码与结果

class Solution {    public int shipWithinDays(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型，避免错误哦。

代码与结果

class Solution {    public int[] successfulPairs(int[] spells, int[] potions, long success) { int[] ans = new int[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;    }}

✨总结

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

$原创不易，还希望各位大佬支持一下$

$点赞，你的认可是我创作的动力！$

$收藏，你的青睐是我努力的方向！$

$评论，你的意见是我进步的财富！$