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