网站copyright写法,室内设计平面图库,开发者选项在哪里打开,温州排名推广【问题描述】[中等] 【解答思路】
当 xx 号房间中有 yy 号房间的钥匙时#xff0c;我们就可以从 xx 号房间去往 yy 号房间。如果我们将这 nn 个房间看成有向图中的 nn 个节点#xff0c;那么上述关系就可以看作是图中的 xx 号点到 yy 号点的一条有向边。
这样一来#xff…【问题描述】[中等] 【解答思路】
当 xx 号房间中有 yy 号房间的钥匙时我们就可以从 xx 号房间去往 yy 号房间。如果我们将这 nn 个房间看成有向图中的 nn 个节点那么上述关系就可以看作是图中的 xx 号点到 yy 号点的一条有向边。
这样一来问题就变成了给定一张有向图询问从 00 号节点出发是否能够到达所有的节点。
用visit数组或者Set记录已经访问的节点
1. DFS
使用深度优先搜索的方式遍历整张图统计可以到达的节点个数并利用数组 vis 标记当前节点是否访问过以防止重复访问。 复杂度
class Solution {boolean[] vis;int num;public boolean canVisitAllRooms(ListListInteger rooms) {int n rooms.size();num 0;vis new boolean[n];dfs(rooms, 0);return num n;}public void dfs(ListListInteger rooms, int x) {vis[x] true;num;for (int it : rooms.get(x)) {if (!vis[it]) {dfs(rooms, it);}}}
}
2. BFS
用广度优先搜索的方式遍历整张图统计可以到达的节点个数并利用数组 vis /Set标记当前节点是否访问过以防止重复访问。 复杂度
class Solution {public boolean canVisitAllRooms(ListListInteger rooms) {int n rooms.size(), num 0;boolean[] vis new boolean[n];QueueInteger que new LinkedListInteger();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(ListListInteger rooms) {StackInteger a new Stack();HashSetInteger set new HashSetInteger();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/
