[Swift]LeetCode743. 网络延迟时间 | Network Delay Time
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10525029.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
There are N network nodes, labelled 1 to N.
Given times, a list of travel times as directededges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.
Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.
Note:
Nwill be in the range[1, 100].Kwill be in the range[1, N].- The length of
timeswill be in the range[1, 6000]. - All edges
times[i] = (u, v, w)will have1 <= u, v <= Nand0 <= w <= 100.
有 N 个网络节点，标记为 1 到 N。
给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。
现在，我们向当前的节点 K 发送了一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
注意:
N的范围在[1, 100]之间。K的范围在[1, N]之间。times的长度在[1, 6000]之间。- 所有的边
times[i] = (u, v, w)都有1 <= u, v <= N且0 <= w <= 100。
Runtime: 496 ms
Memory Usage: 19.3 MB
1 class Solution {
2 func networkDelayTime(_ times: [[Int]], _ N: Int, _ K: Int) -> Int {
3 var res:Int = 0
4 var edges:[Int:[(Int,Int)]] = [Int:[(Int,Int)]]()
5 var dist:[Int] = [Int](repeating:Int.max,count:N + 1)
6 var q:[Int] = [K]
7 dist[K] = 0
8 for e in times
9 {
10 edges[e[0],default:[(Int,Int)]()].append((e[1], e[2]))
11 }
12 while (!q.isEmpty)
13 {
14 var u:Int = q.first!
15 q.removeFirst()
16 var visited:Set<Int> = Set<Int>()
17 for (key,val) in edges[u,default:[(Int,Int)]()]
18 {
19 var v:Int = key
20 var w:Int = val
21 if dist[u] != Int.max && dist[u] + w < dist[v]
22 {
23 dist[v] = dist[u] + w
24 if visited.contains(v) {continue}
25 visited.insert(v)
26 q.append(v)
27 }
28 }
29 }
30 for i in 1...N
31 {
32 res = max(res, dist[i])
33 }
34 return res == Int.max ? -1 : res
35 }
36 }604ms
1 class Solution {
2 func networkDelayTime(_ times: [[Int]], _ N: Int, _ K: Int) -> Int {
3 guard times.count > 0 else {
4 return -1
5 }
6
7
8 var graph = [[Int]](repeating:[Int](repeating:-1, count:N + 1), count: N + 1)
9
10 for t in times {
11 graph[t[0]][t[1]] = t[2]
12 }
13
14 var memo = [Int: Int]()
15 var visited = [Int: Bool]()
16 //We need to use bfs
17 var queue = [Int]()
18 for i in 1...N {
19 queue.append(i)
20 memo[i] = Int.max
21 }
22
23 memo[K] = 0
24
25 while queue.count != 0 {
26 queue.sort(by:{ memo[$0]! < memo[$1]! })
27 let node = queue.removeFirst()
28 visited[node] = true
29
30 for i in 0..<graph[node].count {
31 if visited[i] == true || graph[node][i] == -1 {
32 continue
33 } else {
34 memo[i]! = min(memo[i]!, memo[node]! + graph[node][i])
35 }
36 }
37 }
38
39 var maxT = 0
40
41 print(memo)
42
43
44 for i in 1...N {
45 if let time = memo[i] {
46 if time == Int.max {
47 return -1
48 } else {
49 maxT = max(maxT, time)
50 }
51 }
52 }
53
54 return maxT
55 }
56 }660ms
1 class Solution {
2 func networkDelayTime(_ times: [[Int]], _ N: Int, _ K: Int) -> Int {
3 var delayTimes = Array(repeating: Int.max, count: N + 1)
4 delayTimes[K] = 0
5
6 var nodeLeft = Array(repeating: 1, count: N + 1)
7
8 while true {
9 var closest = Int.max
10 var closestIndex = -1
11 for i in 1..<nodeLeft.count {
12 if nodeLeft[i] != 0 && delayTimes[i] < closest {
13 closest = delayTimes[i]
14 closestIndex = i
15 }
16 }
17
18 if closestIndex == -1 {
19 break
20 }
21
22 for i in 0..<times.count {
23 if times[i][0] == closestIndex {
24 delayTimes[times[i][1]] = min(delayTimes[times[i][1]], delayTimes[times[i][0]] + times[i][2])
25 }
26 }
27
28 nodeLeft[closestIndex] = 0
29 }
30
31 var delayTime = 0
32
33 for i in 1..<delayTimes.count {
34 if delayTimes[i] == Int.max {
35 return -1
36 } else {
37 delayTime = max(delayTime, delayTimes[i])
38 }
39 }
40
41 return delayTime
42 }
43 }680ms
1 class Solution {
2 func networkDelayTime(_ times: [[Int]], _ N: Int, _ K: Int) -> Int {
3 var delayTimes = Array(repeating: Int.max, count: N)
4 delayTimes[K - 1] = 0
5
6 var nodeLeft = Array(repeating: 1, count: N)
7
8 while true {
9 var closest = Int.max
10 var closestIndex = -1
11 for i in 0..<nodeLeft.count {
12 if nodeLeft[i] != 0 && delayTimes[i] < closest {
13 closest = delayTimes[i]
14 closestIndex = i + 1
15 }
16 }
17
18 if closestIndex == -1 {
19 break
20 }
21
22 for i in 0..<times.count {
23 if times[i][0] == closestIndex {
24 delayTimes[times[i][1] - 1] = min(delayTimes[times[i][1] - 1], delayTimes[times[i][0] - 1] + times[i][2])
25 }
26 }
27
28 nodeLeft[closestIndex - 1] = 0
29 }
30
31 return delayTimes.max()! == Int.max ? -1 : delayTimes.max()!
32 }
33 }712ms
1 class Solution {
2 func networkDelayTime(_ times: [[Int]], _ N: Int, _ K: Int) -> Int {
3 let graph = Graph<Int>(.undirected)
4 times.forEach { (time) in
5 let source = graph.createVertex(time[0])
6 let destination = graph.createVertex(time[1])
7 graph.addDirectedEdge(from: source, to: destination, weight: Double(time[2]))
8 }
9
10 var distances: [Vertex<Int>: Int] = [:]
11 var parent: [Vertex<Int>: Vertex<Int>] = [:]
12 dijstra(graph, source: graph.createVertex(K), distances: &distances, parent: &parent)
13 if distances.count != N {
14 return -1
15 }
16 return distances.reduce(into: 0, { $0 = max($0, $1.value) })
17 }
18
19
20 func dijstra<T: Hashable>(_ graph: Graph<T>,
21 source: Vertex<T>,
22 distances: inout [Vertex<T>: Int],
23 parent: inout [Vertex<T>: Vertex<T>]
24 ) {
25 var source = source
26 var inTree: Set<Vertex<T>> = []
27 distances[source] = 0
28
29 while !inTree.contains(source) {
30 inTree.insert(source)
31
32 for edge in graph.edges(of: source) {
33 let destination = edge.destination
34 let edgeWeight = Int(edge.weight!)
35 if distances[destination] == nil ||
36 distances[destination]! > edgeWeight + distances[source]! {
37 distances[destination] = edgeWeight + distances[source]!
38 parent[destination] = source
39 }
40 }
41 var minDistance = Int.max
42 for (vertex, distance) in distances where !inTree.contains(vertex) {
43 if minDistance > distance {
44 minDistance = distance
45 source = vertex
46 }
47 }
48 }
49
50 }
51 }
52
53 enum GraphType {
54 case directed
55 case undirected
56 }
57
58
59 struct Vertex<T:Hashable> : Hashable{
60 public var val : T
61
62 public init(_ val: T){
63 self.val = val
64 }
65
66 public var hashValue: Int {
67 return val.hashValue
68 }
69
70 public static func == (lhs: Vertex<T>, rhs: Vertex<T>) -> Bool{
71 return lhs.val == rhs.val
72 }
73 }
74
75 extension Vertex: CustomStringConvertible{
76 var description: String{
77 return "\(val)"
78 }
79 }
80
81
82 struct Edge<T:Hashable>{
83 public let source: Vertex<T>
84 public let destination: Vertex<T>
85 public var weight : Double?
86 }
87
88 class Graph<T: Hashable>{
89 public var vertices : [Vertex<T>] = []
90 private var adjacencyList : [Vertex<T> : [Edge<T>]] = [:]
91 public var type: GraphType
92 public init(_ type: GraphType) {
93 self.type = type
94 }
95
96 public func createVertex(_ val: T)->Vertex<T>{
97 let vertex = Vertex<T>.init(val)
98 if adjacencyList[vertex] == nil{
99 adjacencyList[vertex] = []
100 vertices.append(vertex)
101 }
102 return vertex
103 }
104
105 public func addDirectedEdge(from source: Vertex<T>,
106 to destination: Vertex<T>,
107 weight: Double?
108 ){
109 let edge = Edge<T>.init(source: source, destination: destination, weight: weight)
110 adjacencyList[source]?.append(edge)
111 }
112
113 public func addUndirectedEdge(between source: Vertex<T>,
114 and destination: Vertex<T>,
115 weight: Double?
116 ){
117 addDirectedEdge(from: source, to: destination, weight: weight)
118 addDirectedEdge(from: destination, to: source, weight: weight)
119 }
120
121 public func edges(of source: Vertex<T>)->[Edge<T>]{
122 return adjacencyList[source] ?? []
123 }
124
125 public func weight(of source: Vertex<T>,
126 to destination: Vertex<T>
127 )->Double?{
128 return adjacencyList[source]?.first(where: {$0.destination == destination})?.weight
129 }
130 }800ms
1 class Solution {
2 typealias link = (target: Int, delay: Int)
3
4 private class node {
5 var distance = Int.max
6 var next = [link]()
7 }
8
9 func networkDelayTime(_ times: [[Int]], _ N: Int, _ K: Int) -> Int {
10 var dict = [Int:node]()
11 var visited = Set([K])
12
13 for index in 1...N {
14 dict[index] = node()
15 }
16
17 for time in times {
18 dict[time[0]]!.next.append((time[1],time[2]))
19 }
20
21 dict[K]!.distance = 0
22
23 while (visited.count != N) {
24 var shortestDist = Int.max; var shortestIndex = 0
25 for index in visited {
26 let tmpNode = dict[index]!
27 var counter = 0
28 for connectedNodes in tmpNode.next {
29 let tmpIndex = connectedNodes.target
30 if visited.contains(tmpIndex) {
31 _ = tmpNode.next.remove(at: counter)
32 continue
33 }
34 counter += 1
35 let tmpDist = connectedNodes.delay + tmpNode.distance
36 let prevDist = dict[tmpIndex]!.distance
37
38 if (tmpDist < prevDist) {
39 dict[tmpIndex]!.distance = tmpDist
40 }
41 if (tmpDist < shortestDist) {
42 shortestDist = tmpDist
43 shortestIndex = tmpIndex
44 }
45 }
46 }
47 if (shortestIndex == 0) {
48 return -1
49 }
50 visited.insert(shortestIndex)
51 }
52
53 var maxDelay = 0
54
55 for nodes in dict.values where (nodes.distance > maxDelay) {
56 maxDelay = nodes.distance
57 }
58
59 return maxDelay
60 }
61 }- 上一篇 »Linux tc命令模拟网络延迟和丢包
- 下一篇 »PHP常用函数大全
