当前位置:网站首页>LeetCode 2359. 找到离给定两个节点最近的节点 基环树
LeetCode 2359. 找到离给定两个节点最近的节点 基环树
2022-08-02 21:06:00 【超级码力奥】
基环树
- 对于有向图来说:基环树就是一个环上挂了一堆树,每个节点只有一个出边,可能有环
- 对于无向图来说:n个点n条边的联通,一定是一个基环树
题目描述
给你一个 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
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-closest-node-to-given-two-nodes
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
数据量10的五次方,要控制在nlogn以内。
思路很简单,就是求出来每个点到两个起点的距离,然后再遍历每个点,在维护距离最大值的同时,维护一个id的最小值。
求每个点到起点的最短距离,由于每个边权重一样,直接BFS就可以,但是由于是基环树,起点到每个点的路径是唯一的,所以也不用BFS这么麻烦了,直接沿着临边遍历即可。
class Solution {
public:
int closestMeetingNode(vector<int>& p, int x, int y) {
int n = p.size();
vector<int> d1(n, -1), d2(n, -1); // 存每个点到起点的距离
// 初始化
d1[x] = d2[y] = 0;
while(p[x] != -1)
{
// 如果有环,则退出
if(d1[p[x]] != -1) break;
d1[p[x]] = d1[x] + 1;
x = p[x];
}
while(p[y] != -1)
{
if(d2[p[y]] != -1) break;
d2[p[y]] = d2[y] + 1;
y = p[y];
}
// 遍历所有节点
int res = -1, id = -1;
for(int i = 0; i < n; i ++)
{
int a = d1[i], b = d2[i];
if(a != -1 && b != -1)
{
if(res == -1 || res > max(a, b))
{
res = max(a, b);
id = i;
}
}
}
return id;
}
};
class Solution:
def closestMeetingNode(self, p: List[int], x: int, y: int) -> int:
n = len(p)
d1 = [-1] * n
d2 = [-1] * n
d1[x] = 0
d2[y] = 0
while p[x] != -1:
if d1[p[x]] != -1:
break
d1[p[x]] = d1[x] + 1
x = p[x]
while p[y] != -1:
if d2[p[y]] != -1:
break
d2[p[y]] = d2[y] + 1
y = p[y]
# print(d1)
# print(d2)
res, id = -1, -1
for i in range(n):
a, b = d1[i], d2[i]
if a != -1 and b != -1:
if res == -1 or res > max(a, b):
res, id = max(a, b), i
return id
灵佬的代码:
最后一个循环的优化:
class Solution:
def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
n, min_dis, ans = len(edges), len(edges), -1
def calc_dis(x: int) -> List[int]:
dis = [n] * n
d = 0
while x >= 0 and dis[x] == n:
dis[x] = d
d += 1
x = edges[x]
return dis
for i, d1, d2 in zip(range(n), calc_dis(node1), calc_dis(node2)):
d = max(d1, d2)
if d < min_dis:
min_dis, ans = d, i
return ans
作者:endlesscheng
链接:https://leetcode.cn/problems/find-closest-node-to-given-two-nodes/solution/ji-suan-dao-mei-ge-dian-de-ju-chi-python-gr2u/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
边栏推荐
- 拥抱Cmake小朋友 简单又实用,但是不灵活
- Common tools and test methods for interface testing (Introduction)
- vscode如何能将输出从OUTPUT改为TERMINAL或者DebugConsole
- 无线振弦采集仪远程修改参数的方式
- 2022年金九银十,Android面试中高频必问的问题汇总
- 汉源高科千兆4光4电工业级网管型智能环网冗余以太网交换机防浪涌防雷导轨式安装
- ACE JET NPOI
- Zabbix 5.0 Monitoring Tutorial (2)
- golang刷leetcode: 小于等于 K 的最长二进制子序列
- I interviewed a 985 graduate, and I will never forget the expression when answering the "performance tuning" question
猜你喜欢
汉源高科2光12电千兆导轨式网管型工业以太网交换机双光自愈保护式以太网光交换机
【C语言进阶】--指针典题剖析
ECCV 2022 | ByteTrack: 简单高效的数据关联方法
The software testing process specification is what?Specific what to do?
引用类型 ,值类型 ,小坑。
Vscode快速入门、 插件安装、插件位置、修改vscode默认引用插件的路径、在命令行总配置code、快捷键
Mysql用户管理
WPF development through practical 】 【 automatic production management platform
微软SQL服务器被黑客入侵以窃取代理服务的带宽
字节内部技术图谱 惊艳级实用
随机推荐
y85.第四章 Prometheus大厂监控体系及实战 -- prometheus告警机制进阶、pushgateway和prometheus存储(十六)
用户之声 | GBASE南大通用实训有感
[C题目]力扣142. 环形链表 II
2022年金九银十,Android面试中高频必问的问题汇总
golang刷letcode:公司命名
回文自动机+CodeTON Round 2 C,D
千人优学 | GBase 8s数据库2022年6月大学生专场实训圆满结束
解道8-编程技术5
Li Mu hands-on deep learning V2-BERT pre-training and code implementation
博客主页rrs代码
IP协议(网际协议)
C#异步和多线程
华为设备配置BFD多跳检测
以赛促练-力扣第304场周赛反思(持续更新中)
工厂模式理解了没有?
Ansible安装与配置
golang 刷leetcode:统计打字方案数
PLC working principle animation
C# Barrier class
树形结构构造示例代码