【双指针】【C++算法】1537. 最大得分

作者推荐

【深度优先搜索】【树】【图论】2973. 树中每个节点放置的金币数目

本文涉及知识点

双指针

LeetCoce 1537. 最大得分

你有两个 有序 且数组内元素互不相同的数组 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]得到。

提示：

1 <= nums1.length, nums2.length <= 10⁵

1 <= nums1[i], nums2[i] <= 10⁷

nums1 和 nums2 都是严格递增的数组。

双指针

max1 记录从nums[0]开始，nums[i-1]结束的最大得分。max2记录nums2[0]开始，nums2[j]结束的最大得分。iMax=max(max1,max2)。返回iMax。

如果没有相同值：

max1 = nums1[0,i)之和，max2=nums2[0,j)之和

如果有相同值。

假定第一个相同值是nums[ix] nums[jx]。 i=ix+1时，y=jx+1时，max1和max2都等于iMax。

用iMax替换 nums1[0,ix] ,用iMax替换nums2[0,iy]继续迭代。

代码

核心代码

class Solution {
public:
  int maxSum(vector<int>& nums1, vector<int>& nums2) {
    long long max1 = 0, max2 = 0;
    for (int i = 0, j = 0; (i < nums1.size()) || (j < nums2.size());)
    {
      if ((i < nums1.size()) && (j < nums2.size()))
      {
        const int iCmp = nums1[i] - nums2[j];
        if (0 == iCmp)
        {
          max1 = max2 = max(max1 + nums1[i++], max2 + nums2[j++]);
        }
        else if (iCmp < 0)
        {
          max1 += nums1[i++];
        }
        else
        {
          max2 += nums2[j++];
        }
      }
      else if (i < nums1.size())
      {
        max1 += nums1[i++];
      }
      else
      {
        max2 += nums2[j++];
      }
    }
    return max(max1, max2) % (1'000'000'000+ 7);
  }
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{ 
  vector<int> nums1,nums2;
  int k;
  {
    Solution sln;
    nums1 = { 2, 4, 5, 8, 10 }, nums2 = { 4, 6, 8, 9 };
    auto res = sln.maxSum(nums1, nums2);
    Assert(30, res);
  }
  {
    Solution sln;
    nums1 = { 1, 3, 5, 7, 9 }, nums2 = { 3, 5, 100 };
    auto res = sln.maxSum(nums1, nums2);
    Assert(109, res);
  }
  
  
  {
    Solution sln;
    nums1 = { 1, 2, 3, 4, 5 }, nums2 = { 6, 7, 8, 9, 10 };
    auto res = sln.maxSum(nums1, nums2);
    Assert(40, res);
  }
}

2023年8月版

class Solution {

public:

int maxSum(vector& nums1, vector& nums2) {

int i1 = 0, i2 = 0;

long long iiNum1 = 0, iiNum2 = 0;

long long iiRet = 0;

while (true)

{

while ((i1 < nums1.size()) && (i2 < nums2.size()) && (nums1[i1] != nums2[i2]))

{

if (nums1[i1] < nums2[i2])

{

iiNum1 += nums1[i1];

i1++;

}

else

{

iiNum2 += nums2[i2];

i2++;

}

}

if ((i1 < nums1.size()) && (i2 < nums2.size()))

{

iiRet += max(iiNum1, iiNum2) + nums1[i1];

iiNum1 = iiNum2 = 0;

i1++;

i2++;

continue;

}

while (i1 < nums1.size())

{

iiNum1 += nums1[i1];

i1++;

}

while (i2 < nums2.size())

{

iiNum2 += nums2[i2];

i2++;

}

iiRet += max(iiNum1, iiNum2);

break;

}

const int s_iMod = 1000000007;

return iiRet % s_iMod;

}

};