当前位置:网站首页>0DFS Medium LeetCode6134. Find the closest node to the given two nodes
0DFS Medium LeetCode6134. Find the closest node to the given two nodes
2022-08-01 21:35:00 【18 Aru】
6134. Find the closest node to the given two nodes
描述
给你一个 n 个节点的 有向图 ,节点编号为 0 到 n - 1 ,每个节点 至多 有一条出边.
有向图用大小为 n 下标从 0 开始的数组 edges 表示,表示节点 i 有一条有向边指向 edges[i] .如果节点 i 没有出边,那么 edges[i] == -1 .
同时给你两个节点 node1 和 node2 .
请你返回一个从 node1 和 node2 都能到达节点的编号,使节点 node1 和节点 node2 到这个节点的距离 较大值最小化.如果有多个答案,请返回 最小 的节点编号.如果答案不存在,返回 -1 .
注意 edges 可能包含环.
提示:
n == edges.length
2 <= n <= 105
-1 <= edges[i] < n
edges[i] != i
0 <= node1, node2 < n
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-closest-node-to-given-two-nodes
著作权归领扣网络所有.商业转载请联系官方授权,非商业转载请注明出处.
分析
可达性分析
Node1 和node2分别遍历一次,Record the distance to each node,Then iterate over each node,在node1和node2Select from the nodes that can be reachednode1和node2The smallest node that reaches the larger value of this node.
Note the distance from1开始这样node1,node2The distance will not be0,It is convenient to exclude which nodes cannot be reached by two nodes.
class Solution {
public int closestMeetingNode(int[] edges, int node1, int node2) {
int n = edges.length;
int[] len = new int[n];
int[] len2 = new int[n];
int i = node1, j = node2;
int l1 = 1;
int l2 = 1;
while (i != -1 && len[i] == 0) {
len[i] = l1;
l1++;
i = edges[i];
}
int ans = -1;
int max = n+2;
while (j != -1 && len2[j] == 0) {
len2[j] = l2;
l2++;
j = edges[j];
}
for (int k = 0; k < n; k++) {
if (len[k] != 0 && len2[k] != 0) {
int tmp = Math.max(len[k],len2[k]);
if (max > tmp) {
max = tmp;
ans = k;
}
}
}
return ans;
}
}
边栏推荐
- Unity Shader 常规光照模型代码整理
- C Expert Programming Chapter 1 C: Through the Fog of Time and Space 1.1 The Prehistoric Phase of the C Language
- 测试的意义并不是能找到全部的缺陷
- LeetCode·每日一题·1374.生成每种字符都是奇数个的字符串·模拟
- C Expert Programming Chapter 1 C: Through the Fog of Time and Space 1.5 ANSI C Today
- P7215 [JOISC2020] 首都 题解
- Transplant MQTT source code to STM32F407 development board
- with语句和上下文管理器
- 如何优雅的性能调优,分享一线大佬性能调优的心路历程
- FusionGAN:A generative adversarial network for infrared and visible image fusion文章学习笔记
猜你喜欢
随机推荐
一个关于操作数据库的建议—用户密码
Spark shuffle tuning
图片识别商品接口 API:天猫淘宝
Spark shuffle调优
【力扣】字符串相乘
JVM内存结构详解
NFT的10种实际用途(NFT系统开发)
Image fusion GANMcC study notes
render-props和高阶组件
shell规范与变量
Jmeter实战 | 同用户重复并发多次抢红包
方舟开服需要知道的那些事
An online JVM FullGC made it impossible to sleep all night and completely crashed~
Day33 LeetCode
作业8.1 孤儿进程与僵尸进程
C Pitfalls and Defects Chapter 7 Portability Defects 7.11 An Example of a Portability Problem
多商户商城系统功能拆解19讲-平台端发票管理
Interview Blitz 70: What are sticky packs and half packs?How to deal with it?
微软校园大使喊你来秋招啦!
C Pitfalls and Defects Chapter 7 Portability Defects 7.6 Memory Location 0