Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者ZooseWu (動物園公告)時間2年前 (2023/10/29 18:29)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串472/719 (看更多)

458. Poor Pigs 給你b個桶子其中包含一個有毒的桶子你一共有t分鐘可以進行測試然後你可以拿去讓豬喝喝到有毒的桶會讓豬d分鐘後死亡正在等待中的豬不能再喝其他的桶請問當有b個桶子測試一次要d分鐘測驗時間共t分鐘的情況下回傳進行測試最少需要的豬隻數量 Input: b = 4, d = 15, t = 15 Output: 2 讓A豬喝1,2桶 B豬喝1,3桶判斷哪一桶有毒 A豬死亡:2桶 AB豬死亡:1桶 B豬死亡:3桶沒有豬死亡:4桶 Input: b = 4, d = 15, t = 30 Output: 2 我沒有找到這一題的正確餵法所以我沒有解出來這邊先講我的思路: 首先t跟d兩個可以簡化成可以測試的次數time time = floor(t/d) 然後我們要找到怎麼在有限次數內找到最佳解法我想到的實驗方法是類似雙蛋問題的解決方法可是這個方法不是最佳解稍微講一下思路就好如果我們有5隻豬可以測驗三次那我們第一次可以把桶分六堆讓每隻豬各喝其中一堆看哪一隻豬死掉沒死掉就是剩下一堆有毒之後把剩下的桶分五堆前四堆讓四隻豬測試最後剩下三隻豬用binary的方法讓豬混著喝可以測試最多8桶然後根據前面分堆可以得到5隻豬最多測試8*5*6=240桶然後還要判斷豬沒死掉的話那一堆可以多測的桶數但是這不是正解我就沒有研究下去了網路上的正解: 先計算我們一共可以測驗的次數time 如果time是4 代表我們可以分五堆然後我們把桶子以二維的方式排列 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 接下來第一隻豬第一次測驗喝第一欄(1 6 11 16 21) 第二隻豬第一次測驗喝第一列(1 2 3 4 5) 測驗四次之後看豬在什麼時候死掉如果第一隻豬第三次測驗死掉第二隻豬第四次測驗死掉代表第18桶有毒都沒死掉代表第25桶有毒這個方法可以讓我們透過兩隻豬及四次測驗分辨25個桶哪個有毒可以得到公式 (time + 1)^pig = bucket 但是我們要找的是豬的數量所以pig = log(time+1)bucket 然後log有公式 log(A)B = logB / logA TS code: function poorPigs (b: number, d: number, t: number): number { const r = Math.log(b) / Math.log(Math.floor(t / d) + 1) return r - Math.floor(r) > 0.001 ? Math.ceil(r) : Math.floor(r) } 我在交答案的時候被TypeScript搞了一次因為TS沒有整數只有浮點數我加一加冒出一個3.00000000000004 -- Zoosewu Yoututbe顯示PTT推文可以在各個網站追實況或Live時使用預覽圖: https://i.imgur.com/ZhtXdAJ.png