这是悦乐书的第235次更新，第248篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第102题（顺位题号是455）。有1000个水桶，其中只有一个水桶含有毒药，其余的都没毒。它们看起来都一样。如果猪喝了那桶带有毒药的水，它会在15分钟内死亡。你需要在一小时内找出哪个桶中含有毒药的最小猪量是多少。回答这个问题，并为后续一般案例编写算法。
跟进：如果有n桶水，猪喝了带毒的水会在m分钟内死亡，那么你需要在p分钟内使用多少只猪（x）找出“毒药”桶？ 只有一个带毒药的桶。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 解题
题目里面的三个参数，buckets表示水桶数量，minutesToDie表示小猪喝了有毒的水需要多少分钟死，minutesToTest表示有多少分钟用来测试。最后两个参数合起来理解就是可以测试的次数。比如小猪喝了有毒的水15分钟后死，有60分钟来测试，那么我们就可以测试4次。题目要求返回的是小猪的数量。我们先来看几个例子，找下规律。
情况1：测试次数为1次，有2只小猪，最多可以测试多少个水桶？
我们将4个水桶标记为1,2,3,4，小猪a喝1和2，小猪b喝2和3。15分钟后，如果小猪a死了，说明水桶1有毒；如果小猪b死了，说明水桶3有毒；如果小猪a和b都死了，说明第2桶水有毒；如果两只小猪都没有死，说明水桶4有毒。测试次数为1次，有两只小猪，可以测试4个水桶。
情况2：测试次数还是为2次，有2只小猪，最多可以测试多少个水桶？
1 2 3
4 5 6
7 8 9
使用数字1到9来标记水桶，第一只猪a第一次喝第1,2,3桶水，第二次喝4,5,6,；第二只猪b第一次喝1,4,7，第二次喝2,5,8。如果在第一次，a和b都死了，说明1有毒；如果a第一次死了，b在第二次死了，说明2有毒。如果继续往下观察，可能有毒的水桶其实就是一个坐标，也可以理解为一个二维数组。
如果继续往上延伸，测试次数为2次，3只猪时，最多可以测27桶水。因此，三者之间的关系满足m的x次方等于能测的桶数。而m则是可以测试的次数加1。反过来，就可以通过取对数获得x的值。
public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
int count = minutesToTest/minutesToDie + 1;
return (int)Math.ceil(Math.log((double)buckets)/Math.log((double)count));
}
03 小结
算法专题目前已日更超过三个月，算法题文章102+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论