主备网站服务器自动切换 win2003,网站建设找客户,做网站的应该怎么发广告,wordpress注册带密码本文涉及知识点
C图论 打开打包代码的方法兼述单元测试
LeetCode2359. 找到离给定两个节点最近的节点
给你一个 n 个节点的 有向图 #xff0c;节点编号为 0 到 n - 1 #xff0c;每个节点 至多 有一条出边。 有向图用大小为 n 下标从 0 开始的数组 edges 表示#xff0c…本文涉及知识点
C图论 打开打包代码的方法兼述单元测试
LeetCode2359. 找到离给定两个节点最近的节点
给你一个 n 个节点的 有向图 节点编号为 0 到 n - 1 每个节点 至多 有一条出边。 有向图用大小为 n 下标从 0 开始的数组 edges 表示表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边那么 edges[i] -1 。 同时给你两个节点 node1 和 node2 。 请你返回一个从 node1 和 node2 都能到达节点的编号使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案请返回 最小 的节点编号。如果答案不存在返回 -1 。 注意 edges 可能包含环。 示例 1
输入edges [2,2,3,-1], node1 0, node2 1 输出2 解释从节点 0 到节点 2 的距离为 1 从节点 1 到节点 2 的距离为 1 。 两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值所以我们返回节点 2 。 示例 2
输入edges [1,2,-1], node1 0, node2 2 输出2 解释节点 0 到节点 2 的距离为 2 节点 2 到它自己的距离为 0 。 两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值所以我们返回节点 2 。
提示
n edges.length 2 n 105 -1 edges[i] n edges[i] ! i 0 node1, node2 n
图论
由于出度至多为1所以无需DFS或BFS直接循环。环如果没处理好会引起死循环。由于只有n个节点我们循环n-1次就可以枚举所有情况。 i1距离node1 i的节点如果不存在为-1。i2距离node2 i的节点如果不存在为-1。 cnt[i1];cnt[i2]; 如果cnt[i1]或cnt[i2] 等于2则返回i。 如果没有返回i返回-1。 错误 一cnt1必须和cnt2分开。由于有环node1或node2可能访问同一个节点多次。 二i相同的时候必须较小的节点。
代码
核心代码
class Solution {public:int closestMeetingNode(vectorint edges, int node1, int node2) {const int N edges.size();vectorint cnt1(N), cnt2(N);auto Vis [](vectorint cnt,int node) {if (-1 node) { return false; }cnt[node];return cnt1[node] cnt2[node];};auto Next [](int cur) {if (-1 cur) { return; }cur edges[cur];};for (int i 0,i1node1,i2node2; i N; i) {int ans INT_MAX;if (Vis(cnt1, i1)) { ans min(ans, i1); }if (Vis(cnt2,i2)) { ans min(ans, i2); }if (INT_MAX ! ans) { return ans; }Next(i1);Next(i2);}return -1;}};单元测试 vectorint edges;int node1, node2;TEST_METHOD(TestMethod11){edges { 2, 2, 3, -1 }, node1 0, node2 1;auto res Solution().closestMeetingNode(edges, node1, node2);AssertEx(2, res);}TEST_METHOD(TestMethod12){edges { 1,2,-1 }, node1 0, node2 2;auto res Solution().closestMeetingNode(edges, node1, node2);AssertEx(2, res);}TEST_METHOD(TestMethod13){edges { 5,4,5,4,3,6,-1 }, node1 0, node2 1;auto res Solution().closestMeetingNode(edges, node1, node2);AssertEx(-1, res);}TEST_METHOD(TestMethod14){edges { 4,4,8,-1,9,8,4,4,1,1 }, node1 5, node2 6;auto res Solution().closestMeetingNode(edges, node1, node2);AssertEx(1, res);}扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
