LeetCode-钥匙和房间

首先尝试用BFS算法，遍历到不同的钥匙，总房间数减一，最终房间数等于0，就是全部能进去

public boolean canVisitAllRooms(List<List<Integer>> rooms) { if (rooms == null || rooms.isEmpty()){ return false; } int roomNum = rooms.size(); if(roomNum == 1){ return true; } List<Integer> keys = rooms.get(0); if (keys == null || keys.size() <= 0){ return false; } Set<Integer> set = new HashSet<>(); Queue<Integer> queue = new LinkedList<>(); queue.offer(0); while (!queue.isEmpty() && roomNum != 0){ Integer poll = queue.poll(); if (set.contains(poll)){ continue; }else{ roomNum --; set.add(poll); List<Integer> keyList = rooms.get(poll); if (keyList != null && keyList.size() > 0){ keyList.forEach(k -> queue.offer(k)); } } } if (roomNum == 0){ return true; } return false; }

因为有限条路就能走遍所有房间的概率较大，所以DFS是要快一点的

private int roomNum; public boolean canVisitAllRooms(List<List<Integer>> rooms) { if (rooms == null || rooms.isEmpty()){ return false; } roomNum = rooms.size(); if(roomNum == 1){ return true; } boolean[] already = new boolean[roomNum]; dfs(rooms,already,0); if (roomNum == 0){ return true; } return false; } private void dfs(List<List<Integer>> rooms, boolean[] already, int key){ if (already[key]){ return; } roomNum --; already[key] = true; if (roomNum == 0){ return; } List<Integer> integers = rooms.get(key); if (integers.size() <= 0){ return; } for (int room : rooms.get(key)){ dfs(rooms, already, room); } }