付費限定

咒語和藥水的成功配對數 Successful Pairs of Spells&Potions_LC 2300 精選75題

更新於 發佈於 閱讀時間約 5 分鐘

題目敘述

題目會給我們兩個輸入陣列spells咒語、potions藥水,還有一個參數success。

咒語和藥水相乘的值 >= success就是一個成功配對

請問每個咒語能夠形成的成功配對數有多少?

以陣列的形式輸出返回答案。


題目的原文敘述


測試範例

Example 1:

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.

Example 2:

Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Explanation:
- 0th spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
- 1st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful.
- 2nd spell: 2 * [8,5,8] = [16,10,16]. 2 pairs are successful.
Thus, [2,0,2] is returned.

約束條件

Constraints:

  • n == spells.length

咒語陣列的長度為n。

  • m == potions.length

藥水陣列的長度為m。

  • 1 <= n, m <= 10^5

輸入陣列的長度都介於1~十萬。

  • 1 <= spells[i], potions[i] <= 10^5

輸入陣列的元素值都介於1~十萬。

  • 1 <= success <= 10^10

參數success介於1~一百億。


演算法 排序 +二分搜尋

除了傳統的暴力搜索配對之外,還有一個比較高效率的排序+二分搜尋演算法。

先把potion藥水陣列從小到大排序
這是為了後續的二分搜尋鋪路,滿足已排序的性質

