[Swift]LeetCode841.钥匙和房间|KeysandRooms

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

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

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

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

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

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

There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0).

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

Input: [[1],[2],[3],[]]
Output: true
Explanation:  
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.

Example 2:

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.

Note:

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
The number of keys in all rooms combined is at most 3000.

有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初，除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true，否则返回 false。

示例 1：

输入: [[1],[2],[3],[]]
输出: true
解释:  
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

示例 2：

输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

提示：

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
所有房间中的钥匙数量总计不超过 3000。

40ms

 1 class Solution {
 2     func canVisitAllRooms(_ rooms: [[Int]]) -> Bool {
 3         var keys: [Int] = Array(repeating: -1, count: rooms.count)
 4         var result:[Int] = [0]
 5         keys[0] = 0
 6         var i: Int = 0
 7         while i < result.count {
 8             for each in rooms[result[i]] {
 9                 if keys[each] == -1 {
10                     result.append(each)
11                     keys[each] = 0
12                 }
13             }
14             if result.count == rooms.count {
15                 return true
16             }
17             i += 1
18         }
19         return false
20     }
21 }

Runtime: 44 ms

Memory Usage: 19.4 MB

 1 class Solution {
 2     func canVisitAllRooms(_ rooms: [[Int]]) -> Bool {
 3         var dfs:[Int] = [Int]()
 4         dfs.append(0)
 5         var seen:Set<Int> = Set<Int>()
 6         seen.insert(0)
 7         while(!dfs.isEmpty)
 8         {
 9             var i:Int = dfs.removeLast()
10             for j in rooms[i]
11             {
12                 if !seen.contains(j)
13                 {
14                     dfs.append(j)
15                     seen.insert(j)
16                     if rooms.count == seen.count {return true}
17                 }
18             }
19         }
20         return rooms.count == seen.count
21     }
22 }

44ms

 1 class Solution {
 2     func canVisitAllRooms(_ rooms: [[Int]]) -> Bool {
 3         let count = rooms.count
 4         var seen = [Bool](repeating: false, count: count)
 5         seen[0] = true
 6         
 7         var keysInRoom = [Int]()
 8         keysInRoom.append(0)
 9         
10         while keysInRoom.count != 0 {
11             let room = keysInRoom.last!
12             keysInRoom.removeLast()
13             
14             let keys = rooms[room]
15             for key in keys {
16                 if !seen[key] {
17                     seen[key] = true
18                     keysInRoom.append(key)
19                 }
20             }
21         }
22         for s in seen {
23             if !s {
24                 return false
25             }
26         }
27         return true
28     }
29 }

48ms

 1 class Solution {
 2     func canVisitAllRooms(_ rooms: [[Int]]) -> Bool {
 3 
 4         var numberOfRooms = rooms.count
 5         var visited: [Int: Int] = [:]
 6         var stack: [Int] = []
 7         stack.append(0)
 8         visited[0] = 1
 9         
10         while(!stack.isEmpty) {
11             
12             var room = stack.removeLast()
13             var keys = rooms[room]
14             
15             for key in keys {
16                 if(visited[key] == nil) {
17                     visited[key] = 1
18                     stack.append(key)
19                 }
20             }            
21         }
22         return numberOfRooms == visited.keys.count
23     }
24 }

52ms

 1 class Solution {
 2     func canVisitAllRooms(_ rooms: [[Int]]) -> Bool {
 3         var key = Set(rooms[0])
 4         var open = [0:0]
 5         var nextOpen : Int? = 0
 6         while nextOpen != nil {
 7             nextOpen = nil
 8             for data in key {
 9                 if open[data] == nil {
10                 nextOpen = data
11                open[ data] = data
12                 for k in rooms[data]{
13                     key.insert(k)
14                  }
15                 key.remove(data)
16                 }
17             }
18         }
19         return open.count == rooms.count
20     }
21 }

64ms

 1 class Solution {
 2     func canVisitAllRooms(_ rooms: [[Int]]) -> Bool {
 3         var unvisited : Set<Int> = []
 4         var canVisit : [Int] = []
 5         
 6         for i in 0 ..< rooms.count {
 7             unvisited.insert(i)
 8         }
 9         
10         canVisit = rooms[0]
11         unvisited.remove(0)
12         
13         while !canVisit.isEmpty {
14             let room = canVisit.removeFirst()
15             if unvisited.contains(room) {
16                 canVisit.append(contentsOf: rooms[room])
17                 unvisited.remove(room)
18             }
19         }
20         
21         if unvisited.isEmpty {
22             return true
23         }
24         
25         return false
26     }
27 }

76ms

 1 class Solution {
 2     func canVisitAllRooms(_ rooms: [[Int]]) -> Bool {
 3         if (rooms.count <= 1) { return true }
 4         
 5         var visitedRooms: [Bool] = Array.init(repeating: false, count: rooms.count)
 6         visitedRooms[0] = true
 7         var queue: [Int] = []
 8         addKeysToQueue(&queue, 0, &visitedRooms, rooms)
 9         
10         while (!queue.isEmpty) {
11             addKeysToQueue(&queue, queue.removeLast(), &visitedRooms, rooms)
12         }
13         
14         for i in 0..<visitedRooms.count {
15             if (!visitedRooms[i]) {
16                 return false
17             }
18         }
19         return true
20     }
21     
22     func addKeysToQueue(_ queue: inout [Int], _ key: Int, _ visitedRooms: inout [Bool], _ rooms: [[Int]]) {
23         for i in 0..<rooms[key].count {
24             var nextRoom = rooms[key][i]
25             if (!visitedRooms[nextRoom]) {
26                 queue.append(nextRoom)
27                 visitedRooms[nextRoom] = true
28             }
29         }
30     }
31 }