数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学Python中的钥匙和房间
假设我们有N个房间，我们从房间0开始。每个房间都有一个独特的数字0, 1, 2, ..., N-1，每个房间可能有一些钥匙可以进入下一个房间。换句话说，每个房间i都有一个钥匙列表rooms[i]，每个钥匙rooms[i][j]都是[0, 1, ..., N-1]中的一个整数，其中N = 房间数。钥匙rooms[i][j] = v，这将打开编号为v的房间。因此，如果输入是[[1], [2], [3], []]。那么输出将为true。我们还应该记住以下几点：
- 最初，所有房间都是锁着的（除了房间0）。
- 我们可以自由地在房间之间来回走动。
- 当且仅当我们可以进入每个房间时，我们应该返回true。
所以我们将从房间0开始，拿到钥匙1，然后去房间1，拿到钥匙2，然后从房间2，拿到钥匙3，访问完3后，如果所有房间都被访问过，则返回true。
为了解决这个问题，我们将遵循以下步骤：
- 创建一个空队列，并为所有房间创建一个visited数组，并将其设置为false
- queue := addRooms(rooms, 0, queue, visited)
- visited[0] := True
- 当队列中有一些元素时
- queue := addRooms(rooms, queue[0], queue, visited)
- 将visited[queue[0]]标记为true，
- 从队列中删除该元素
- 当visited数组中的所有元素都为true时，返回true
- addRoom()将接收rooms、index、queue和visited数组，这将类似于
- 对于rooms[index]数组中的i
- 如果i未被访问，则将i插入队列
- 返回队列
示例（Python）
让我们看看下面的实现，以便更好地理解：
class Solution(object): def canVisitAllRooms(self, rooms): queue = [] visited = [False for i in rooms] queue = self.add_rooms(rooms,0,queue,visited) visited[0] = True while len(queue)>0: queue = self.add_rooms(rooms,queue[0],queue,visited) visited[queue[0]] = True queue.pop(0) return all(visited) def add_rooms(self, rooms,index,queue,visited): for i in rooms[index]: if not visited[i]: queue.append(i) return queue ob1 = Solution() print(ob1.canVisitAllRooms([[1],[2],[3],[]]))
输入
[[1],[2],[3],[]]
输出
true
更新于：2020年4月29日
433 次浏览
广告