以行動支持創作者!付費即可解鎖
本篇內容共 2024 字、1 則留言,僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容,可能因為尚未登入,或沒有該房間的查看權限。
留言
avatar-img
留言分享你的想法!
小松鼠-avatar-img
發文者
2024/06/01
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/08/14
題目敘述 Find K-th Smallest Pair Distance 給定一個輸入陣列nums和 參數k。 請找出第k小的pair distance是多少? pair distance定義為 abs( nums[i] - nums[j]), i 不等於j 也就是任意兩陣列元素差值的絕對值
Thumbnail
2024/08/14
題目敘述 Find K-th Smallest Pair Distance 給定一個輸入陣列nums和 參數k。 請找出第k小的pair distance是多少? pair distance定義為 abs( nums[i] - nums[j]), i 不等於j 也就是任意兩陣列元素差值的絕對值
Thumbnail
2024/05/27
給定一個輸入非負整樹陣列nums,請找出k值,使得陣列中恰好有k個元素大於等於 k。如果無解,回傳-1。尋找k值的方法包括排序法和二分搜尋法,時間複雜度都為O(n log n),空間複雜度為O(1)。關鍵知識點是當解空間具有遞增或遞減的性質時,可以用二分搜尋法加快搜尋效率。
Thumbnail
2024/05/27
給定一個輸入非負整樹陣列nums,請找出k值,使得陣列中恰好有k個元素大於等於 k。如果無解,回傳-1。尋找k值的方法包括排序法和二分搜尋法,時間複雜度都為O(n log n),空間複雜度為O(1)。關鍵知識點是當解空間具有遞增或遞減的性質時,可以用二分搜尋法加快搜尋效率。
Thumbnail
2024/03/19
這篇文章,會帶著大家複習以前學過的二分搜尋法(Binary Search)框架, 並且以二分搜尋法的概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個實用的演算法框架。 Binary search 二分搜尋法框架 用途: 在已經排序好的數列中尋找目標值。
Thumbnail
2024/03/19
這篇文章,會帶著大家複習以前學過的二分搜尋法(Binary Search)框架, 並且以二分搜尋法的概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個實用的演算法框架。 Binary search 二分搜尋法框架 用途: 在已經排序好的數列中尋找目標值。
Thumbnail
看更多
你可能也想看
Thumbnail
介紹朋友新開的蝦皮選物店『10樓2選物店』,並分享方格子與蝦皮合作的分潤計畫,註冊流程簡單,0成本、無綁約,推薦給想增加收入的讀者。
Thumbnail
介紹朋友新開的蝦皮選物店『10樓2選物店』,並分享方格子與蝦皮合作的分潤計畫,註冊流程簡單,0成本、無綁約,推薦給想增加收入的讀者。
Thumbnail
當你邊吃粽子邊看龍舟競賽直播的時候,可能會順道悼念一下2300多年前投江的屈原。但你知道端午節及其活動原先都與屈原毫無關係嗎?這是怎麼回事呢? 本文深入探討端午節設立初衷、粽子、龍舟競渡與屈原自沉四者。看完這篇文章,你就會對端午、粽子、龍舟和屈原的四角關係有新的認識喔。那就讓我們一起解開謎團吧!
Thumbnail
當你邊吃粽子邊看龍舟競賽直播的時候,可能會順道悼念一下2300多年前投江的屈原。但你知道端午節及其活動原先都與屈原毫無關係嗎?這是怎麼回事呢? 本文深入探討端午節設立初衷、粽子、龍舟競渡與屈原自沉四者。看完這篇文章,你就會對端午、粽子、龍舟和屈原的四角關係有新的認識喔。那就讓我們一起解開謎團吧!
Thumbnail
題目敘述 Combination Sum II_Leetcode #40 給定一個整數陣列candidates 和 目標值target。 每個陣列元素只能選擇一次,請問有多少種組合方法,可以使得組合數總和 = target? 請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
Thumbnail
題目敘述 Combination Sum II_Leetcode #40 給定一個整數陣列candidates 和 目標值target。 每個陣列元素只能選擇一次,請問有多少種組合方法,可以使得組合數總和 = target? 請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
Thumbnail
題目敘述 Solving Questions With Brainpower 給定一個測驗題陣列,每個欄位都是一個pair, 分別記錄測驗題做完可以得到的分數,和需要的冷卻時間 (也就是會有一段時間不能作答接下來的題目)。 請問在最佳的答題策略下,最多可以獲得多少分數?
Thumbnail
題目敘述 Solving Questions With Brainpower 給定一個測驗題陣列,每個欄位都是一個pair, 分別記錄測驗題做完可以得到的分數,和需要的冷卻時間 (也就是會有一段時間不能作答接下來的題目)。 請問在最佳的答題策略下,最多可以獲得多少分數?
Thumbnail
題目敘述 題目會給定我們一個整數陣列nums,我們每回合可以挑選總和為K的兩個數字,形成一個K-Sum pair。 請問我們最多可以製造幾個K-Sum pair? 題目的原文敘述 測試範例 Example 1: Input: nums = [1,2,3,4], k = 5 Output
Thumbnail
題目敘述 題目會給定我們一個整數陣列nums,我們每回合可以挑選總和為K的兩個數字,形成一個K-Sum pair。 請問我們最多可以製造幾個K-Sum pair? 題目的原文敘述 測試範例 Example 1: Input: nums = [1,2,3,4], k = 5 Output
Thumbnail
題目敘述 題目會給定我們兩個輸入字串word1, word2,要求我們依照word1,word2,word1,word2, ... 交叉前進的方式,合併兩個字串,作為輸出。 題目的原文敘述 測試範例 Example 1: Input: word1 = "abc", word2 = "pq
Thumbnail
題目敘述 題目會給定我們兩個輸入字串word1, word2,要求我們依照word1,word2,word1,word2, ... 交叉前進的方式,合併兩個字串,作為輸出。 題目的原文敘述 測試範例 Example 1: Input: word1 = "abc", word2 = "pq
Thumbnail
題目敘述 題目會給我們兩個輸入陣列spells咒語、potions藥水,還有一個參數success。 當咒語和藥水相乘的值 > success就是一個成功配對。 請問每個咒語能夠形成的成功配對數有多少? 以陣列的形式輸出返回答案。 題目的原文敘述 測試範例 Example 1:
Thumbnail
題目敘述 題目會給我們兩個輸入陣列spells咒語、potions藥水,還有一個參數success。 當咒語和藥水相乘的值 > success就是一個成功配對。 請問每個咒語能夠形成的成功配對數有多少? 以陣列的形式輸出返回答案。 題目的原文敘述 測試範例 Example 1:
Thumbnail
題目敘述 題目會給我們一個陣列,要求我們返回 兩數之和=target所在的陣列索引值。 題目還額外保證,一定剛好有一組解。 測試範例 Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1]
Thumbnail
題目敘述 題目會給我們一個陣列,要求我們返回 兩數之和=target所在的陣列索引值。 題目還額外保證,一定剛好有一組解。 測試範例 Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1]
Thumbnail
這題的題目會給我們一個輸入整數,要求我們判斷這個整數是否可以用2^k 的形式來表達 (二的冪)?
Thumbnail
這題的題目會給我們一個輸入整數,要求我們判斷這個整數是否可以用2^k 的形式來表達 (二的冪)?
Thumbnail
題目會給我們兩條已經從小到大排序好的串列,要求我們依照從小到大的順序,合併這兩條串列。
Thumbnail
題目會給我們兩條已經從小到大排序好的串列,要求我們依照從小到大的順序,合併這兩條串列。
Thumbnail
題目會給定我們一個輸入陣列,要求我們計算好配對的數目有多少個? 好配對的定義: 兩個數字相同,但是陣列索引一個在前,一個在後。 nums[i] == nums[j] and i < j. 這樣 (i, j) 就稱為一組好配對。
Thumbnail
題目會給定我們一個輸入陣列,要求我們計算好配對的數目有多少個? 好配對的定義: 兩個數字相同,但是陣列索引一個在前,一個在後。 nums[i] == nums[j] and i < j. 這樣 (i, j) 就稱為一組好配對。
Thumbnail
題目會給我們一個輸入陣列candidates,和一個目標值 target 問我們,從canditdates裡面重複挑選,可以湊出總和為target目標值的組合數有幾種? 在此,我們將使用找零錢II的DP模型和化簡的技巧來解題。
Thumbnail
題目會給我們一個輸入陣列candidates,和一個目標值 target 問我們,從canditdates裡面重複挑選,可以湊出總和為target目標值的組合數有幾種? 在此,我們將使用找零錢II的DP模型和化簡的技巧來解題。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News