共计 2423 个字符，预计需要花费 7 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 458. 可怜的小猪 ，难度为 艰难。
Tag :「数学」
有 buckets 桶液体，其中 正好 有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。
为了弄清楚哪只水桶含有毒药，你能够喂一些猪喝，通过观察猪是否会死进行判断。可怜的是，你只有 minutesToTest 分钟工夫来确定哪桶液体是有毒的。
喂猪的规定如下：
- 抉择若干活猪进行喂养
- 能够容许小猪同时饮用任意数量的桶中的水，并且该过程不须要工夫。
- 小猪喝完水后，必须有
minutesToDie分钟的冷却工夫。在这段时间里，你只能察看，而不容许持续喂猪。 - 过了
minutesToDie分钟后，所有喝到毒药的猪都会死去，其余所有猪都会活下来。 - 反复这一过程，直到工夫用完。
给你桶的数目 buckets，minutesToDie 和 minutesToTest，返回在规定工夫内判断哪个桶有毒所需的 最小 猪数。
示例 1：
输出：buckets = 1000, minutesToDie = 15, minutesToTest = 60
输入：5示例 2：
输出：buckets = 4, minutesToDie = 15, minutesToTest = 15
输入：2示例 3：
输出：buckets = 4, minutesToDie = 15, minutesToTest = 30
输入：2提醒：
- $1 <= buckets <= 1000$
- $1 <= minutesToDie <= minutesToTest <= 100$
数学
咱们用试验对象来代指题干的小动物。同时为了不便，咱们应用 $n$ 代指有多少桶水，$d$ 为试验对象的反应时间，$t$ 为测试总工夫。
依据题意，最大测试次数为 $k = \left \lfloor \frac{t}{d} \right \rfloor$。
咱们能够先思考 $k = 1$ 的状况，最简略的状况是，咱们应用与水等同数量的试验对象数量来进行测试。
此时哪个试验对象有反馈，则能够推断出哪一桶水有问题。
但这样的测试形式，每个试验动物承载的信息量是很低的，每个试验对象仅承载了某一桶水是否有问题。
为缩小试验对象数量，咱们须要增大每个试验对象承载的信息量（让每个试验对象同时测试多桶水），而后从最终所有试验对象的状态（是否有所反馈）来反推哪一桶水有问题。
用最小单位示意最大信息量，这疏导咱们应用「进制示意」相干形式。因为咱们只有 $1$ 次测试机会，因而咱们能够应用二进制的形式进行测试。
当 $k = 1$，应用二进制的形式测试哪桶水有问题，咱们至多须要 $m$ 个试验对象（其中 $m$ 为 $n$ 的二进制示意的长度），而后让编号为 $x$（$0 <= x < m$）的试验对象喝掉二进制示意中第 $x$ 位为 $1$ 的水。
最终这 $m$ 个试验对象会对应一个后果序列：如果编号 $x_1$ 的试验对象没有反馈，阐明有问题的水的二进制示意中第 $x_1$ 位为 $0$，如果编号为 $x_2$ 的试验对象有反馈，则阐明有问题的水的二进制示意中第 $x_2$ 为 $1$。即依据最终每个试验对象的状态，咱们能够残缺地反推回有问题的水的编号是多少。
当 $k > 1$ 时，相当于在原问题根底上，多思考一层「轮数」维度，即不仅思考某个试验对象是否有所反馈，还须要思考是在哪一轮有所反馈。
咱们还是应用「进制示意」的形式来最大化每个单位所能承载的最大信息量。
具体的，咱们先应用 $k + 1$ 进制对所有水进行编号，此时每桶水都有惟一的进制示意编码。而后咱们思考「什么时候」将水喂给「哪个试验对象」。
其中一种可行的测试形式是：设定须要的试验对象数量 $m$ 为 $k + 1$ 进制数的长度，若某桶水的 $k + 1$ 进制中的第 $x$ 位为 $i$（$0 <= i <= k$），则代表将该水在第 $i$ 轮喂给编号为 $x$ 的试验对象。
同理，利用最终的后果矩阵，咱们能够反推回是哪一桶水是有问题的。
上述做法，只是论述了咱们存在这样的可行解，须要证实这样的做法是最优解。
利用 香农熵，咱们能够计算明确熵值，公式为：
$$
H(X) = – \sum_{x}^{} P(x) \log_2[P(x)]
$$
其中 $P(x)$ 代表随机事件 $x$ 的产生概率。
对于本题，记随机事件 $A$ 为 $n$ 桶水中哪一个桶有问题，概率为 $\frac{1}{n}$。
记随机事件 $B$ 为在测试轮数为 $k$ 时，所有试验对象的最终状态，每个试验对象的状态共有 $k + 1$ 种，即共有 $C = (k + 1)^m$ 种最终后果，可近似看做等概率 $\frac{1}{C}$。
咱们须要求得在满足 $H(A) <= H(B)$ 前提下的最小 $m$ 值。
代入公式可得：
$$
-(\log_2{\frac{1}{n}}) <= – \sum_{result = 0}^{(k + 1)^m} \frac{1}{(k + 1)^m} \log_2{\frac{1}{(k + 1)^m}} = m \log_2(k + 1)
$$
移项化简得：
$$
\frac{\log_2{n}}{\log_2{(k + 1)}} <= m
$$
代码：
class Solution {public int poorPigs(int n, int d, int t) {
int k = t / d;
return (int) Math.ceil(Math.log(n) / Math.log(k + 1));
}
}- 工夫复杂度：$O(1)$
- 空间复杂度：$O(1)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.458 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
