LeetCode——458. 可怜的小猪（Java）

本文主要是介绍LeetCode——458. 可怜的小猪（Java），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述

题干：
有 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

题解思路

用最少的猪猪来测试出那一桶水是带毒的，这里就必须联想到经典的老鼠测毒的问题

采用二进制的方式来标记，最后根据每个老鼠的状态来确定二进制的每一个位数来找到那一瓶是毒药

当时只是记住了这种思想，但是丝毫没有考虑为什么采用二进制，而不用效率更高的高进制呢

遇到这道题之后才发现，原来具体几进制是根据最后结果的状态来确定的，老鼠的结果之后生和死

而这里的猪猪却有分时间的生死，因为他在每一次minutesToDie的时间后都有生死两种状态

这里就有了minutesToTest / minutesToDie + 1种状态，这里有用到了一个信息论的思想

这确实需要强大的数学功底才能验证，这里只运用结论的公式来解答，如果感兴趣可以自行去学习

正确代码

    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int times = minutesToTest / minutesToDie + 1;
        double time = Math.log(buckets) / Math.log(times);
        return (int)Math.ceil(time);
    }

总结

信息论中引用了“信息熵”的定义，它和化学中的熵有异曲同工之妙，意思也就是信息的不确定度

在我理解看来，只有一件事情的可能性大于所有的结果，这件事情才能一定成功，鄙人拙见

如果文章存在问题或者更好的题解，欢迎在评论区斧正和评论，各自努力，最高处见

这篇关于LeetCode——458. 可怜的小猪（Java）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！