【双指针】【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 <= 105
1 <= nums1[i], nums2[i] <= 107
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;
}
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 **C+

+17**
如无特殊说明,本算法用**C++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/387622.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

极其抽象的SpringSecurity理解

原始&#xff1a;A → B Security&#xff1a;A → S → B 太抽象了&#xff0c;看不懂啊T_T 抽象故事 故事大概&#xff1a;C是一个大区&#xff0c;拥有巨大的火力&#xff08;C准备联合B吞并掉A&#xff09;&#xff0c;A得到了这个消息&#xff0c;…

解决‘vue‘ 不是内部或外部命令,也不是可运行的程序(设置全局变量)

发现是没有执行&#xff1a; npm install -g vue/cli 但是发现还是不行 此时&#xff0c;我们安装了 Vue CLI&#xff0c;但是在运行 vue ui 命令时出现了问题。这通常是因为全局安装的 Vue CLI 的路径没有被正确地添加到系统的环境变量中。 可以尝试以下几种方法来解决这个问…

视觉slam十四讲学习笔记(四)相机与图像

理解理解针孔相机的模型、内参与径向畸变参数。理解一个空间点是如何投影到相机成像平面的。掌握OpenCV的图像存储与表达方式。学会基本的摄像头标定方法。 目录 前言 一、相机模型 1 针孔相机模型 2 畸变 单目相机的成像过程 3 双目相机模型 4 RGB-D 相机模型 二、图像…

LEETCODE 315. 计算右侧小于当前元素的个数(归并)

