关于后端:综合笔试题难度-455超超超经典数学运用题

3次阅读

共计 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));
    }
}