LeetCode 841：鑰匙和房間 Keys and Rooms

  • 2019 年 10 月 7 日
  • 筆記

題目：

有 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。

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.

示例 1：

輸入: [[1],[2],[3],[]]  輸出: true  解釋:  我們從 0 號房間開始，拿到鑰匙 1。  之後我們去 1 號房間，拿到鑰匙 2。  然後我們去 2 號房間，拿到鑰匙 3。  最後我們去了 3 號房間。  由於我們能夠進入每個房間，我們返回 true。

示例 2：

輸入：[[1,3],[3,0,1],[2],[0]]  輸出：false  解釋：我們不能進入 2 號房間。

提示：

  1. 1 <= rooms.length <= 1000
  2. 0 &lt;= rooms[i].length &lt;= 1000
  3. 所有房間中的鑰匙數量總計不超過 3000。

Note:

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

解題思路：

很簡單的一道題，從0號房間開始遞歸遍歷就可以了。唯一需要注意的是如何判斷房間是否訪問過。可以用set哈希表把已訪問過的房間號記錄下來，最後如果哈希表長度和rooms長度相等，那麼就意味著所有房間均可到達。

程式碼：

Set集合(Java):

class Solution {      Set<Integer> set = new LinkedHashSet<>();        public boolean canVisitAllRooms(List<List<Integer>> rooms) {          helper(rooms, 0);          return set.size() == rooms.size();//長度相等則可以到達所有房間      }        private void helper(List<List<Integer>> rooms, int index) {          if (set.contains(index)) return;           set.add(index);//已訪問房間號加入哈希表          for (Integer i : rooms.get(index)) {//遍歷房間的每一個鑰匙                  helper(rooms, i);//進入遞歸          }      }  }

可以看到用哈希表解題方法在遞歸期間會多出許多set函數的調用，如 set.add() 、set.contains()，相對很多這道題解題時間，這個開銷是很大。對這道題而言，是完全可以用數組避免的。

Java：

class Solution {        public boolean canVisitAllRooms(List<List<Integer>> rooms) {          int len = rooms.size();          int[] visited = new int[len];//初始化等長數組，數組每個值默認為0          helper(rooms, 0, visited);          for (int i : visited)              if (i == 0) return false;//數組中依然有0，則證明有房間未訪問到          return true;      }        private void helper(List<List<Integer>> rooms, int index, int[] visited) {          if (visited[index] == 1) return;//如果該房間已訪問過，直接返回          visited[index] = 1;//在訪問    的房間，改為1來標記          for (Integer i : rooms.get(index)) {//遍歷              helper(rooms, i, visited);          }      }  }

Python：

class Solution:      def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:          size=len(rooms)          self.visited = [False]*size # 初始化等長數組，默認為False，所有房間均未訪問          self.helper(rooms, 0)          return all(self.visited)        def helper(self, rooms: List[List[int]], index: int) -> None:          if self.visited[index]:#如果為True，該房間已訪問過，直接返回              return          self.visited[index] = True #在訪問的房間標記為True          for i in rooms[index]:#遍歷鑰匙              self.helper(rooms, i)#進入遞歸函數

VirMach 便宜 VPS

QNews

QNews