付費限定

一題多解 能打開所有房間的門嗎? Keys and Rooms_Leetcode #841 精選75題

閱讀時間約 7 分鐘

題目敘述

題目會給我們一個房間陣列rooms,每個房間裡面擁有數量不等,可以打開其他房間的鑰匙。

每一道房間門預設都是鎖住的,只有0號房間的門一開始是打開的

請問,從0號房間開始拿鑰匙,最終能不能打開所有房間的門?


題目的原文敘述


測試範例

Example 1:

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.

0號們一開始就是打開的。​
0號房間可以拿到1號房間的鑰匙。
1號房間可以拿到2號房間的鑰匙。​
2號房間可以拿到3號房間的鑰匙。

可以打開所有房間的門。​

Example 2:

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.
不管怎麼走,都拿不到2號房間的鑰匙。
無解,返回False,​

約束條件

Constraints:

  • n == rooms.length

房間的總數目定義為n

  • 2 <= n <= 1000

房間的總數目n 介於 2 ~ 1000 之間。

  • 0 <= rooms[i].length <= 1000

每個房間內部可能有0~1000把鑰匙。

代表有些房間進去之後,拿不到別的鑰匙。

  • 1 <= sum(rooms[i].length) <= 3000

鑰匙的總數量介於1~3000把之間。

  • 0 <= rooms[i][j] < n

每把鑰匙都可以打開對應的門,不會有惡作劇無用的鑰匙。

  • All the values of rooms[i] are unique.

單獨每一間房間,內部擁有的鑰匙不會重複。


建立解題模型 與 演算法