class Solution { public: // 将count声明为publicvector<int> count; vector<int> indexs,tmp;public:vector<int> countSmaller(vector<int>& nums) {//归并int left0;int rightnums.size()-1;//计数// vector<int> count(nums.size()); …

【MATLAB】PSO_BP神经网络回归预测(多输入多输出)算法原理

有意向获取代码&#xff0c;请转文末观看代码获取方式~也可转原文链接获取~ 1 基本定义 PSO-BP神经网络回归预测&#xff08;多输入多输出&#xff09;算法是一种结合粒子群优化算法&#xff08;PSO&#xff09;和反向传播&#xff08;BP&#xff09;神经网络的混合算法。该算…

CSS之选择器、优先级、继承

1.CSS选择器 常用的选择器 <body><div class"parent"><div id"one" style"background: blue" class"child">1<div class"one_one">11</div><div style"background-color: blueviole…

vue3 Element Plus 基于webstorm练习

提要 vue是前端框架&#xff0c;Elemen是组件库。前端框架和组件库的区别与联系 nodejs 脚本语言需要一个解析器才能运行&#xff0c;JavaScript是脚本语言&#xff0c;在不同的位置有不一样的解析器&#xff0c;如写入html的js语言&#xff0c;浏览器是它的解析器角色。而对…

浅谈业务场景中缓存的使用

业务场景中缓存的使用 一、背景二、缓存分类1.本地缓存2.分布式缓存 三、缓存读写模式1.读请求2.写请求 四、缓存穿透1.缓存空对象2.请求校验3.请求来源限制4.布隆过滤器 五、缓存击穿1.改变过期时间2.串行访问数据库 六、缓存雪崩1.避免集中过期2.提前更新缓存 七、缓存与数据…

TMGM公司官网介绍

TMGM主要提供外汇、贵金属、原油、股指等CFD产品&#xff0c;客户可以根据个人的交易习惯选择其中一种或多种进行投资。具体来说&#xff0c;TMGM的金融产品包括但不限于货币对、黄金、原油、股票指数等。此外&#xff0c;TMGM还提供多种账户类型以满足不同客户的交易需求。 请…

error MSB8008: 指定的平台工具集(v143)未安装或无效。请确保选择受支持的 PlatformToolset 值解决办法

右击解决方案&#xff0c;选择属性 将工具集为143的修改为其他&#xff0c;如图 重新编译即可运行

DDC技术:AIGC网络的革命性解决方案

2023年&#xff0c;人工智能生成内容&#xff08;AIGC&#xff09;技术将蓬勃发展&#xff0c;其中ChatGPT作为一个典型案例&#xff0c;在文本生成、代码开发和诗歌创作等多个领域引起行业变革。DDC技术对改变网络格局具有创新和突破性意义&#xff0c;很大程度上提升了效率和…

Python 读取pdf文件

Python 实现读取pdf文件简单示例。 安装命令 需要安装操作pdf的三方类库&#xff0c;命令如下&#xff1a; pip install pdfminer3K 安装过程如下&#xff1a; 引入类库 需要引入很多的类库。 示例如下&#xff1a; import sys import importlib importlib.reload(sys)fr…

汽车零部件制造业MES系统解决方案

一、​汽车零部件行业现状 随着全球汽车产业不断升级&#xff0c;汽车零部件市场竞争日趋激烈&#xff0c;从上游的钢铁、塑料、橡胶等生产到下游的主机厂配套制造&#xff0c;均已成为全球各国汽车制造大佬战略目标调整的焦点&#xff0c;其意欲在汽车零部件行业快速开疆扩土&…

蓝牙BLE学习-GAP

1.概述 GAP层&#xff08;Generic access profile-通用访问配置文件&#xff09;。GAP是对LL层payload&#xff08;有效数据包&#xff09;如何进行解析的两种方式的一种&#xff0c;而且也是最简单的一种。GAP简单的对LL payload进行一些规范和定义&#xff0c;因此GAP能实现的…

Compose高级别API动画指南

前文讲了Compose中的低级别API动画&#xff0c;与之对应的&#xff0c;还有高级别API动画&#xff0c;同样也符合Material-Design规范。所有高级别动画 API 都是在低级别动画 API 的基础上构建而成&#xff0c;其对应关系如图&#xff1a; 接下来就对其高级别API逐个分析&…

【王道数据结构】【chapter5树与二叉树】【P159t12】

设一棵二叉树的结点结构为(LLINK,INFO,RLINK)&#xff0c;ROOT为指向该二叉树根结点的指针&#xff0c;p和q分别为指向该二叉树中任意两个节点的指针&#xff0c;试编写算法ANCESTOR(ROOT,p,q,r)&#xff0c;找到p和q的最近公共祖先结点r #include <iostream> #include &…

Linux第54步_根文件系统第1步_编译busybox并安装_然后添加“根文件系统”的库

学习编译busybox&#xff0c;并安装&#xff0c;然后添加“根文件系统”的库。有人说busybox构建根文件系统&#xff0c;只适合学习&#xff0c;不适合做项目。 1、了解ubuntu的根文件系统 根文件系统的目录名为“/”&#xff0c;就是一个斜杠。 1)、输入“cd /回车”&…

算法学习——LeetCode力扣二叉树篇7

算法学习——LeetCode力扣二叉树篇7 236. 二叉树的最近公共祖先 236. 二叉树的最近公共祖先 - 力扣&#xff08;LeetCode&#xff09; 描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点…

加速创新如何先从创意管理开始?

文章详细介绍了什么是创意管理以及它在组织中的重要性和最佳实践。创意管理是指在组织内捕捉、组织、评估和实施创意的过程。它通过建立一个结构化的系统&#xff0c;从员工、客户或其他利益相关者那里收集创意&#xff0c;并系统地审查和选择最有前景的创意进行进一步的开发或…

《区块链公链数据分析简易速速上手小册》第8章:实战案例研究(2024 最新版)

文章目录 8.1 案例分析&#xff1a;投资决策支持8.1.1 基础知识8.1.2 重点案例&#xff1a;股票市场趋势预测准备工作实现步骤步骤1: 加载和准备数据步骤2: 特征工程步骤3: 训练模型步骤4: 评估模型 结论 8.1.3 拓展案例 1&#xff1a;基于情感分析的投资策略准备工作实现步骤步…