湖州网络公司网站建设,重庆喷绘制作,wordpress上传文件插件,网站作品怎么做链接作者推荐
【深度优先搜索】【树】【图论】2973. 树中每个节点放置的金币数目
本文涉及知识点
双指针
LeetCoce 1537. 最大得分
你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。 一条 合法路径 定义如下#xff1a; 选择数组 nums1 或者 nums2 开始遍历…作者推荐
【深度优先搜索】【树】【图论】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]结束的最大得分。iMaxmax(max1,max2)。返回iMax。 如果没有相同值 max1 nums1[0,i)之和max2nums2[0,j)之和 如果有相同值。 假定第一个相同值是nums[ix] nums[jx]。 iix1时yjx1时max1和max2都等于iMax。 用iMax替换 nums1[0,ix] ,用iMax替换nums2[0,iy]继续迭代。
代码
核心代码
class Solution {
public:int maxSum(vectorint nums1, vectorint 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) % (1000000000 7);}
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}}int main()
{ vectorint 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 C17 或者 操作系统win10 开发环境 VS2022 **C
17** 如无特殊说明本算法用**C**实现。
