Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-05-24 16:20:50
https://leetcode.com/problems/maximum-subsequence-score/description/
2542. Maximum Subsequence Score
给你两个大小一样的阵列 nums1 和 nums2,以及一个数字 k,找出大小为 k 的子序列,
透过下列规则计算出分数 score:
score = (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) *
min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1])
求出 score 最大是多少。
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.
思路:
1.最大分数需要 nums1 的和越高越好,nums2 的最小数越大越好,两者相乘才会最高,简
单讲就是要求长度为k的最优Pair。
2.我们可以先让Pair的其中一边是最佳解,再尝试把其他nums1的元素加进来比较,如果得
到更大分数,就把比较小的键值对移除得到更优解。
3.因为分数是 nums2 的“其中一个数字”乘以nums1的“多个数字之和”,所以nums2变化
比较小,我们把nums2由大到小排序并取k个Pair可以得到一个局部最佳解ans。
4.从k+1位置开始,每次尝试加入一个新Pair,如果加入后的和变更大就把序列里的最小
值移除加入新的Pair,并计算nums2次优和nums1更优解相乘是否更大,更新ans。
5.把nums1的序列放进一个MinHeap,这样如果和更大,每次pop出来的都是最小元素。
Java Code:
作者: pandix (面包屌)   2023-05-24 16:23:00
大师
作者: MurasakiSion (紫咲シオン)   2023-05-24 16:23:00
大师
作者: Che31128 (justjoke)   2023-05-24 16:27:00
大师
作者: pandix (面包屌)   2023-05-24 16:34:00
我的话会用每个nums2[i]当成最小值的情况下 最佳解会是多少来解释
作者: NTHUlagka (拉卡)   2023-05-24 17:25:00
同上 p大的那种思路感觉会比较好想

Links booklink

Contact Us: admin [ a t ] ucptt.com