leetcode458.可怜的小猪

题目链接

题目描述:

有 1000 只水桶，其中有且只有一桶装的含有毒药，其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药，它会在 15 分钟内死去。

问题来了，如果需要你在一小时内，弄清楚哪只水桶含有毒药，你最少需要多少只猪？

回答这个问题，并为下列的进阶问题编写一个通用算法。

进阶:

假设有 n 只水桶，猪饮水中毒后会在 m 分钟内死亡，你需要多少猪（x）就能在 p 分钟内找出 “有毒” 水桶？这 n 只水桶里有且仅有一只有毒的桶。

提示：

可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
小猪喝完水后，必须有 m 分钟的冷却时间。在这段时间里，只允许观察，而不允许继续饮水。
任何给定的桶都可以无限次采样（无限数量的猪）。

题解：数学

对于本题，假设毒药的药效为15min,要求在1h之内弄清有毒的水桶。

一只猪最多可以验证五个桶：假设只有五个桶，其中一只桶是有毒的。这只小猪一个小时总共可以喝四次，如果小猪还没有死，那么验证了第五只桶是毒桶。

那么两只猪可以验证多少只桶呢？

答案是25只桶。具体请参考这篇 题解

通过上面的分析可以得出，假设需要n只猪，需要满足：

base = minutesToTest/minutesToDie + 1
base ^ n >= buckets

通过上式可以得到 n 的表达式为：

n >= Math.log(buckets) / Math.log(base)

即：

n = Math.ceil(Math.log(buckets) / Math.log(base))

代码如下：

class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int base = minutesToTest/minutesToDie + 1;
        // base ^ res >= buckets 
        // res >= Math.log(buckets) / Math.log(base)
        // res = Math.ceil(Math.log(buckets) / Math.log(base))
        return (int)Math.ceil(Math.log(buckets) / Math.log(base));
    }
}

时间复杂度：O(1)
额外空间复杂度：O(1)

执行结果如下：