2039. 网络空闲的时刻 : 简单「建图 + BFS」运用题

简介: 2039. 网络空闲的时刻 : 简单「建图 + BFS」运用题

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 2039. 网络空闲的时刻 ,难度为 中等


Tag : 「BFS」


给你一个有 nn 个服务器的计算机网络,服务器编号为 00n - 1n1 。同时给你一个二维整数数组 edges ,其中 edges[i] = [u_i, v_i]edges[i]=[ui,vi] 表示服务器 u_iuiv_ivi 之间有一条信息线路,在一秒内它们之间可以传输任意数目的信息。再给你一个长度为 nn 且下标从 00 开始的整数数组 patience


题目保证所有服务器都是相通的,也就是说一个信息从任意服务器出发,都可以通过这些信息线路直接或间接地到达任何其他服务器。


编号为 00 的服务器是主服务器,其他服务器为数据服务器。每个数据服务器都要向主服务器发送信息,并等待回复。信息在服务器之间按最优线路传输,也就是说每个信息都会以最少时间到达主服务器。主服务器会处理所有新到达的信息并立即按照每条信息来时的路线反方向发送回复信息。


00 秒的开始,所有数据服务器都会发送各自需要处理的信息。从第 11 秒开始,每一秒最开始时,每个数据服务器都会检查它是否收到了主服务器的回复信息(包括新发出信息的回复信息):


  • 如果还没收到任何回复信息,那么该服务器会周期性重发信息。数据服务器 iipatience[i]patience[i] 秒都会重发一条信息,也就是说,数据服务器 ii 在上一次发送信息给主服务器后的 patience[i]patience[i] 秒 后 会重发一条信息给主服务器。
  • 否则,该数据服务器不会重发信息。


当没有任何信息在线路上传输或者到达某服务器时,该计算机网络变为空闲状态。


请返回计算机网络变为空闲状态的最早秒数。


示例 1:


网络异常,图片无法展示
|


输入:edges = [[0,1],[1,2]], patience = [0,2,1]
输出:8
解释:
0 秒最开始时,
- 数据服务器 1 给主服务器发出信息(用 1A 表示)。
- 数据服务器 2 给主服务器发出信息(用 2A 表示)。
1 秒时,
- 信息 1A 到达主服务器,主服务器立刻处理信息 1A 并发出 1A 的回复信息。
- 数据服务器 1 还没收到任何回复。距离上次发出信息过去了 1 秒(1 < patience[1] = 2),所以不会重发信息。
- 数据服务器 2 还没收到任何回复。距离上次发出信息过去了 1 秒(1 == patience[2] = 1),所以它重发一条信息(用 2B 表示)。
2 秒时,
- 回复信息 1A 到达服务器 1 ,服务器 1 不会再重发信息。
- 信息 2A 到达主服务器,主服务器立刻处理信息 2A 并发出 2A 的回复信息。
- 服务器 2 重发一条信息(用 2C 表示)。
...
4 秒时,
- 回复信息 2A 到达服务器 2 ,服务器 2 不会再重发信息。
...
7 秒时,回复信息 2D 到达服务器 2 。
从第 8 秒开始,不再有任何信息在服务器之间传输,也不再有信息到达服务器。
所以第 8 秒是网络变空闲的最早时刻。
复制代码


示例 2:


网络异常,图片无法展示
|


输入:edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]
输出:3
解释:数据服务器 1 和 2 第 2 秒初收到回复信息。
从第 3 秒开始,网络变空闲。
复制代码


提示:


  • n == patience.lengthn==patience.length
  • 2 <= n <= 10^52<=n<=105
  • patience[0] == 0patience[0]==0
  • 对于 1 <= i < n1<=i<n ,满足 1 <= patience[i] <= 10^51<=patience[i]<=105
  • 1 <= edges.length <= \min(105, n * (n - 1) / 2)1<=edges.length<=min(105,n(n1)/2)
  • edges[i].length == 2edges[i].length==2
  • 0 <= ui, vi < n0<=ui,vi<n
  • ui != viui!=vi
  • 不会有重边。
  • 每个服务器都直接或间接与别的服务器相连。


建图 + BFS



根据题目可知这是一个边权为 11 的无向连通图,我们可以采用「邻接表建图 + BFS」的方式预处理出 distdist 数组,dist[i]dist[i] 含义为节点 ii00 号点的最短距离。


一个数据服务器 ii 往主服务器发送消息所消耗的时间为两节点之间的最短路径 dist[i]dist[i],而从发送消息到收到回复所需的时间为 di = 2 * dist[i]di=2dist[i]


同时每个数据服务器还存在时间间隔为 t = patience[i]t=patience[i] 的重发动作,并且动作只有在第一次收到主服务的回复后才会停止。


