本文主要是介绍LeetCode2300咒语和药水的成功对数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
解析
先对药水排序后每个咒语去二分查找最低满足的药水的位置。
class Solution {public int[] successfulPairs(int[] spells, int[] potions, long success) {int n = spells.length, m = potions.length;Arrays.sort(potions);for (int i = 0; i < n; i++) {long target = (success - 1) / spells[i];if (target < potions[m - 1]) {spells[i] = m - binarySearch(potions, (int) target + 1);} else{spells[i] = 0;}}return spells;}private int binarySearch(int[] nums, int target) {int left = 0, right = nums.length;while (left < right) {int mid = left + ((right - left) >> 1);if (nums[mid] < target) {left = mid + 1;} else {right = mid;}}return left;}
}
这题还有更快的解法，也就是示例代码最快的那个。代码首先找能满足的最低条件，相当于是一个剪枝操作，然后对于能满足的都在数组中加一，最后求前缀和，因为当前能够满足那么它之前的一定能满足，最后对应查找就行了。
class Solution {static int inf = (int)1e5;public int[] successfulPairs(int[] spells, int[] potions, long success) {int max = 0;for (int x:spells) if(x > max) max = x;int minPotion = (int)Math.min(inf, (success+max-1) / max);int[] count = new int[max + 1];for (int potion : potions) {if (potion >= minPotion) ++count[(int)((success + potion - 1) / potion)];}for (int i = 1; i <= max; i++)count[i] += count[i - 1];int n = spells.length; int[] result = new int[n]; for (int i = 0; i < n; i++) result[i] = count[spells[i]];return result;}
}
这篇关于LeetCode2300咒语和药水的成功对数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
