X

LEETCODE 1537. Get the Maximum Score 解题思路分析

题目大意:

最大得分

你有两个 有序 且数组内元素互不相同的数组 nums1nums2

一条 合法路径 定义如下:

选择数组 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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1537

解题思路分析:

找到数组中相同的数字,然后将所有相同数字连线,这样我们可以把两个数组分别分成n个部分,对于两个数组的每个部分,我们选取和较大的并累加至返回结果即可。

比如数组:

[1, 3, 4, 6, 7]
[1, 2, 3, 7, 9]

我们将数组中相同的数字连线后,会将其分割成以下形式:

[1],    | [3, 4, 6], | [7]
[1, 2], | [3],       | [7, 9]

sum:
1       |  13        | 7
3       |  3         | 16

max:
3 + 13 + 16 = 32

解题时我们使用双指针分别代表两个数组当前的下标。然后再使用两个变量sum1和sum2分别代表当前两个数组的子区间和。循环中,如果当前两个数组指向的数字相同,那么以这两个数字连线为界,可将数组截断。将此时两个区间和sum1和sum2较大一方累加至返回结果。同时两个区间和清零。并且两个数组下标分别加一。如果数组1的数字小于数组2的数字,那么将数组1的数字累加至sum1,同时数组1下标加一。反之,将数组2 的当前数字累加至sum2,同时数组2的下标加一。(解释:由于两个数组都是升序排列,因此移动较小一方的指针,目的是尽快找到数值相同的两个数字)

实现代码:

public int maxSum(int[] nums1, int[] nums2) {
    int index1=0,index2=0; // 两个数组当前下标
    long sum1=0,sum2=0; // 两个数组的区间和
    long sum=0; // 返回结果
    while(index1<nums1.length&&index2<nums2.length){
        if(nums1[index1]==nums2[index2]){ // 如果两个数字相同
            sum1+=nums1[index1]; // 将数组1的当前数字累加至sum1
            sum2+=nums2[index2]; // 将数组2的当前数字累加至sum2
            sum+=Math.max(sum1,sum2); // 两个区间和的较大值累加至返回结果
            sum1=0; // 区间和清零
            sum2=0; // 区间和清零
            index1++; // 下标加一
            index2++; // 下标加一 
        }else if(nums1[index1]<nums2[index2]){ // 如果数组1当前数字较小
            sum1+=nums1[index1]; // 将数组1的当前数字累加至sum1
            index1++; // 下标加一
        }else{ // 如果数组2当前数字较小
            sum2+=nums2[index2]; // 将数组2的当前数字累加至sum1
            index2++; // 下标加一
        }
    }
    while(index1<nums1.length){ // 如果数组1还有剩余
        sum1+=nums1[index1]; // 将数组1的当前数字累加至sum1
        index1++; // 下标加一
    }
    while(index2<nums2.length){ // 如果数组2还有剩余
        sum2+=nums2[index2]; // 将数组2的当前数字累加至sum1
        index2++; // 下标加一
    }
    sum+=Math.max(sum1,sum2); // 两个区间和的较大值累加至返回结果
    return (int)(sum%1000000007);
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 100.00% of Java online submissions for Get the Maximum Score.

Memory Usage: 49.4 MB, less than 100.00% of Java online submissions for Get the Maximum Score.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1537-get-the-maximum-score-解题思路分析/
Categories: leetcode
kwantong: