力扣-钥匙和房间

思路分析

房间和钥匙的关系可抽象为有向图：
节点：房间编号（0~n-1）；
边：若房间 i 有钥匙 j，则存在一条从 i 到 j 的有向边。
问题转化为：从节点 0 出发，能否遍历图中所有节点？
解决思路：用深度优先搜索（DFS） 或广度优先搜索（BFS） 遍历，记录访问过的房间数量，最终判断是否等于总房间数。

代码实现

这里列出dfs遍历的写法

classSolution{intcount=0;boolean[]visit;publicbooleancanVisitAllRooms(List<List<Integer>>rooms){intn=rooms.size();visit=newboolean[n];dfs(rooms,0);returncount==n;}publicvoiddfs(List<List<Integer>>rooms,intidx){// 标记访问该房间visit[idx]=true;++count;for(intkey:rooms.get(idx)){if(!visit[key]){dfs(rooms,key);}}}}

复杂度分析

• 时间复杂度：O(n+m)（n 是房间数，m 是钥匙总数，每个房间 / 钥匙仅访问一次）；
• 空间复杂度：O(n)（递归栈深度 + visited 数组，最坏情况是链式房间：0→1→2→…→n-1，递归栈深度为 n）。