付費限定

最大化子序列的分數 Maximum Subsequence Score_Leetcode #2542 精選75題

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

題目敘述

題目會給兩個陣列nums1和nums2。

題目要求我們從中同步選擇長度為k的子序列,並且最大化子序列的分數,
回傳最高的分數值。

分數的定義:

分數 =
(nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) *
min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1])

= nums1子序列的總和 * nums2子序列的最小值


題目的原文敘述


測試範例

Example 1:

Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
Output: 12
Explanation:
The four possible subsequence scores are:
- We choose the indices 0, 1, and 2 with score = (1+3+3) * min(2,1,3) = 7.
- We choose the indices 0, 1, and 3 with score = (1+3+2) * min(2,1,4) = 6.
- We choose the indices 0, 2, and 3 with score = (1+3+2) * min(2,3,4) = 12.
- We choose the indices 1, 2, and 3 with score = (3+3+2) * min(1,3,4) = 8.
Therefore, we return the max score, which is 12.

Example 2:

Input: nums1 = [4,2,3,1,1], nums2 = [7,5,10,9,6], k = 1
Output: 30
Explanation:
Choosing index 2 is optimal: nums1[2] * nums2[2] = 3 * 10 = 30 is the maximum possible score.

約束條件

Constraints:

  • n == nums1.length == nums2.length

num1的陣列長度 = num2的陣列長度

  • 1 <= n <= 10^5

陣列長度介於1~十萬。

  • 0 <= nums1[i], nums2[j] <= 10^5

每個陣列元素值都介於0~十萬。

  • 1 <= k <= n

子序列長度介於1~n之間。


演算法 排序 + 最小堆minHeap

分數= nums1子序列的總和 * nums2子序列的最小值

所以,瓶頸點首先是nums2的最小值接著是盡量讓nums1選中的元素值越大越好


