ETH官方钱包

前往
大廳
主題

LeetCode - 2560. House Robber IV 解題心得

Not In My Back Yard | 2024-01-14 12:00:14 | 巴幣 0 | 人氣 157

題目連結:


題目意譯:
現在有連續若干間房子在一條街上,每一間都有一些錢在其中。現在同時有某個小偷,他想要從這些房子偷走一些錢,但是不想要同時偷兩間相鄰的住家。

小偷的「本領」定義為在他偷的所有房子中金額最大者。

你被給定一個整數陣列 nums 代表著每一間藏著多少錢。更正式地說,從左邊數過來第 i 間房子有著 nums[i] 元。

你同時也被給定一整數 k,代表著該小偷最少將會偷的房子之數量。測資保證可以偷至少 k 間房子。

回傳在所有小偷可以偷至少 k 間房子的方式之中的小偷本領最小值。

限制:
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 9
1 ≦ k ≦ (nums.length + 1)/2



範例測資:
範例 1:
輸入: nums = [2,3,5,9], k = 2
輸出: 5
解釋:
現在有三種方式可以偷至少 2 間房子:
- 偷位於索引值 0 和 2 的房子。本領值為 max(nums[0], nums[2] = 5)。
- 偷位於索引值 0 和 3 的房子。本領值為 max(nums[0], nums[3] = 9)。
- 偷位於索引值 1 和 3 的房子。本領值為 max(nums[1], nums[3] = 9)。
因此我們回傳 min(5, 9, 9) = 5。

範例 2:
輸入: nums = [2,7,9,3,1], k = 2
輸出: 2
解釋: 現在有 7 種偷這些房子的方式。其中可以得到最小本領值的方式為偷位於索引值 0 和 4 的房子。回傳 max(nums[0], nums[4]) = 2。


解題思維:
系列第一題的變化版。而這題的核心策略除了跟第一題一樣以外,還可以搭配對「答案」進行二分搜尋法(Binary Search)的手法,如這題

因為我們如果知道答案為 X,則我們如果試圖只偷那些藏錢量小於 X(也就是設定藏錢量的最高上限為 X - 1),將會必定偷不夠 k 間(不然答案至少應為 X - 1 或更小)。

也就是說,如果小偷盡量去偷的話。對於藏錢量最高上限為 0 ~ X - 1 之值,都會偷不夠 k 間;而對於 X ~ ∞ 之值,則都可以偷滿至少 k 間。

而可以看到這個藏錢量最高上限「幾乎」就是「本領值」(這個上限值會大於等於實際上的本領值;但是上限恰好等於未知的 X 值時必定剛好就是最小本領值)。



所以如果我們去隨便猜一個上限值 M,然後搭配第一題的策略來看可以偷多少間房子。也就是說把所有藏錢量小於等於 M 者設為 1、大於 M 者設為 0,然後照著原本的策略跑便會得到最大的「利潤」,而這實際上是我們要求的「最多可以偷幾間房子」。

如果發現這個 M 值得到 < k 的結果,則代表著這個上限值猜得太小了,需要猜大一點;反之,則代表「有機會」可以猜得小一點。而這部分就是固定的二分搜尋法之手法了。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作