【刷题日记】2039. 网络空闲的时刻

本次刷题日记的第 9 篇，力扣题为：2039. 网络空闲的时刻 ，中等

一、题目描述：

乍看今天的这道题，有点要被劝退的感觉 ！！  xdm 有这种感受吗

但是为了提高我们自己的能力，我们还是有这个耐心来将题目看完的，并且会找出其中的重点信息

二、思路分析：

1、这道题考察了什么思想？你的思路是什么？

这道题具体需要如何去实现呢，我们可以来分析一下，题中给我们展示了哪些有用的信息

• 题目会给出多个服务器，从  0 到 n -1 个服务器编号，且 0 是主服务器，其他的服务器都会向 主服务器发送消息，主服务器也会原路回应消息
  
• 节点和节点之间，能够在 1 秒钟将所有信息全部发送完毕
  
• 每个服务器和服务器之间都是可以通过某个路径进行通信的，但是题目要求的是最小路径 ， 且服务器和服务器之间，顶多有 1 条信息线，不会出现两个节点之间有 2 条甚至更多的信息线
  
• 题目中还提供一个数组，来表示对应服务器发送信息出去后的超时重发时间，如果在指定时间内服务器收到了主服务器 0 的回包，那么就不重发，否则就重发
  
• 最后我们需要计算网络变空闲的最早时刻，那就意味着，网络中每一个节点都要是空闲的才行，此刻计算最晚空闲下来的节点时间，就是整个网络的最早空闲时间
  毕竟整体的结果，是团队内每一个人努力付出的结果
  

那么，根据题中的示例，我们可以来分析和推演一下：

以 edges = [[0,1],[1,2]], patience = [0,2,1] 为例

通过上图，我们需要分清楚有 2 种情况，那就是该节点从发包到收到包的时间是小于超时时间 p（2t <= p ），那么就不会重发，总共耗时 就是  2t 秒，第 2t + 1 秒就是空闲的

只有当发第一个包到收到的时间大于超时时间 p 的时候（2t > p），才会重发，总共耗时 p *((2t -1) / p) + 2t ，最终 p *((2t -1) / p) + 2t + 1  秒开始空闲

那么已经知道如何计算网络的最晚空闲时间的数学原理之后，我们就可以看看这个题的最短路径问题了

最短路径，详细分析就不做赘述了，对于之后的最短路径的题再一起来推理，暂时我们可以理解，先把节点和节点的连接关系表示出来，如下：

接下来，我们直接可以使用 广度优先算法 BFS 来计算最短路径了

2、尝试编码

根据上述逻辑和分析，我们就可以翻译成如下代码

编码如下：

func networkBecomesIdle(edges [][]int, p []int) (ans int) {
    n := len(p)
    g := make([][]int, n)
    // 先找到节点和节点之间的连接关系，如上述的案例，此处就能得到
    //g[0] = [1]    -- 表示 0 这个节点可以连接  1 节点
  //g[1] = [0,2] -- 表示 1 这个节点，可以连接 0节点， 和 2 节点
  //g[2] = [1]    -- 表示 2 这个节点，可以连接 1 节点
    for _, e := range edges {
        x, y := e[0], e[1]
        g[x] = append(g[x], y)
        g[y] = append(g[y], x)
    }
    vis := make([]bool, n)
    vis[0] = true
    q := []int{0}
    // 通过 bfs 的方式来来计算最短路径
    for t := 1; q != nil; t++ {
        tmp := q
        q = nil
        for _, x := range tmp {
            for _, v := range g[x] {
                if vis[v] {
                    continue
                }
                vis[v] = true
                q = append(q, v)
                // 计算最晚空闲时间
                ans = max(ans, (t*2-1)/p[v] * p[v] + t*2 +1)
            }
        }
    }
    return
}
func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

通过上述代码，我们知道主要逻辑是：

• 找到节点和节点间的连接关系
• 通过 bfs 广度优先算法，计算节点到 主节点 0 的最短距离，并计算该节点的最晚空闲时间
• 最终取，数值最大的最晚空闲时间为整个网络的最早空闲时间

四、总结：

整个题，需要弄清楚整个网络的最早空闲时间是依赖于节点的最晚空闲时间，需要处理好超时重传的时间问题

本题的时间复杂度和空间复杂度为 ：O(n+m)

原题地址：2039. 网络空闲的时刻

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~