以行動支持創作者!付費即可解鎖
本篇內容共 2413 字、1 則留言,僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容,可能因為尚未登入,或沒有該房間的查看權限。
留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
96會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/08/13
題目敘述 Combination Sum II_Leetcode #40 給定一個整數陣列candidates 和 目標值target。 每個陣列元素只能選擇一次,請問有多少種組合方法,可以使得組合數總和 = target? 請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
Thumbnail
2024/08/13
題目敘述 Combination Sum II_Leetcode #40 給定一個整數陣列candidates 和 目標值target。 每個陣列元素只能選擇一次,請問有多少種組合方法,可以使得組合數總和 = target? 請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
Thumbnail
2024/06/01
動態規劃Dynamic Programming其實是 一種泛用的演算法思考方式與演算法建構框架。 動態規劃並不拘束於只能解課本上特定的的範例題。 只要我們能找出DP狀態定義、DP遞迴結構、初始條件(終止條件),就能適用動態規劃來解題,以數學的形式表達,並且在紙筆上或者電腦上、計算機上計算
Thumbnail
2024/06/01
動態規劃Dynamic Programming其實是 一種泛用的演算法思考方式與演算法建構框架。 動態規劃並不拘束於只能解課本上特定的的範例題。 只要我們能找出DP狀態定義、DP遞迴結構、初始條件(終止條件),就能適用動態規劃來解題,以數學的形式表達,並且在紙筆上或者電腦上、計算機上計算
Thumbnail
2024/05/29
Leetcode 精選75題 題目與題解 熱門考點 目錄 (持續更新中) 建議從左側目錄 或者 按Ctrl+F輸入關鍵字進行搜尋
Thumbnail
2024/05/29
Leetcode 精選75題 題目與題解 熱門考點 目錄 (持續更新中) 建議從左側目錄 或者 按Ctrl+F輸入關鍵字進行搜尋
Thumbnail
看更多
你可能也想看
Thumbnail
常常被朋友問「哪裡買的?」嗎?透過蝦皮分潤計畫,把日常購物的分享多加一個步驟,就能轉換成現金回饋。門檻低、申請簡單,特別適合學生與上班族,讓零碎時間也能創造小確幸。
Thumbnail
常常被朋友問「哪裡買的?」嗎?透過蝦皮分潤計畫,把日常購物的分享多加一個步驟,就能轉換成現金回饋。門檻低、申請簡單,特別適合學生與上班族,讓零碎時間也能創造小確幸。
Thumbnail
嗨!歡迎來到 vocus vocus 方格子是台灣最大的內容創作與知識變現平台,並且計畫持續拓展東南亞等等國際市場。我們致力於打造讓創作者能夠自由發表、累積影響力並獲得實質收益的創作生態圈!「創作至上」是我們的核心價值,我們致力於透過平台功能與服務,賦予創作者更多的可能。 vocus 平台匯聚了
Thumbnail
嗨!歡迎來到 vocus vocus 方格子是台灣最大的內容創作與知識變現平台,並且計畫持續拓展東南亞等等國際市場。我們致力於打造讓創作者能夠自由發表、累積影響力並獲得實質收益的創作生態圈!「創作至上」是我們的核心價值,我們致力於透過平台功能與服務,賦予創作者更多的可能。 vocus 平台匯聚了
Thumbnail
題目敘述 題目會給定一個有n個整數的陣列nums和指定的k值,問我們長度為k的子陣列的平均值的最大值是多少? 題目的原文敘述 測試範例 Example 1: Input: nums = [1,12,-5,-6,50,3], k = 4 Output: 12.75000 Explanati
Thumbnail
題目敘述 題目會給定一個有n個整數的陣列nums和指定的k值,問我們長度為k的子陣列的平均值的最大值是多少? 題目的原文敘述 測試範例 Example 1: Input: nums = [1,12,-5,-6,50,3], k = 4 Output: 12.75000 Explanati
Thumbnail
題目敘述 題目會給兩個陣列nums1和nums2。 題目要求我們從中同步選擇長度為k的子序列,並且最大化子序列的分數, 回傳最高的分數值。 分數的定義: 分數 = (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] ,
Thumbnail
題目敘述 題目會給兩個陣列nums1和nums2。 題目要求我們從中同步選擇長度為k的子序列,並且最大化子序列的分數, 回傳最高的分數值。 分數的定義: 分數 = (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] ,
Thumbnail
這題也是滿經典的DP動態規劃教學案例和題目,就順便複習一下吧。 題目敘述 題目會給我們兩個字串text1, text2。 要求我們找出兩個字串的最長共同子序列,並且返回最長共同子序列的長度。 如果彼此沒有共同子序列,則返回0。 題目的原文敘述 測試範例 Example 1: In
Thumbnail
這題也是滿經典的DP動態規劃教學案例和題目,就順便複習一下吧。 題目敘述 題目會給我們兩個字串text1, text2。 要求我們找出兩個字串的最長共同子序列,並且返回最長共同子序列的長度。 如果彼此沒有共同子序列,則返回0。 題目的原文敘述 測試範例 Example 1: In
Thumbnail
題目敘述 題目會給定一個整數陣列nums,要求我們找出最大的兩個整數a, b,返回(a-1) * (b-1)的乘積。 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [3,4,5,2] Output: 12
Thumbnail
題目敘述 題目會給定一個整數陣列nums,要求我們找出最大的兩個整數a, b,返回(a-1) * (b-1)的乘積。 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [3,4,5,2] Output: 12
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
題目會給們一個陣列,還有一個k值。 好陣列定義是: 有包含nums[k]的子陣列。 分數定義是: min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 其中, i, j 分別是子陣列的左端點和右端點 請問,好的子陣列的最大分數是多少?
Thumbnail
題目會給們一個陣列,還有一個k值。 好陣列定義是: 有包含nums[k]的子陣列。 分數定義是: min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 其中, i, j 分別是子陣列的左端點和右端點 請問,好的子陣列的最大分數是多少?
Thumbnail
題目會給定一個存有整數的陣列,要求我們依照下列規則進行排序,由小排到大,升序排列。
Thumbnail
題目會給定一個存有整數的陣列,要求我們依照下列規則進行排序,由小排到大,升序排列。
Thumbnail
題目會給我們一顆二元樹的根結點,要求我們找出每一層最大的節點值。
Thumbnail
題目會給我們一顆二元樹的根結點,要求我們找出每一層最大的節點值。
Thumbnail
題目會給定我們兩個字串,一個字串s,另一個字串t 要求我們判段字串s是否為字串t的子序列? (也就是s的每個字元都可以在t裡面找到,而且前後相對順序相同)
Thumbnail
題目會給定我們兩個字串,一個字串s,另一個字串t 要求我們判段字串s是否為字串t的子序列? (也就是s的每個字元都可以在t裡面找到,而且前後相對順序相同)
Thumbnail
這題就是經典的考排序驗算法, 不管在教科書、上機考、面試白板題都是一個很基本又滿熱門的題目。 題目會給定一個輸入陣列,要求我們實作一個排序演算法,把陣列元素從小到大排好。
Thumbnail
這題就是經典的考排序驗算法, 不管在教科書、上機考、面試白板題都是一個很基本又滿熱門的題目。 題目會給定一個輸入陣列,要求我們實作一個排序演算法,把陣列元素從小到大排好。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News