LeetCode 841:鍵と部屋Keys and Rooms

タイトル: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 <= rooms.length <= 1000

0 <= rooms[i].length <= 1000

すべての部屋の鍵の数は合計3000を超えません.

Note:

1 <= rooms.length <= 1000

0 <= rooms[i].length <= 1000

The number of keys in all rooms combined is at most 3000 .

問題解決の考え方:
簡単な問題ですが、0号室から再帰すればいいです.唯一注意しなければならないのは、部屋が訪問したかどうかをどのように判断するかです.アクセスした部屋番号をsetハッシュテーブルで記録することができ、最後にハッシュテーブルの長さとroomsの長さが等しい場合、すべての部屋が到着できることを意味します.
コード:
Setコレクション(Java):

class Solution {
    Set set = new LinkedHashSet<>();

    public boolean canVisitAllRooms(List> rooms) {
        helper(rooms, 0);
        return set.size() == rooms.size();//             
    }

    private void helper(List> rooms, int index) {
        if (set.contains(index)) return;
         set.add(index);//           
        for (Integer i : rooms.get(index)) {//          
                helper(rooms, i);//    
        }
    }
}

ハッシュテーブルで問題を解く方法では、set.add()、set.contains()など、再帰中に多くのset関数の呼び出しが多く、この問題を解く時間が比較的多く、このオーバーヘッドが大きいことがわかります.この問題にとって,配列で完全に回避できる.
Java:

class Solution {

    public boolean canVisitAllRooms(List> 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> 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)#      

微.信公.衆号:Bugを書くのが好きです