以行動支持創作者!付費即可解鎖
本篇內容共 2916 字、1 則留言,僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容,可能因為尚未登入,或沒有該房間的查看權限。
avatar-img
88會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目敘述 題目會給我們一顆二元樹的根結點,請我們列出每一層最右邊的節點值,以陣列的形式返回答案。 題目的原文敘述 測試範例 Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] 每一層最右邊的節點值分別是1, 3,
題目敘述 題目會給定我們一個字串s,和一組字庫wordDict。 問我們能不能透過字串串接的方式,從字庫裡面的字拼成原本的字串s? 可以的話,返回True。 無解的話,返回False。 註: 題目還允許重複使用字庫裡面的字去串接。
題目敘述 題目會給定一個指定高度和寬的方格版,還有一顆小球的起始位置,和最大移動步數。 小球每一步可以選擇向上、下、左、右移動一格,請問小球能走到方格版界外的路徑方法數總共有幾種? 方法數可能很大,題目要求,最後回傳答案時,先對10^9+7做除法取餘數再回傳。 題目的原文敘述 約束條件
題目敘述 題目給定我們一顆二元樹的根節點,要求我們計算出從根節點到葉子節點的偽回文路徑路徑有幾條? 偽回文路徑路徑 的定義: 路徑經過重新排列之後,可以形成回文Palindrome,也就是頭尾鏡像對稱。 ​ 例如: 1 -> 3 -> 3 重新排列之後,可以形成 3 -> 1 -> 3
題目敘述 題目會給定一個字串陣列arr最為輸入,我們可以任意選擇一組不包含重複字元的陣列子序列,將字串進行串接,成為字串s,請問字串s的最大長度是多少? 例如: arr=["dog","cow","cat"] 我們可以選擇"dog", "cat"進行串接,得到的字串s="dogcat",s的
題目敘述 題目會給定我們一棵二元數Binary Tree的根結點。 問我們任意祖先節點和晚輩節點之間,最大的差值的絕對值是多少? 題目的原文敘述 測試範例 Example 1: Input: root = [8,3,10,1,6,null,14,null,null,4,7,13] Ou
題目敘述 題目會給我們一顆二元樹的根結點,請我們列出每一層最右邊的節點值,以陣列的形式返回答案。 題目的原文敘述 測試範例 Example 1: Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] 每一層最右邊的節點值分別是1, 3,
題目敘述 題目會給定我們一個字串s,和一組字庫wordDict。 問我們能不能透過字串串接的方式,從字庫裡面的字拼成原本的字串s? 可以的話,返回True。 無解的話,返回False。 註: 題目還允許重複使用字庫裡面的字去串接。
題目敘述 題目會給定一個指定高度和寬的方格版,還有一顆小球的起始位置,和最大移動步數。 小球每一步可以選擇向上、下、左、右移動一格,請問小球能走到方格版界外的路徑方法數總共有幾種? 方法數可能很大,題目要求,最後回傳答案時,先對10^9+7做除法取餘數再回傳。 題目的原文敘述 約束條件
題目敘述 題目給定我們一顆二元樹的根節點,要求我們計算出從根節點到葉子節點的偽回文路徑路徑有幾條? 偽回文路徑路徑 的定義: 路徑經過重新排列之後,可以形成回文Palindrome,也就是頭尾鏡像對稱。 ​ 例如: 1 -> 3 -> 3 重新排列之後,可以形成 3 -> 1 -> 3
題目敘述 題目會給定一個字串陣列arr最為輸入,我們可以任意選擇一組不包含重複字元的陣列子序列,將字串進行串接,成為字串s,請問字串s的最大長度是多少? 例如: arr=["dog","cow","cat"] 我們可以選擇"dog", "cat"進行串接,得到的字串s="dogcat",s的
題目敘述 題目會給定我們一棵二元數Binary Tree的根結點。 問我們任意祖先節點和晚輩節點之間,最大的差值的絕對值是多少? 題目的原文敘述 測試範例 Example 1: Input: root = [8,3,10,1,6,null,14,null,null,4,7,13] Ou
你可能也想看
Google News 追蹤
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
Thumbnail
昨天自己又測試了一下,感覺還是有優化的空間,又做了一些細微調整,目前我認為這個版本非常強悍了。
Thumbnail
有一次在家裡整理東西時,我的貓嚇到我了。因為當時就只有我一個人在家,所以非常的安靜。那你可能會想,貓咪走路不都沒有聲音的嗎?沒錯,正因為牠們走路都沒有聲音所以才更嚇人,因為當時並不曉得貓咪從自己後方走過來,完全沒有腳步聲的狀況下,只聽到了一個聲音,那就是呼吸聲。當下聽到急促的呼吸聲也沒有聯想到是自己
Thumbnail
「醫師啊,我從前體檢的血糖好像有一點超標,算不算糖尿病?需要再驗嗎?我平時都沒有不舒服,應該沒關係吧!」一到診間坐下,中年大叔就開口詢問:「我應該是健康的胖子,雖然這顆肚子消不下來,不過假日都有出門散步運動,體力還不錯。」語畢,滿意地拍拍自己的肚子。
Thumbnail
l 政府的教育目的到底是什麼? l 錯誤的目的、心態導致後面一連串的錯誤 l 我們可以如何跨出去?
Thumbnail
民事案件:不動產「借名登記」問題多!借名登記探究(一)-內部關係 不動產借名登記契約是否有效?是否違反民法上強制及禁止規定?如若有效,則不動產借名登記契約的性質為何?是消極信託還是類推適用民法的委任契約條文?
Thumbnail
童文薰律師在童溫層節目中整理出蔡英文一魚多吃的記錄 我其實蠻意外,在童文薰律師揭露蔡英文論文原稿一魚多吃之後,御用媒體會真的當回事發報導洗白的;因為這真的不是一般人會關心的事。但《芋傳媒》還真的引用了一個臉書粉專:《翻譯有要緊》的貼文煞有介事的這麼做了。
Thumbnail
本所許健鈴律師主持【歡迎搭乘,喜麗詩號】,從李佳庭社工的《你不伸手,他會在這裡躺多久?:一個年輕社工的掙扎與淚水》,談談幾個跟街友相關的法律問題。
Thumbnail
●2017印尼電影【愛的所有格 Posesif】有一種愛叫佔有 (普特莉馬利諾 阿迪帕提多肯 葛莉瑟達阿嘉莎 奇可庫尼阿萬) 這張海報跟在HamiVedio付費頻道【愛的所有格 Posesif】的預告片,是讓我驚豔的。
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
Thumbnail
昨天自己又測試了一下,感覺還是有優化的空間,又做了一些細微調整,目前我認為這個版本非常強悍了。
Thumbnail
有一次在家裡整理東西時,我的貓嚇到我了。因為當時就只有我一個人在家,所以非常的安靜。那你可能會想,貓咪走路不都沒有聲音的嗎?沒錯,正因為牠們走路都沒有聲音所以才更嚇人,因為當時並不曉得貓咪從自己後方走過來,完全沒有腳步聲的狀況下,只聽到了一個聲音,那就是呼吸聲。當下聽到急促的呼吸聲也沒有聯想到是自己
Thumbnail
「醫師啊,我從前體檢的血糖好像有一點超標,算不算糖尿病?需要再驗嗎?我平時都沒有不舒服,應該沒關係吧!」一到診間坐下,中年大叔就開口詢問:「我應該是健康的胖子,雖然這顆肚子消不下來,不過假日都有出門散步運動,體力還不錯。」語畢,滿意地拍拍自己的肚子。
Thumbnail
l 政府的教育目的到底是什麼? l 錯誤的目的、心態導致後面一連串的錯誤 l 我們可以如何跨出去?
Thumbnail
民事案件:不動產「借名登記」問題多!借名登記探究(一)-內部關係 不動產借名登記契約是否有效?是否違反民法上強制及禁止規定?如若有效,則不動產借名登記契約的性質為何?是消極信託還是類推適用民法的委任契約條文?
Thumbnail
童文薰律師在童溫層節目中整理出蔡英文一魚多吃的記錄 我其實蠻意外,在童文薰律師揭露蔡英文論文原稿一魚多吃之後,御用媒體會真的當回事發報導洗白的;因為這真的不是一般人會關心的事。但《芋傳媒》還真的引用了一個臉書粉專:《翻譯有要緊》的貼文煞有介事的這麼做了。
Thumbnail
本所許健鈴律師主持【歡迎搭乘,喜麗詩號】,從李佳庭社工的《你不伸手,他會在這裡躺多久?:一個年輕社工的掙扎與淚水》,談談幾個跟街友相關的法律問題。
Thumbnail
●2017印尼電影【愛的所有格 Posesif】有一種愛叫佔有 (普特莉馬利諾 阿迪帕提多肯 葛莉瑟達阿嘉莎 奇可庫尼阿萬) 這張海報跟在HamiVedio付費頻道【愛的所有格 Posesif】的預告片,是讓我驚豔的。