本文共 1814 字，大约阅读时间需要 6 分钟。

1228. 可怜的猪：

有1000个桶，有且仅有一个桶里面装了毒药，其他的都装了水。这些桶从外面看上去完全相同。如果一只猪喝了毒药，它将在15分钟内死去。在一个小时内，至少需要多少只猪才能判断出哪一个桶里装的是毒药呢？

思考回答这个问题，随后请设计实现一个算法去处理更一般的情况。

样例 1

输入: 	buckets = 1000; minutesToDie = 15; minutesToTest = 60输出: 	5

挑战

假如一共有 n 个桶，只有一个桶装了毒药。一只猪将在喝完毒药 m 分钟后死去。你需要多少只猪才能在 p 分钟内找出那个装毒药的桶呢？

适用于所有人的分析

最直接的想法是有多少桶就需要多少头猪，然后哪个牺牲了，哪个桶里就是毒药。但是现实条件说中毒15分钟内必然死去，而我们有1个小时，也就是说一个小时内不同的死亡时间也是一个统计纬度，假如我们每个猪猪喝完所有水，但是时间不同，那么猪猪可能是15分钟死亡，30分死亡，45分死亡，60分死亡，60分没死亡也就代表会在75分死亡，这样就可以代表5种情况。每个猪猪只去测试一个桶，那太浪费了，我们要物尽其用。这里有个比较抽象的概念，五纬度，现实中比较好理解的是三维度(立体)，我先用更加简单的二纬度(平面)去举例子。

假设只给15分钟时间，也就是只能喝一次水。

我们用2头猪猪，让小猪1号按着行喝水，小猪2号按着列喝水。也就是小猪1号喝1和2号桶的水，小猪2号喝1和3号桶的水。结果如下：

• 小猪1号15分钟死亡，小猪2号也是15分钟死亡，那么肯定是1号桶有毒。
• 小猪1号15分钟死亡，小猪2号没死，那么肯定是2号桶有毒。
• 小猪1号没死亡，小猪2号是15分钟死亡，那么肯定是3号桶有毒。
• 小猪1号没死，小猪2号也没死，那么肯定是4号桶有毒。

回到题目，我们测试1次可以有2行2列，如果我们可以尝试4次，那么也就会变成5行，5列，也就是25桶。增加一头猪猪，就会推广到三维立体，也就是5行，5列，5层，一共就是125桶(这时候每头猪猪每次就喝一个平面里编号的桶)。每增加一头猪猪，可以认为就是多一个纬度。4头猪猪就会是625桶，5头猪猪就会是3125桶，足够测试1000个桶。虽然5头死掉的猪猪很惨，但是我们利用技巧，救了995头猪猪。推广到一般问题，那么其实就是幂次方的关系。

适用于专业人士的分析：

15分钟内必死，那么一个小时可以检查4个死亡时间，加上不死，一共5种情况。每头猪可以检查5种情况，可以理解为5进制，每增加一头猪就是增加一位5进制，可以表示的情况数就扩大5倍，可以用10进制和2进制类比。所以是5的幂次方。

题解

public class Solution {
       /**     * @param buckets: an integer     * @param minutesToDie: an integer     * @param minutesToTest: an integer     * @return: how many pigs you need to figure out the "poison" bucket within p minutes      */    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
           // Write your code here        if (buckets == 1) {
       		return 0;		}        int bits = minutesToTest / minutesToDie + 1;		int ret = bits;		int pigs = 1;		for (; ret < buckets; ++pigs) {
   			ret = ret * bits;		}		return pigs;    }}

最后说两句

非常感谢你阅读本文章，如果你觉得本文对你有所帮助，请留下你的足迹，点个赞，留个言，多谢~

作者水平有限，如果文章内容有不准确的地方，请指正。

希望小伙伴们都能每天进步一点点。

声明

本文由博客原创，转载请注明来源，谢谢~

转载地址：https://le-yi.blog.csdn.net/article/details/108899496 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！