Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間3年前 (2022/12/20 09:17)推噓1(1推 0噓 1→)

留言2則, 2人參與討論串144/719 (看更多)

841. Keys and Rooms 給定n個房間，每個房間都會放置0到n把鑰匙，第0個房間總是沒上鎖，求出有沒有辦法訪問所有房間。 Example： Input: rooms = [[1],[2],[3],[]] Output: true Explanation: We visit room 0 and pick up key 1. We then visit room 1 and pick up key 2. We then visit room 2 and pick up key 3. We then visit room 3. Since we were able to visit every room, we return true. Input: rooms = [[1,3],[3,0,1],[2],[0]] Output: false Explanation: We can not enter room number 2 since the only key that unlocks it is in that room. 法一 BFS 思路： 1.利用BFS來求解，首先把第0個房間的鑰匙加入queue，再來每輪從queue中取出一個鑰匙，若該房間還沒去過則把該房間的所有鑰匙也加入queue並標記該房間已經走訪過。 2.利用一個變數記錄開鎖的房間數量，最後檢查是否恰好開啟了n房間即可。 Java Code： ----------------------------- class Solution { public boolean canVisitAllRooms(List<List<Integer>> rooms) { int n = rooms.size(); int opened = 1; boolean[] visited = new boolean[n]; Queue<Integer> queue = new LinkedList<>(); visited[0] = true; for (int key : rooms.get(0)) { queue.offer(key); } while (!queue.isEmpty()) { int curKey = queue.poll(); if (!visited[curKey]) { for (int key : rooms.get(curKey)) { queue.offer(key); } visited[curKey] = true; opened++; } } return opened == n; } } ----------------------------- 法二 DFS 思路： 1.和1差不多改用DFS走訪 Java Code： ------------------------------ class Solution { public boolean canVisitAllRooms(List<List<Integer>> rooms) { Set<Integer> set = new HashSet<>(); dfs(rooms, set, 0); return set.size() == rooms.size(); } private void dfs(List<List<Integer>> rooms, Set<Integer> set, int i) { set.add(i); for (int key : rooms.get(i)) { if (!set.contains(key)) { dfs(rooms, set, key); } } } } ------------------------------ -- https://i.imgur.com/3e5CZfj.jpg