[Leetcode][第841题][JAVA][钥匙和房间][DFS][BFS]

墨蓝 2022-12-02 13:42 151阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

#### 【解答思路】 ####

当 xx 号房间中有 yy 号房间的钥匙时，我们就可以从 xx 号房间去往 yy 号房间。如果我们将这 nn 个房间看成有向图中的 nn 个节点，那么上述关系就可以看作是图中的 xx 号点到 yy 号点的一条有向边。

这样一来，问题就变成了给定一张有向图，询问从 00 号节点出发是否能够到达所有的节点。

用visit数组或者Set记录已经访问的节点

###### 1. DFS ######

使用深度优先搜索的方式遍历整张图，统计可以到达的节点个数，并利用数组 vis 标记当前节点是否访问过，以防止重复访问。  
**复杂度**  
![在这里插入图片描述][20200831102558270.png_pic_center]

class Solution { 
        boolean[] vis;
        int num;
    
        public boolean canVisitAllRooms(List<List<Integer>> rooms) { 
            int n = rooms.size();
            num = 0;
            vis = new boolean[n];
            dfs(rooms, 0);
            return num == n;
        }
    
        public void dfs(List<List<Integer>> rooms, int x) { 
            vis[x] = true;
            num++;
            for (int it : rooms.get(x)) { 
                if (!vis[it]) { 
                    dfs(rooms, it);
                }
            }
        }
    }

###### 2. BFS ######

用广度优先搜索的方式遍历整张图，统计可以到达的节点个数，并利用数组 vis /Set标记当前节点是否访问过，以防止重复访问。  
**复杂度**  
![在这里插入图片描述][20200831102653664.png_pic_center]

class Solution { 
        public boolean canVisitAllRooms(List<List<Integer>> rooms) { 
            int n = rooms.size(), num = 0;
            boolean[] vis = new boolean[n];
            Queue<Integer> que = new LinkedList<Integer>();
            vis[0] = true;
            que.offer(0);
            while (!que.isEmpty()) { 
                int x = que.poll();
                num++;
                for (int it : rooms.get(x)) { 
                    if (!vis[it]) { 
                        vis[it] = true;
                        que.offer(it);
                    }
                }
            }
            return num == n;
        }
    }

public boolean canVisitAllRooms(List<List<Integer>> rooms) { 
            Stack<Integer> a = new Stack<>();
            HashSet<Integer> set = new HashSet<Integer>();
            set.add(0);
            a.add(0);
            while(!a.isEmpty()){ 
                int i =a.pop();
                for(int j:rooms.get(i)){ 
                    if(!set.contains(j)){ 
                        a.add(j);
                        set.add(j);
                        if (rooms.size() == set.size()) return true;
                    }
                   
                }
    
            }
            return (rooms.size() == set.size()) ;
        }

#### 【总结】 ####

###### 1. DFS 递归回溯 BFS 队列 ######

###### 2.审题！！！ 思考后再行动 ######

转载链接：https://leetcode-cn.com/problems/keys-and-rooms/solution/yao-chi-he-fang-jian-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/334b6fcc204042aa8ebae24b23f2a1e0.png
[20200831102558270.png_pic_center]: /images/20221123/0c2c1f28bde54ea699d93ef446cc99fa.png
[20200831102653664.png_pic_center]: /images/20221123/ff9202fd03464a108c3bcbe1c99bf889.png