458 可怜的小猪 进制猜想 & 香农熵验证

发表于

「这是我参与11月更文挑战的第 25 天，活动详情查看：2021最后一次更文挑战」。

题目描述

这是 LeetCode 上的 458. 可怜的小猪 ，难度为 困难。

Tag : 「数学」

有 buckets 桶液体，其中 正好 有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。

为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。

喂猪的规则如下：

  1. 选择若干活猪进行喂养
  2. 可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
  3. 小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
  4. 过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
  5. 重复这一过程，直到时间用完。

给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回在规定时间内判断哪个桶有毒所需的 最小 猪数。

示例 1：

1
2
3
ini复制代码输入：buckets = 1000, minutesToDie = 15, minutesToTest = 60

输出：5

示例 2：

1
2
3
ini复制代码输入：buckets = 4, minutesToDie = 15, minutesToTest = 15

输出：2

示例 3：

1
2
3
ini复制代码输入：buckets = 4, minutesToDie = 15, minutesToTest = 30

输出：2

提示：

  • 1<=buckets<=10001 <= buckets <= 10001<=buckets<=1000
  • 1<= minutesToDie<= minutesToTest<=1001 <= minutesToDie <= minutesToTest <= 1001<= minutesToDie<= minutesToTest<=100

数学

考虑到部分有宗教信仰的同学（我不是🤣），我们用实验对象来代指题干的小动物。同时为了方便，我们使用 nnn 代指有多少桶水，ddd 为实验对象的反应时间，ttt 为测试总时间。

根据题意，最大测试次数为 k=⌊td⌋k = \left \lfloor \frac{t}{d} \right \rfloork=⌊dt​⌋。

我们可以先考虑 k=1k = 1k=1 的情况，最简单的情况是，我们使用与水同等数量的实验对象数量来进行测试。

此时哪个实验对象有反应，则可以推断出哪一桶水有问题。

但这样的测试方式，每个实验动物承载的信息量是很低的，每个实验对象仅承载了某一桶水是否有问题。

为减少实验对象数量，我们需要增大每个实验对象承载的信息量（让每个实验对象同时测试多桶水），然后从最终所有实验对象的状态（是否有所反应）来反推哪一桶水有问题。

用最小单位表示最大信息量，这引导我们使用「进制表示」相关方式。由于我们只有 111 次测试机会，因此我们可以使用二进制的方式进行测试。

当 k=1k = 1k=1，使用二进制的方式测试哪桶水有问题，我们至少需要 mmm 个实验对象（其中 mmm 为 nnn 的二进制表示的长度），然后让编号为 xxx（0<=x<m0 <= x < m0<=x<m）的实验对象喝掉二进制表示中第 xxx 位为 111 的水。

最终这 mmm 个实验对象会对应一个结果序列：如果编号 x1x_1x1​ 的实验对象没有反应，说明有问题的水的二进制表示中第 x1x_1x1​ 位为 000，如果编号为 x2x_2x2​ 的实验对象有反应，则说明有问题的水的二进制表示中第 x2x_2x2​ 为 111。即根据最终每个实验对象的状态，我们可以完整地反推回有问题的水的编号是多少。

当 k>1k > 1k>1 时，相当于在原问题基础上，多考虑一层「轮数」维度，即不仅考虑某个实验对象是否有所反应，还需要考虑是在哪一轮有所反应。

我们还是使用「进制表示」的方式来最大化每个单位所能承载的最大信息量。

具体的，我们先使用 k+1k + 1k+1 进制对所有水进行编号，此时每桶水都有唯一的进制表示编码。然后我们考虑「什么时候」将水喂给「哪个实验对象」。

其中一种可行的测试方式是：设定需要的实验对象数量 mmm 为 k+1k + 1k+1 进制数的长度，若某桶水的 k+1k + 1k+1 进制中的第 xxx 位为 iii（0<=i<=k0 <= i <= k0<=i<=k），则代表将该水在第 iii 轮喂给编号为 xxx 的实验对象。

同理，利用最终的结果矩阵，我们可以反推回是哪一桶水是有问题的。

上述做法，只是阐述了我们存在这样的可行解，需要证明这样的做法是最优解。

利用 香农熵，我们可以计算明确熵值，公式为：

H(X)=−∑xP(x)log⁡2[P(x)]H(X) = - \sum_{x}^{} P(x) \log_2[P(x)]H(X)=−x∑​P(x)log2​[P(x)]
其中 P(x)P(x)P(x) 代表随机事件 xxx 的发生概率。

对于本题，记随机事件 AAA 为 nnn 桶水中哪一个桶有问题，概率为 1n\frac{1}{n}n1​。

记随机事件 BBB 为在测试轮数为 kkk 时，所有实验对象的最终状态，每个实验对象的状态共有 k+1k + 1k+1 种，即共有 C=(k+1)mC = (k + 1)^mC=(k+1)m 种最终结果，可近似看做等概率 1C\frac{1}{C}C1​。

我们需要求得在满足 H(A)<=H(B)H(A) <= H(B)H(A)<=H(B) 前提下的最小 mmm 值。

代入公式可得：

−(log⁡21n)<=−∑result=0(k+1)m1(k+1)mlog⁡21(k+1)m=mlog⁡2(k+1)-(\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)−(log2​n1​)<=−result=0∑(k+1)m​(k+1)m1​log2​(k+1)m1​=mlog2​(k+1)
移项化简得：

log⁡2nlog⁡2(k+1)<=m\frac{\log_2{n}}{\log_2{(k + 1)}} <= mlog2​(k+1)log2​n​<=m
代码：

1
2
3
4
5
6
Java复制代码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)O(1)
  • 空间复杂度：O(1)O(1)O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.458 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%