ETH官方钱包

前往
大廳
主題

LeetCode - 2305. Fair Distribution of Cookies 解題心得

Not In My Back Yard | 2023-04-27 12:00:01 | 巴幣 1000 | 人氣 420

題目連結:


題目意譯:
你被給定一整數陣列 cookies,其中 cookies[i] 代表第 i 個袋子中的餅乾數量。你同時被給定一整數 k 代表著要給予裝著餅乾的袋子之小孩數量。同一袋子中的餅乾必須給予至同一位小孩,不得分拆。

一個分配方式的不公平性定義為在分配方式中單一小孩得到的最大餅乾總數。

回傳所有分配方式中最小的不公平性。

限制:
2 ≦ cookies.length ≦ 8
1 ≦ cookies[i] ≦ 10 ^ 5
2 ≦ k ≦ cookies.length


範例測資:
範例 1:
輸入: cookies = [8,15,10,20,8], k = 2
輸出: 31
解釋: 其中一個最佳分配方式為 [8,15,8] 和 [10,20]
- 第一個小孩收到 [8,15,8],其有著總計 8 + 15 + 8 = 31 塊餅乾。
- 第二個小孩收到 [10,20],其有著總計 10 + 20 = 30 塊餅乾。
該分配方式的不公平性為 max(31,30) = 31。
可以證明不存在其他分配方式的不公平性小於 31。

範例 2:
輸入: cookies = [6,1,3,2,2,4,1,2], k = 3
輸出: 7
解釋: 其中一個最佳分配方式為 [6,1] 、 [3,2,2] 和 [4,1,2]
- 第一個小孩收到 [8,15,8],其有著總計 6 + 1 = 7 塊餅乾。
- 第二個小孩收到 [10,20],其有著總計 3 + 2 + 2 = 7 塊餅乾。
- 第三個小孩收到 [10,20],其有著總計 4 + 1 + 2 = 7 塊餅乾。
該分配方式的不公平性為 max(7,7,7) = 7。
可以證明不存在其他分配方式的不公平性小於 7。


解題思維:
(令 n = cookies.length)
直接窮舉出每一種分配的可能性即可,即 k ^ n 種。

如果嫌太慢的話,可以把「當前最小值」(也就是先前窮舉的方式中不公平性最小的,而根據定義其為某一分配方式中的餅乾最大值)作為遞迴條件。

也就是說,如果把某袋餅乾給了某位小孩後會使得該小孩擁有超過「當前最小值」的話,則就不繼續遞迴下去(該袋餅乾就改成給別的小孩),因為一定不會比較好。

這個方式稱之為「剪枝」(Pruning),因為遞迴過程可以看成是一棵樹,而我們做的就是把不可能成為答案的「樹枝」給「剪掉」。




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

創作回應

屌面大公雞
請問這題用memorize有什麼想法嗎?
我一開始用cookie index & zeroCount (零個背包的孩子數量)當做state variable
暴力解會對,但加上memorization就錯了

2023-07-02 13:28:01
Not In My Back Yard
可以分享兩次(暴力解以及後來寫的 memorization)各自的 code 嗎?
2023-07-02 13:36:09
屌面大公雞
可以的我截個圖
2023-07-02 13:39:45
屌面大公雞
https://truth.bahamut.com.tw/s01/202307/1746f5cb4533c697e129a4897f578dca.JPG
2023-07-02 13:40:36
屌面大公雞
試過用i當作state variable或是i & zeroCount都不對https://truth.bahamut.com.tw/s01/202307/22406494aaa7b6f100d0d8a7efc316d8.JPG
2023-07-02 13:42:46
Not In My Back Yard
不是很懂 m - i < zeroCount 這個停止條件。
2023-07-02 14:27:37

更多創作