Skip to content

Latest commit

 

History

History
86 lines (47 loc) · 2.11 KB

0458._Poor_Pigs.md

File metadata and controls

86 lines (47 loc) · 2.11 KB

458. Poor Pigs

难度: Easy

刷题内容

原题连接

内容描述

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.

Follow-up:

If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the "poison" bucket within p minutes? There is exact one bucket with poison.

解题方案

思路 1 - 时间复杂度: O(1)- 空间复杂度: O(1)******

参考stefan

beats 100%

class Solution(object):
    def poorPigs(self, buckets, minutesToDie, minutesToTest):
        """
        :type buckets: int
        :type minutesToDie: int
        :type minutesToTest: int
        :rtype: int
        """
        pigs = 0
        while (minutesToTest / minutesToDie + 1) ** pigs < buckets:
            pigs += 1
        return pigs

思路 2 - 时间复杂度: O(1)- 空间复杂度: O(1)******

minutesToTest内可以尝试几次,设为t,那么我们要求最少的p使得t^p >= buckets

参考zzg_zzm, ckcz123

beats 100%

class Solution(object):
    def poorPigs(self, buckets, minutesToDie, minutesToTest):
        """
        :type buckets: int
        :type minutesToDie: int
        :type minutesToTest: int
        :rtype: int
        """
        return int(math.ceil(math.log(buckets)/math.log(minutesToTest//minutesToDie+1)))