[Swift]LeetCode847.访问所有节点的最短路径|ShortestPathVisitingAllNodes ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10591816.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

An undirected, connected graph of N nodes (labeled 0, 1, 2, ..., N-1) is given as graph.

graph.length = N, and j != i is in the list graph[i] exactly once, if and only if nodes i and j are connected.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

Example 1:

Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]

Example 2:

Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

Note:

1 <= graph.length <= 12
0 <= graph[i].length < graph.length

给出 graph 为有 N 个节点（编号为 0, 1, 2, ..., N-1）的无向连通图。

graph.length = N，且只有节点 i 和 j 连通时，j != i 在列表 graph[i] 中恰好出现一次。

返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

示例 1：

输入：[[1,2,3],[0],[0],[0]]
输出：4
解释：一个可能的路径为 [1,0,2,0,3]

示例 2：

输入：[[1],[0,2,4],[1,3,4],[2],[1,2]]
输出：4
解释：一个可能的路径为 [0,1,4,2,3]

提示：

1 <= graph.length <= 12
0 <= graph[i].length < graph.length

Runtime: 240 ms

Memory Usage: 19.5 MB

 1 class Solution {
 2     func shortestPathLength(_ graph: [[Int]]) -> Int {
 3         var n:Int = graph.count
 4         var fullMask:Int = (1 << n) - 1
 5         var visited:Set<String> = Set<String>()
 6         var que:[Node] = [Node]()
 7         for i in 0..<n
 8         {
 9             var node:Node = Node(i, 1<<i)
10             que.append(node)
11             visited.insert(node.toString())
12         }
13         var level:Int = 0
14         while(!que.isEmpty)
15         {
16             var size:Int = que.count
17             for i in 0..<size
18             {
19                 var node = que.removeFirst()
20                 if node.mask == fullMask {return level}
21                 for next in graph[node.id]
22                 {
23                     var nextNode:Node = Node(next, node.mask | (1 << next))
24                     if visited.contains(nextNode.toString()) {continue}
25                     que.append(nextNode)
26                     visited.insert(nextNode.toString())
27                 }
28             }
29             level += 1
30         }
31         return level
32     }
33 }
34 
35 class Node {
36     var id:Int = 0
37     var mask:Int = 0
38     
39     init(_ id:Int,_ mask:Int)
40     {
41         self.id = id
42         self.mask = mask        
43     }
44     
45     func toString() -> String
46     {
47         return String(id) + " " + String(mask)
48     }
49 }