Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2022-12-20 09:17:22
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:
作者: plzza0cats (西黑百夫长)   2022-12-20 09:19:00
皇城版主搞N号房 我报警了
作者: pandix (面包屌)   2022-12-20 11:04:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com