跳转至

LeetCode: 458. 可怜的小猪

1、题目描述

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

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

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

进阶:

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

2、解题思路

​ 这个题目很巧妙,从头开始分析问题

  • 假如现在有一头猪,测试一次,能够确认几桶水呢?

​ 答案是2桶,喝一桶,如果没事,表示有毒的是另一桶

  • 如果同样是一头猪,测试两次呢?
1 2 3

让这头猪第一次喝1,第二次是2,只能是3桶

  • 如果是两头猪,测试一次,那么能够测试几桶水?

4桶,

1 2 3 4

是4桶,为什么呢?

两头猪有四种死亡状态,都没死,其中一个死,也就是第一个猪喝1,2,第二个猪是1,3,这样根据得到的4种状态,得到结果

  • 如果是两头猪,测试2次呢?
1 2 3
4 5 6
7 8 9

测试2次,就是一个二维的,第一头猪第一次喝1,2,3,第二头猪第一次喝1,4,7,假如两头猪都没事,

5 6
8 9

结果集变成了上面这样,两头猪就能直接测试4桶水了

如果第一头死了,那么剩下一头猪,结果集如下

2 3

第二头猪就能够测试两个数

​ 3头猪测试两次,能够测试多少呢?

​ 答案是27头,相当于上面的9头的,增加了一个维度,

​ 如果测试一次,那么n头猪最多是2^n

​ 也就是说,用猪的数量表示维度,测试次数加一,表示的是维度坐标长度,

​ 例如,2头猪,一次, 表示二维,维度长度是1+1 = 2

​ 3头猪,一次,三维,维度长度是2, 2*2*2 = 8

​ 3头猪,2次,三维,维度长度是3,3*3*3=27

​ 所以,就可以得出结果了

​ n头猪,测试次数是k,能够测试的数量就是 $$ (k+1)^{n} $$ ​ 所以,如果是m通水, $$ (k+1)^{n} >=m $$

​ 使用对数求解 $$ n * log(k+1) >= logm\ n >= \frac{logm}{log(k+1)} $$ ​ 在c中,math.h提供了ceil函数,天花板,表示求解党的等于当前数的最小整数

​ floor,地板,表示小于等于这个数的最大整数

int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
    return (int)ceil(log(buckets) / log(minutesToTest /minutesToDie +1));
}

​ 所以解题思路很重要啊,哈哈