Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/04/03 01:37)推噓3(3推 0噓 2→)

留言5則, 5人參與討論串279/719 (看更多)

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： ------------------------------------------------------------ class Solution { public int[] successfulPairs(int[] spells, int[] potions, long success) { long[] arr = new long[potions.length]; Arrays.sort(potions); for (int i = 0; i < potions.length; i++) { arr[i] = potions[i]; } int[] ans = new int[spells.length]; for (int i = 0; i < spells.length;i++) { int index = search(arr, spells[i], success); ans[i] = potions.length - index; } return ans; } private int search(long[] arr, long spell, long target) { int n = arr.length; if (arr[n - 1] * spell < target) { return n; } int l = 0; int r = n - 1; while (l < r) { int mid = (l + r)/2; if (arr[mid] * spell >= target) { r = mid; } else { l = mid + 1; } } return r; } } ------------------------------------------------------------ -- https://i.imgur.com/PIoxddO.jpg