5478. 最大得分 [hard]

第 200 场周赛, paypal专场

https://leetcode-cn.com/contest/weekly-contest-200/problems/get-the-maximum-score/

你有两个有序且数组内元素互不相同的数组 nums1 和 nums2 。

一条合法路径定义如下：

选择数组 nums1 或者 nums2 开始遍历（从下标 0 处开始）。
从左到右遍历当前数组。
如果你遇到了 nums1 和 nums2 中都存在的值，那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。得分定义为合法路径中不同数字的和。

请你返回所有可能合法路径中的最大得分。

由于答案可能很大，请你将它对 10^9 + 7 取余后返回。

示例 1：

输入：nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
输出：30
解释：合法路径包括：
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],（从 nums1 开始遍历）
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]  （从 nums2 开始遍历）
最大得分为上图中的绿色路径 [2,4,6,8,10] 。

示例 2：

输入：nums1 = [1,3,5,7,9], nums2 = [3,5,100]
输出：109
解释：最大得分由路径 [1,3,5,100] 得到。

示例 3：

输入：nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
输出：40
解释：nums1 和 nums2 之间无相同数字。
最大得分由路径 [6,7,8,9,10] 得到。

示例 4：

输入：nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
输出：61

提示：

1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 和 nums2 都是严格递增的数组。

First Try

2020-08-02

找出相同的节点，统计节点之间的距离，有点权重图的感觉。

但其实统计出节点之间的选择之后，使用动态规划每一个关键节点都选择最优，就得到了总体最优最大得分路径。

想清楚怎么把问题进行压缩，变成有限固定节点之间的选择，问题就容易多了。

第四题hard做出来了，但没想到第三题5477的medium没做出来，哎。

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        # 提供一个共同的归宿，减少额外处理
        nums1.append(0)
        nums2.append(0)
        # 找出所有重复点
        counter = collections.defaultdict(list)
        for i in range(len(nums1)):
            counter[nums1[i]].append(i)
        for j in range(len(nums2)):
            counter[nums2[j]].append(j)
        duplicates = [k for k, v in counter.items() if len(v) == 2]
        
        # 感觉可以转化为图的问题
        gap1 = [0] * len(duplicates)
        gap2 = [0] * len(duplicates)
        for idx in range(len(duplicates)):
            if idx > 0:
                starti = counter[duplicates[idx - 1]][0] + 1 
                startj = counter[duplicates[idx - 1]][1] + 1
            else:
                starti, startj = 0, 0 
            for i in range(starti, counter[duplicates[idx]][0] + 1):
                gap1[idx] += nums1[i]
            for j in range(startj, counter[duplicates[idx]][1] + 1):
                gap2[idx] += nums2[j]
        
        print("duplicates", duplicates)
        print("gap1", gap1)
        print("gap2", gap2)
        # 还是得用动态规划才行
        maxv = 0
        for i in range(len(duplicates)):
            maxv = maxv + max(gap1[i], gap2[i])
        
        return maxv % (10 ** 9 + 7)
                

5478. 最大得分 [hard]​

First Try​

5478. 最大得分 [hard]

First Try