【leetcode】458. Poor Pigs
1743 ワード
【leetcode】458. Poor Pigs
There are 1000 buckets, one and only one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket contains the poison within one hour.
Answer this question, and write an algorithm for the follow-up general case.
问题の大体の意味は1000桶の水があって、その中の1桶は毒の水で、かわいそうな豚はどの桶が毒があることをテストされて、豚が水を饮んで15分后に死ぬことを知っていて、少なくともどれだけの豚が1时间以内に毒の水を探し当てることができることを求めます.
試験例は上述のように、通常、60/15+1=5であり、豚1頭に5つの状態があることを5ラウンドで知る必要があり、15 min、30、45、60、die or aliveである.この時、私は経験上の誤解に陥った.以前、マウスの問題に遭遇したことがある.バケツをバイナリで番号付けしたが、ここでは豚が2つの状態だけでなく、5つの状態を持っていることに気づかなかった.だから、5進数でコードしなければならない.豚が1つだけなら、0、1、2、3、4の5つの状態しかない.2頭のブタであれば、最大で以下の符号化が可能であり、00,01,02,03,04,10,11,12,13,14,20,21,22,23,24,30,31,32,33,34,40,41,42,43,44の合計25個である.このように3頭の豚を押す..この符号化方式で唯一1つのバケツに対応し、5ラウンドが終わった後、2頭の豚が5つの状態の状態でどのバケツの水が毒があるかを判断する.だからn個の豚が確定できる符号化数は5のn次方である.
次はPythonのacコードです.テーマを理解してからコードが書きやすいです.
There are 1000 buckets, one and only one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket contains the poison within one hour.
Answer this question, and write an algorithm for the follow-up general case.
问题の大体の意味は1000桶の水があって、その中の1桶は毒の水で、かわいそうな豚はどの桶が毒があることをテストされて、豚が水を饮んで15分后に死ぬことを知っていて、少なくともどれだけの豚が1时间以内に毒の水を探し当てることができることを求めます.
試験例は上述のように、通常、60/15+1=5であり、豚1頭に5つの状態があることを5ラウンドで知る必要があり、15 min、30、45、60、die or aliveである.この時、私は経験上の誤解に陥った.以前、マウスの問題に遭遇したことがある.バケツをバイナリで番号付けしたが、ここでは豚が2つの状態だけでなく、5つの状態を持っていることに気づかなかった.だから、5進数でコードしなければならない.豚が1つだけなら、0、1、2、3、4の5つの状態しかない.2頭のブタであれば、最大で以下の符号化が可能であり、00,01,02,03,04,10,11,12,13,14,20,21,22,23,24,30,31,32,33,34,40,41,42,43,44の合計25個である.このように3頭の豚を押す..この符号化方式で唯一1つのバケツに対応し、5ラウンドが終わった後、2頭の豚が5つの状態の状態でどのバケツの水が毒があるかを判断する.だからn個の豚が確定できる符号化数は5のn次方である.
次はPythonのacコードです.テーマを理解してからコードが書きやすいです.
def poorPigs(self, buckets, minutesToDie, minutesToTest):
if buckets ==1 :
return 0
times = minutesToTest/minutesToDie + 1
ans = 1
while math.pow(times,ans) <= buckets:
ans += 1
return ans