Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-04-03 01:37:21
2300. Successful Pairs of Spells and Potions
给定两个阵列spells和points,前者表示多个咒语的强度,后者表示多个药剂的强度,若
咒语和药剂相乘大于success则这一组咒语和药剂配对成功,返回一个长度为spells的阵列
pairs,其中 pairs[i] 是能与第 i 个咒语配对成功的药剂数量。
Example:
Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:
- 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
- 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
- 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
Thus, [4,0,3] is returned.
思路:
1.最简单的方法就是两个阵列相互配对并计算数量,但是咒语和药剂的长度很大这样做
肯定会吃TLE。
2.我们可以先把药剂的强度排序好,每个咒语使用二分搜索找到最小且满足success的
药剂,这样这个索引的右边全部都是配对成功的药剂,若potions.length = n
满足数量就会是 n - index,如果最右边(最大)的药剂和咒语不满足则二分搜索直接
返回n不用继续找寻。
Java Code:
作者: JIWP (JIWP)   2022-04-03 01:37:00
大师
作者: Firstshadow (IamCatづミ'_'ミづ)   2023-04-03 01:38:00
大师
作者: Che31128 (justjoke)   2023-04-03 01:39:00
大师
作者: pomelotea (玖二共侍 一花臭表)   2023-04-03 01:54:00
开始binary search week了
作者: pandix (面包屌)   2023-04-03 02:33:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com