因此如果 di <= tdi<=t,那么数据服务器不会发生重发动作,该节点活动停止时间点为 didi;当 di > tdi>t,数据服务器将会发生重发动作,且最后一个数据包的发送时间为 (di - 1) / t * t(di1)/tt,只有当最后一个数据包收到回复,该节点的所有活动才算停止,停止时间点为 (di - 1) / t * t + di(di1)/tt+di。所有节点的活动停止时间点的最大值即是答案。


一些细节:老规矩,为了避免每个样例都 new 大数组,我们使用 static 优化。使用 static 优化后,你甚至会收获一个稳定 100100% 的结果 🤣


代码:


class Solution {
    static int N = 100010, M = N * 2, INF = 0x3f3f3f3f;
    static int[] he = new int[N], e = new int[M], ne = new int[M];
    static int[] dist = new int[N];
    int idx;
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
    }
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        Arrays.fill(he, -1);
        Arrays.fill(dist, INF);
        int n = patience.length;
        for (int[] e : edges) {
            add(e[0], e[1]);
            add(e[1], e[0]);
        }
        Deque<Integer> d = new ArrayDeque<>();
        d.addLast(0);
        dist[0] = 0;
        while (!d.isEmpty()) {
            int t = d.pollFirst();
            for (int i = he[t]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] != INF) continue;
                dist[j] = dist[t] + 1;
                d.addLast(j);
            }
        }
        int ans = 0;
        for (int i = 1; i < n; i++) {
            int di = dist[i] * 2, t = patience[i];
            int cur = di <= t ? di : (di - 1) / t * t + di;
            if (cur > ans) ans = cur;
        }
        return ans + 1;
    }
}
复制代码


  • 时间复杂度:O(n + m)O(n+m)
  • 空间复杂度:O(n + m)O(n+m)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.2039 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
算法 Cloud Native
【刷题日记】2039. 网络空闲的时刻
本次刷题日记的第 9 篇,力扣题为:2039. 网络空闲的时刻 ,中等
|
算法
[leetcode] 2039. 网络空闲的时刻 | BFS
题意: 给定一张n个点不含重边的无向图,点的编号从0开始到n-1,两点之间如果有连边,可以认为耗时为1秒 1->n-1的点都需要向0号点发送消息(从第0秒开始) 在0号收到消息之后,会回复消息; 从第一秒开始,如果1->n-1号服务器经过patiennce[]时间都还没有收到回复的消息,那么就会重新发送请求的消息 问最早的网络中没有消息传输的时间是什么时候
95 0
[leetcode] 2039. 网络空闲的时刻 | BFS
LeetCode 2039. 网络空闲的时刻(BFS)
LeetCode 2039. 网络空闲的时刻(BFS)
158 0
LeetCode 2039. 网络空闲的时刻(BFS)
|
2天前
|
SQL 安全 网络安全
网络安全与信息安全:关于网络安全漏洞、加密技术、安全意识等方面的知识分享
【10月更文挑战第23天】在数字时代,网络安全和信息安全已成为我们生活中不可或缺的一部分。本文将探讨网络安全漏洞、加密技术和安全意识等方面的内容,以帮助读者更好地了解如何保护自己的网络安全。通过分析常见的网络安全漏洞,介绍加密技术的基本原理和应用,以及强调安全意识的重要性,我们将为读者提供一些实用的建议和技巧,以增强他们的网络安全防护能力。
|
1天前
|
SQL 存储 安全
网络安全与信息安全:防范漏洞、加密技术及安全意识
随着互联网的快速发展,网络安全和信息安全问题日益凸显。本文将探讨网络安全漏洞的类型及其影响、加密技术的应用以及提高个人和组织的安全意识的重要性。通过深入了解这些关键要素,我们可以更好地保护自己的数字资产免受网络攻击的威胁。
|
1天前
|
SQL 安全 算法
网络安全与信息安全:漏洞、加密和意识的三维防护网
【10月更文挑战第25天】在数字时代的浪潮中,网络安全和信息安全如同守护我们虚拟家园的坚固城墙。本文将深入探讨网络安全漏洞的种类与应对策略,解析加密技术的核心原理及其应用,并强调提升个人与企业的安全意识对于构建安全防线的重要性。通过深入浅出的方式,我们将一起探索网络世界的安全之道,确保数据资产的坚不可摧。
|
2天前
|
SQL 安全 网络安全
网络安全与信息安全:关于网络安全漏洞、加密技术、安全意识等方面的知识分享
【10月更文挑战第23天】在数字化时代,网络安全和信息安全已经成为我们生活中不可或缺的一部分。本文将介绍网络安全漏洞、加密技术和安全意识等方面的内容,帮助读者更好地了解网络安全和信息安全的基本知识。通过本文的学习,您将能够更好地保护自己的个人信息和数据安全。