有 buckets 桶液体，其中 正好 有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。
喂猪的规则如下：
选择若干活猪进行喂养
可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
重复这一过程，直到时间用完。
给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回在规定时间内判断哪个桶有毒所需的 最小 猪数。
例子:
输入：buckets = 1000, minutesToDie = 15, minutesToTest = 60
输出：5
输入：buckets = 4, minutesToDie = 15, minutesToTest = 15
输出：2
输入：buckets = 4, minutesToDie = 15, minutesToTest = 30
输出：2
解题思路:
这道题代码量不多, 重点考察数学思维
我们以 minutesToDie = 15, minutesToTest = 60 举例
minutesToTest / minutesToDie = 60 / 15 = 4, 可看出规定时间内可测4轮, 那么我们看下1只猪每次1桶水最多可测几桶
1.喝1桶, 0 ~ 15 内GG, 1桶有毒, 否则继续
2.喝2桶, 15 ~ 30 内GG, 2桶有毒, 否则继续
3.喝3桶, 30 ~ 45 内GG, 3桶有毒, 否则继续
4.喝4桶, 45 ~ 60 内GG, 4桶有毒, 否则继续
5.都没有则5桶有毒
那么有规定时间内1猪1桶, 最多测 minutesToTest / minutesToDie + 1 = 5
即: 1只小猪的状态信号为 states = minutesToTest / minutesToDie + 1，这里状态信号是1只小猪测试出的状态(在可测试的次数的范围内)。
我们看下多猪多桶1次最多喝多少
1只猪, 喝1桶, 1次GG, 1桶有毒, 否则2桶有毒, 最多2桶
2只猪, 1号猪和1, 2桶, 2号猪喝2, 3桶
① 仅1猪GG, 则1号桶有毒
② 仅2猪GG, 则3号桶有毒
③ 仅1,2猪GG, 则2号桶有毒
④ 否则4号桶有毒
可看出, 最多4桶
.....
这里主要是便于理解这个交叉的思路,
我们接着看下多猪多桶多次
还是以 minutesToDie = 15, minutesToTest = 60 举例, 状态信号为 states = 5
1只猪, 4次验证, 总共可验证5桶
(上面已举例)
2只猪, 4次验证, 总共可验证25桶
这里其实多了个时间差概念
示例图
号猪按行喝, 2号猪按列喝
第一次 1号猪喝1, 2, 3, 4, 5桶, 2号猪喝1, 6, 7, 8, 9桶
第二次 1号猪喝6, 7, 8, 9, 15桶, 2号猪喝2, 7, 12, 17, 22桶
......
① 0~15 都GG则1桶有毒
② 0~15 1猪GG, 15~30 2猪GG, 则2桶有毒
③ 0~15 1猪GG, 2猪通过无GG, 则5桶有毒
......
后面同理
.....
最后可得出 n只猪最多可验证 桶, 即
那么我们已知桶总数buckets, 信号 minutesToTest / minutesToDie + 1 = status, 即 求 n
(对数运算)
(如果 ，即
的
次方等于
(
且
!=
)，那么数
叫做以
为底
的对数，记作
其中,
叫做对数的底数,
叫做真数,
叫做以
为底
的对数”。)
接下来, 用换底公式, 有
换底公式
留意需要结果需要向上取整, 不能四舍五入(向上取整方法ceil())
代码
func poorPigs(_ buckets: Int, _ minutesToDie: Int, _ minutesToTest: Int) -> Int {
let states = minutesToTest / minutesToDie + 1;
return Int(ceil(log(Double(buckets)) / log(Double(states))));
}
题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址
网友评论