付費限定

一題多解 能打開所有房間的門嗎? 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題 解析+統整你目前無法檢視以下內容,可能因為尚未登入,或沒有該房間的查看權限。
86會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
題目敘述 題目會給我們一顆二元樹的根結點,請我們列出每一層最右邊的節點值,以陣列的形式返回答案。 題目的原文敘述 測試範例 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
美國總統大選只剩下三天, 我們觀察一整週民調與金融市場的變化(包含賭局), 到本週五下午3:00前為止, 誰是美國總統幾乎大概可以猜到60-70%的機率, 本篇文章就是以大選結局為主軸來討論近期甚至到未來四年美股可能的改變
Thumbnail
Faker昨天真的太扯了,中國主播王多多點評的話更是精妙,分享給各位 王多多的點評 「Faker是我們的處境,他是LPL永遠繞不開的一個人和話題,所以我們特別渴望在決賽跟他相遇,去直面我們的處境。 我們曾經稱他為最高的山,最長的河,以為山海就是盡頭,可是Faker用他28歲的年齡...
Thumbnail
昨天自己又測試了一下,感覺還是有優化的空間,又做了一些細微調整,目前我認為這個版本非常強悍了。
Thumbnail
有一次在家裡整理東西時,我的貓嚇到我了。因為當時就只有我一個人在家,所以非常的安靜。那你可能會想,貓咪走路不都沒有聲音的嗎?沒錯,正因為牠們走路都沒有聲音所以才更嚇人,因為當時並不曉得貓咪從自己後方走過來,完全沒有腳步聲的狀況下,只聽到了一個聲音,那就是呼吸聲。當下聽到急促的呼吸聲也沒有聯想到是自己
Thumbnail
「醫師啊,我從前體檢的血糖好像有一點超標,算不算糖尿病?需要再驗嗎?我平時都沒有不舒服,應該沒關係吧!」一到診間坐下,中年大叔就開口詢問:「我應該是健康的胖子,雖然這顆肚子消不下來,不過假日都有出門散步運動,體力還不錯。」語畢,滿意地拍拍自己的肚子。
Thumbnail
l 政府的教育目的到底是什麼? l 錯誤的目的、心態導致後面一連串的錯誤 l 我們可以如何跨出去?
Thumbnail
民事案件:不動產「借名登記」問題多!借名登記探究(一)-內部關係 不動產借名登記契約是否有效?是否違反民法上強制及禁止規定?如若有效,則不動產借名登記契約的性質為何?是消極信託還是類推適用民法的委任契約條文?
Thumbnail
童文薰律師在童溫層節目中整理出蔡英文一魚多吃的記錄 我其實蠻意外,在童文薰律師揭露蔡英文論文原稿一魚多吃之後,御用媒體會真的當回事發報導洗白的;因為這真的不是一般人會關心的事。但《芋傳媒》還真的引用了一個臉書粉專:《翻譯有要緊》的貼文煞有介事的這麼做了。
Thumbnail
本所許健鈴律師主持【歡迎搭乘,喜麗詩號】,從李佳庭社工的《你不伸手,他會在這裡躺多久?:一個年輕社工的掙扎與淚水》,談談幾個跟街友相關的法律問題。
Thumbnail
●2017印尼電影【愛的所有格 Posesif】有一種愛叫佔有 (普特莉馬利諾 阿迪帕提多肯 葛莉瑟達阿嘉莎 奇可庫尼阿萬) 這張海報跟在HamiVedio付費頻道【愛的所有格 Posesif】的預告片,是讓我驚豔的。
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
美國總統大選只剩下三天, 我們觀察一整週民調與金融市場的變化(包含賭局), 到本週五下午3:00前為止, 誰是美國總統幾乎大概可以猜到60-70%的機率, 本篇文章就是以大選結局為主軸來討論近期甚至到未來四年美股可能的改變
Thumbnail
Faker昨天真的太扯了,中國主播王多多點評的話更是精妙,分享給各位 王多多的點評 「Faker是我們的處境,他是LPL永遠繞不開的一個人和話題,所以我們特別渴望在決賽跟他相遇,去直面我們的處境。 我們曾經稱他為最高的山,最長的河,以為山海就是盡頭,可是Faker用他28歲的年齡...
Thumbnail
昨天自己又測試了一下,感覺還是有優化的空間,又做了一些細微調整,目前我認為這個版本非常強悍了。
Thumbnail
有一次在家裡整理東西時,我的貓嚇到我了。因為當時就只有我一個人在家,所以非常的安靜。那你可能會想,貓咪走路不都沒有聲音的嗎?沒錯,正因為牠們走路都沒有聲音所以才更嚇人,因為當時並不曉得貓咪從自己後方走過來,完全沒有腳步聲的狀況下,只聽到了一個聲音,那就是呼吸聲。當下聽到急促的呼吸聲也沒有聯想到是自己
Thumbnail
「醫師啊,我從前體檢的血糖好像有一點超標,算不算糖尿病?需要再驗嗎?我平時都沒有不舒服,應該沒關係吧!」一到診間坐下,中年大叔就開口詢問:「我應該是健康的胖子,雖然這顆肚子消不下來,不過假日都有出門散步運動,體力還不錯。」語畢,滿意地拍拍自己的肚子。
Thumbnail
l 政府的教育目的到底是什麼? l 錯誤的目的、心態導致後面一連串的錯誤 l 我們可以如何跨出去?
Thumbnail
民事案件:不動產「借名登記」問題多!借名登記探究(一)-內部關係 不動產借名登記契約是否有效?是否違反民法上強制及禁止規定?如若有效,則不動產借名登記契約的性質為何?是消極信託還是類推適用民法的委任契約條文?
Thumbnail
童文薰律師在童溫層節目中整理出蔡英文一魚多吃的記錄 我其實蠻意外,在童文薰律師揭露蔡英文論文原稿一魚多吃之後,御用媒體會真的當回事發報導洗白的;因為這真的不是一般人會關心的事。但《芋傳媒》還真的引用了一個臉書粉專:《翻譯有要緊》的貼文煞有介事的這麼做了。
Thumbnail
本所許健鈴律師主持【歡迎搭乘,喜麗詩號】,從李佳庭社工的《你不伸手,他會在這裡躺多久?:一個年輕社工的掙扎與淚水》,談談幾個跟街友相關的法律問題。
Thumbnail
●2017印尼電影【愛的所有格 Posesif】有一種愛叫佔有 (普特莉馬利諾 阿迪帕提多肯 葛莉瑟達阿嘉莎 奇可庫尼阿萬) 這張海報跟在HamiVedio付費頻道【愛的所有格 Posesif】的預告片,是讓我驚豔的。