🚀 算法題 🚀

🌲 算法刷題專欄 | 面試必備算法 | 面試高頻算法 🍀
🌲 越難的東西,越要努力堅持，因為它具有很高的價值，算法就是這樣?
🌲 作者簡介：碩風和煒，CSDN-Java領域優質創作者🏆，保研|國家獎學金|高中學習JAVA|大學完善JAVA開發技術棧|面試刷題|面經八股文|經驗分享|好用的網站工具分享💎💎💎
🌲 恭喜你發現一枚寶藏博主,趕快收入囊中吧🌻
🌲 人生如棋，我愿為卒，行動雖慢，可誰曾見我后退一步？🎯🎯

🚀 算法題 🚀

🚩 題目鏈接

• 841. 鑰匙和房間

? 題目描述

有 n 個房間，房間按從 0 到 n - 1 編號。最初，除 0 號房間外的其余所有房間都被鎖住。你的目標是進入所有的房間。然而，你不能在沒有獲得鑰匙的時候進入鎖住的房間。

當你進入一個房間，你可能會在里面找到一套不同的鑰匙，每把鑰匙上都有對應的房間號，即表示鑰匙可以打開的房間。你可以拿上所有鑰匙去解鎖其他房間。

給你一個數組 rooms 其中 rooms[i] 是你進入 i 號房間可以獲得的鑰匙集合。如果能進入 所有 房間返回 true，否則返回 false。

示例 1：

輸入：rooms = [[1],[2],[3],[]]
輸出：true
解釋：
我們從 0 號房間開始，拿到鑰匙 1。
之后我們去 1 號房間，拿到鑰匙 2。
然后我們去 2 號房間，拿到鑰匙 3。
最后我們去了 3 號房間。
由于我們能夠進入每個房間，我們返回 true。
示例 2：

輸入：rooms = [[1,3],[3,0,1],[2],[0]]
輸出：false
解釋：我們不能進入 2 號房間。

提示：

n == rooms.length
2 <= n <= 1000
0 <= rooms[i].length <= 1000
1 <= sum(rooms[i].length) <= 3000
0 <= rooms[i][j] < n
所有 rooms[i] 的值 互不相同

🌟 求解思路&實現代碼&運行結果

---

? DFS

🥦 求解思路

1. 該題通過DFS或者BFS來實現，從0位置開始，去找到可以從當前list.get(0)集合中所有可去向的房間，如果當前位置沒有走過，計數加1。遞歸結束后，判斷此時cnt和房間的個數是否相等，如果相等，返回true，否則返回false。
2. 有了基本的思路，接下來我們就來通過代碼來實現一下遞歸和迭代的解法。

🥦 實現代碼

class Solution {List<List<Integer>> rooms;boolean[] flag;int cnt;int n;public boolean canVisitAllRooms(List<List<Integer>> rooms) {this.rooms = rooms;this.flag = new boolean[rooms.size()];this.cnt = 0;dfs(0);return cnt == rooms.size();}private void dfs(int i) {cnt++;flag[i] = true;for (int next : rooms.get(i)) {if (!flag[next])dfs(next);}}}

🥦 運行結果

---

💬 共勉

最后，我想和大家分享一句一直激勵我的座右銘，希望可以與大家共勉！