当前位置: 首页 > news >正文

【C++图论】2359. 找到离给定两个节点最近的节点|1714

本文涉及知识点

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(vector<int>& edges, int node1, int node2) {const int N = edges.size();vector<int> cnt1(N), cnt2(N);auto Vis = [&](vector<int>& 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,i1=node1,i2=node2; 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;}};

单元测试

	vector<int> 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 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:

【C++图论】2359. 找到离给定两个节点最近的节点|1714

本文涉及知识点 C图论 打开打包代码的方法兼述单元测试 LeetCode2359. 找到离给定两个节点最近的节点 给你一个 n 个节点的 有向图 &#xff0c;节点编号为 0 到 n - 1 &#xff0c;每个节点 至多 有一条出边。 有向图用大小为 n 下标从 0 开始的数组 edges 表示&#xff0c…...

重拾设计模式-外观模式和适配器模式的异同

文章目录 目的不同适配器模式&#xff1a;外观模式&#xff1a; 结构和实现方式不同适配器模式&#xff1a;外观模式&#xff1a; 对客户端的影响不同适配器模式&#xff1a;外观模式&#xff1a; 目的不同 适配器模式&#xff1a; 主要目的是解决两个接口不兼容的问题&#…...

51c自动驾驶~合集42

我自己的原文哦~ https://blog.51cto.com/whaosoft/12888355 #DriveMM 六大数据集全部SOTA&#xff01;最新DriveMM&#xff1a;自动驾驶一体化多模态大模型&#xff08;美团&中山大学&#xff09; 近年来&#xff0c;视觉-语言数据和模型在自动驾驶领域引起了广泛关注…...

34 Opencv 自定义角点检测

