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