从一道互联网面试题谈到 Leetcode 458（可怜的小猪）

最近我的一个朋友在面试某国内非常重视算法的公司时遇到了一道有趣的智力题，我在刷leetcode时也遇到相似的题目，总结一下分享给大家。

先来说说那道面试题，有8瓶药，其中只有一瓶是毒药，我们有三只老鼠，能被毒药很快毒死。请问最少几次能把毒药试出来？

这类题目，首先要明确的是，一只老鼠可以同时喝不止一瓶药水，否则就只能一瓶一瓶的试下去了。明确了这件事，问题就变成了三只老鼠分别喝了几瓶药水之后，有多少种状态的问题。

如果我们有一点数学中信息论的知识，甚至只要学过数字电子技术的话（好像暴露了专业），三只老鼠每一只都对应着死或者不死两种状态，而且是独立的，总的状态是2的3次方等于8。这道题中，药水的数量正好是8，所以答案是一天，我们甚至不用去关心具体的方案，就能得出本题的答案。

苦逼的码农备注：不大理解的可以继续看后面的题，就懂了

老鼠说，为什么总是我？

好了，饶过你，轮到可怜的小猪了。

甜点结束，正餐开始！

我们来看一看 leetcode 458 题

题目描述

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

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

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

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

提示：

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

解答

这两道题在本质上是一样的，看到这道题，直接去思考1000只水桶需要多少只猪有些困难，我们不妨采取自下而上的方法，先去想一只猪能够测试出几桶水，答案是5桶，15分钟死，30分钟死，45分钟死，60分钟死，活下来不死，这五种情况。

那么问题来了，两只猪呢？如果你再说是10桶就真的无可救药了，两只猪分别对应5种状态而且相互独立，5*5=25，三只呢，5的三次方等于125，四只呢，625，五只呢，等于几不知道，但肯定比1000大，第一个问题秒杀之，5只！

接下来，我们以两只猪为例关注一下细节，这两只猪是怎么喝水，测试出25桶水中哪一桶有毒呢？

第一只猪喝列的水的混合物，第二只猪喝行的水的混合物，最后一行和一列不喝。

比如说，按照这样的方案喝完水之后，第一只猪在45分钟死去，第二只猪在15分钟死去，则2号水有毒，若两只猪都平安无事，那么标号为24的水有毒。

好了，细节上的问题只是便于理解，不再赘述，我们来看推广：

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

相信有了前边两道题的热身之后，就不太难了。

先上代码：

public int poorPigs(int buckets, int minutesToDie, int minutesToTest){
        //buckets为桶数，例子中是1000，minutesToDie是15，minutesToTest是60
        int base=minutesToTest/minutesToDie+1;
        double temp=Math.log(buckets)/Math.log(base);//log是以e为底的对数
        return (int)Math.ceil(temp);//ceil向上取整
}