文章目录 cornerEigenValsAndVecscornerMinEigenVal示例 cornerEigenValsAndVecs void cornerEigenValsAndVecs(InputArray src, --单通道输入8位或浮点图像OutputArray dst, --输出图像&#xff0c;同源图像或CV_32FC(6)int blockSize, --邻域大小值int ape…...

信创技术栈发展现状与展望:机遇与挑战并存

一、引言 在信息技术应用创新&#xff08;信创&#xff09;战略稳步推进的大背景下&#xff0c;我国信创技术栈已然在诸多关键层面收获了亮眼成果&#xff0c;不过也无可避免地遭遇了一系列亟待攻克的挑战。信创产业作为我国达成信息技术自主可控这一目标的关键一招&#xff0c…...

跟我学c++中级篇——C++中的缓存利用

一、缓存 学习过计算机知识的一般都知道缓存这个概念&#xff0c;大约也知道缓存是什么。但是如果是程序员&#xff0c;如何更好的利用缓存&#xff0c;可能就有很多人不太清楚了。其实缓存的目的非常简单&#xff0c;就是了更高效的操作数据。大家都听说过“局部性原理”&…...

二叉树_堆

目录 一. 树(非线性结构&#xff09; 1.1 树的概念与结构 1.2 树的表示 二. 二叉树 2.1 二叉树的概念与结构 2.2 特殊的二叉树 2.3 二叉树的存储结构 三. 实现顺序结构的二叉树 3.1 堆的概念与结构 一. 树(非线性结构&#xff09; 1.1 树的概念与结构 概念&#xff…...

word文档中有大量空白行删除不掉,怎么办?

现象&#xff1a; 分页之间的空白行太多了&#xff08; 按回车没用。删除也删除不掉 &#xff09; 解决办法&#xff1a; 按ctrl a 全选这个文档右击鼠标&#xff0c;点击【段落】选择【换行和分页】&#xff0c;然后把【分页】里的选项全部勾掉&#xff0c;然后点击【确定】…...

python rabbitmq实现简单/持久/广播/组播/topic/rpc消息异步发送可配置Django

windows首先安装rabbitmq 点击参考安装 1、环境介绍 Python 3.10.16 其他通过pip安装的版本(Django、pika、celery这几个必须要有最好版本一致) amqp 5.3.1 asgiref 3.8.1 async-timeout 5.0.1 billiard 4.2.1 celery 5.4.0 …...

构建高性能异步任务引擎:FastAPI + Celery + Redis

在现代应用开发中&#xff0c;异步任务处理是一个常见的需求。无论是数据处理、图像生成&#xff0c;还是复杂的计算任务&#xff0c;异步执行都能显著提升系统的响应速度和吞吐量。今天&#xff0c;我们将通过一个实际项目&#xff0c;探索如何使用 FastAPI、Celery 和 Redis …...

永磁同步电机无速度算法--全阶滑模观测器

一、原理介绍 在采用传统滑模观测器求取电机角度时通常存在系统抖振、低通滤波器导致角度相位滞后、角度的求取等问题。针对上述问题&#xff0c;本文采用全阶滑模观测器&#xff0c;该全阶滑模观测器具有二阶低通滤波器的特性&#xff0c;能有效滤除反电动势中的高频噪声&…...

部署开源大模型的硬件配置全面指南

目录 第一章:理解大型模型的硬件需求 1.1 模型部署需求分析 第二章:GPU资源平台 2.1 免费GPU资源 2.1.1 阿里云人工智能PAI 2.1.2 阿里天池实验室 2.1.3 Kaggle 2.1.4 Google Colab 2.2 付费GPU服务 2.2.1 AutoDL 2.2.2 Gpushare Cloud 2.2.3 Featurize 2.2.4 A…...

三、使用langchain搭建RAG:金融问答机器人--检索增强生成

经过前面2节数据准备后&#xff0c;现在来构建检索 加载向量数据库 from langchain.vectorstores import Chroma from langchain_huggingface import HuggingFaceEmbeddings import os# 定义 Embeddings embeddings HuggingFaceEmbeddings(model_name"m3e-base")#…...

Day13 用Excel表体验梯度下降法

Day13 用Excel表体验梯度下降法 用所学公式创建Excel表 用Excel表体验梯度下降法 详见本Day文章顶部附带资源里的Excel表《梯度下降法》&#xff0c;可以对照表里的单元格公式进行理解&#xff0c;还可以多尝试几次不同的学习率 η \eta η来感受&#xff0c;只需要更改学习率…...

计算机组成原理的学习笔记(5)--数据的表示与运算·其四 浮点数的储存和加减/内存对齐/大端小端

学习笔记 前言 本文主要是对于b站尚硅谷的计算机组成原理的学习笔记&#xff0c;仅用于学习交流。 1. 浮点数的表示与运算 规格化数&#xff1a; 浮点数的存储格式为 &#xff0c;其中&#xff1a; 为符号位。 为尾数&#xff0c;通常在0和1之间&#xff08;规格化形式为1.xx…...

华为IPD流程6大阶段370个流程活动详解_第二阶段:计划阶段 — 86个活动

华为IPD流程涵盖了产品从概念到上市的完整过程,各阶段活动明确且相互衔接。在概念启动阶段,产品经理和项目经理分析可行性,PAC评审后成立PDT。概念阶段则包括产品描述、市场定位、投资期望等内容的确定,同时组建PDT核心组并准备项目环境。团队培训涵盖团队建设、流程、业务…...

如何使用 Flask 框架创建简单的 Web 应用?

Flask是一个轻量级的Web应用框架&#xff0c;用Python编写&#xff0c;非常适合快速开发和原型设计。 它提供了必要的工具和技术来构建一个Web应用&#xff0c;同时保持核心简单&#xff0c;不强制使用特定的工具或库。 二、创建第一个Flask应用 安装Flask 首先&#xff0c…...

将Minio设置为Django的默认Storage(django-storages)

这里写自定义目录标题 前置说明静态文件收集静态文件 使用django-storages来使Django集成Minio安装依赖settings.py测试收集静态文件测试媒体文件 前置说明 静态文件 Django默认的Storage是本地&#xff0c;项目中的CSS、图片、JS都是静态文件。一般会将静态文件放到一个单独…...

sed | 一些关于 sed 的笔记

sed 总结 sed 语法sed [-hnV] [-e<script>] [-f<script文件>] [文本文件]--- 参数&#xff1a;-e<script> 以选项中指定的script 来处理输入的文本文件-f<script文件> 以选项中指定的script 文件来处理输入的文本文件-n 禁用 pattern space 的默认输出…...

wtforms+flask_sqlalchemy在flask-admin视图下实现日期的修改与更新

背景&#xff1a; 在flask-admin 的modelview视图下实现自定义视图的表单修改/编辑是件不太那么容易的事情&#xff0c;特别是想不自定义前端view的情况下。 材料&#xff1a; wtformsflask_sqlalchemy 制作&#xff1a; 上代码 1、模型代码 from .exts import db from …...

Qwen3.5-2B效果展示:儿童绘本图→识别角色/场景/情绪→生成故事续写+朗读脚本

Qwen3.5-2B效果展示&#xff1a;儿童绘本图→识别角色/场景/情绪→生成故事续写朗读脚本 1. 模型介绍 Qwen3.5-2B是通义千问团队推出的轻量化多模态基础模型&#xff0c;属于Qwen3.5系列的小参数版本&#xff08;20亿参数&#xff09;。这个模型特别适合在资源有限的设备上部…...

DriverStore Explorer:突破Windows驱动管理瓶颈,释放系统空间提升80%存储效率

DriverStore Explorer&#xff1a;突破Windows驱动管理瓶颈&#xff0c;释放系统空间提升80%存储效率 【免费下载链接】DriverStoreExplorer Driver Store Explorer [RAPR] 项目地址: https://gitcode.com/gh_mirrors/dr/DriverStoreExplorer 诊断存储异常&#xff1a;设…...

Kook Zimage 真实幻想 Typora文档集成方案

Kook Zimage 真实幻想 Typora文档集成方案 1. 引言 技术文档写作最头疼的是什么&#xff1f;文字描述得再生动&#xff0c;也不如一张直观的图片来得有说服力。传统的文档创作流程中&#xff0c;我们需要先在专门的AI绘图工具中生成图片&#xff0c;然后下载保存&#xff0c;…...

BGE-Reranker-v2-m3为何必须用?RAG幻觉过滤入门必看

BGE-Reranker-v2-m3为何必须用&#xff1f;RAG幻觉过滤入门必看 如果你正在搭建RAG系统&#xff0c;或者已经搭建了但总觉得回答质量时好时坏&#xff0c;经常出现“幻觉”——也就是模型一本正经地胡说八道——那你很可能遇到了一个核心问题&#xff1a;向量检索“搜不准”。…...

Vue项目中天地图显示不全?试试这个MutationObserver的巧妙解法

Vue项目中天地图显示不全的终极解决方案&#xff1a;MutationObserver深度解析 第一次在Vue项目中集成天地图时&#xff0c;那种地图只渲染出一半的挫败感至今记忆犹新。控制台没有报错&#xff0c;API调用看起来也没问题&#xff0c;但地图就像被无形的剪刀裁切过一样&#xf…...

VisDrone2019-MOT转COCO踩坑实录:为什么你的转换脚本总报错?附修复方案

VisDrone2019-MOT转COCO实战避坑指南&#xff1a;从报错解析到工业级解决方案 当你第一次尝试将VisDrone2019-MOT数据集转换为COCO格式时&#xff0c;可能会遇到各种令人抓狂的报错信息。这不是你的问题——这个转换过程确实存在许多隐藏的陷阱。本文将带你深入剖析五个最常见的…...

Phi-3-mini-4k-instruct-gguf实操手册:中文短文本生成场景下的温度调优策略

Phi-3-mini-4k-instruct-gguf实操手册&#xff1a;中文短文本生成场景下的温度调优策略 1. 模型概述与使用场景 Phi-3-mini-4k-instruct-gguf 是微软推出的轻量级文本生成模型&#xff0c;特别适合处理中文短文本任务。这个经过优化的GGUF版本模型&#xff0c;在问答、文本改…...

comsol matlab联合仿真 也可加入solidworks三软件联合 参数化建模 全自动...

comsol matlab联合仿真 也可加入solidworks三软件联合 参数化建模 全自动建模迭代分析 实现多目标优化 帕累托前沿 代码模型与仿真参数化建模这事儿&#xff0c;玩过CAD和仿真的都懂——改个螺丝孔直径就得重新画图导出&#xff0c;累死个人。不过要是把SolidWorks、COMSOL和M…...

实时行情系统设计:从协议选择到高可用架构,再到数据源选型

一、核心问题及解决方案&#xff08;按踩坑频率排序&#xff09; 问题 1&#xff1a;误删他人持有锁——最基础也最易犯的漏洞 成因&#xff1a;释放锁时未做身份校验&#xff0c;直接执行 DEL 命令删除键。典型场景&#xff1a;服务 A 持有锁后&#xff0c;业务逻辑耗时超过锁…...

GCN在推荐系统中的应用:如何用图神经网络提升电商个性化推荐效果

GCN在电商推荐系统中的实战指南&#xff1a;从二部图构建到A/B测试全流程 当你在电商平台浏览商品时&#xff0c;那些"猜你喜欢"的推荐背后&#xff0c;可能正运行着一套基于图神经网络(GCN)的复杂算法系统。与传统的协同过滤不同&#xff0c;GCN能够捕捉用户-商品交…...