leetcode 1537. Get the Maximum Score merge 变体 取模谨慎

题目

https://leetcode.com/contest/weekly-contest-200/problems/get-the-maximum-score/
You are given two sorted arrays of distinct integers nums1 and nums2.

A valid path is defined as follows:

Choose array nums1 or nums2 to traverse (from index-0).
Traverse the current array from left to right.
If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).
Score is defined as the sum of uniques values in a valid path.

Return the maximum score you can obtain of all possible valid paths.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10], (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10] (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].
Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].
Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].
Example 4:

Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61

Constraints:

1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 and nums2 are strictly increasing.

思路

merge sort
i,j 分别为两个 list 的游标,向前移动并累计求和,对于相同值的两个节点,其后可以选择之前的任意一个分支,同一个 list 两个跳转节点间的值可以压缩为一个节点,所以最终将跳转节点位置对齐,便利跳转节点只需要选择两个 list 中值较大的即可
注意取模的坑,取模会影响 max 操作,所以建议使用 longlong,将取模操作放到最后

源码

class Solution {
public:
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        int  i = 0,j = 0;
        int mod = 1000000007;
        long long res = 0;
        long long sum1 = 0,sum2 = 0;
        while(i<nums1.size()&&j<nums2.size()){
            if(nums1[i]==nums2[j]){
                res = (res+max(sum1,sum2)+nums1[i])%mod;
                sum1 = sum2 = 0;
                i++;
                j++;
            }else if(nums1[i]<nums2[j]){
                sum1=(sum1+nums1[i]);
                i++;
            }else{
                sum2=(sum2+nums2[j]);
                j++;
            }
        }
        while(i!=nums1.size()){
            sum1=sum1+nums1[i];
            i++;
        }
        while(j!=nums2.size()){
            sum2=sum2+nums2[j];
            j++;
        }
        return res=(res+max(sum1,sum2))%mod;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注