資料結構
網路
關係型資料庫管理系統 (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 次瀏覽
廣告