专栏首页灵魂画师牧码画解算法 | 458.可怜的小猪

画解算法 | 458.可怜的小猪

力扣题解

自题解功能上线以来

题解区涌现了很多优质题解

如果你有更好的解题思路

不如来题解区大显身手

你可获得

1.力扣官方平台推荐

2.力扣积分

1篇精选题解:200 力扣积分

1篇优质题解:100 力扣积分

(注:题解著作版权归发布者本人所有)

本期精选题解由我们的用户“灵魂画师牧码”倾情撰写,一起来看看吧!

458.可怜的小猪(文末点击阅读原文查看题目)

题目描述

有 1000 只水桶,其中有且只有一桶装的含有毒药,其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药,它会在 15 分钟内死去。

问题来了,如果需要你在一小时内,弄清楚哪只水桶含有毒药,你最少需要多少只猪?

回答这个问题,并为下列的进阶问题编写一个通用算法。

进阶:

假设有 n 只水桶,猪饮水中毒后会在 m分钟内死亡,你需要多少猪 (x) 就能在 p分钟内找出 “有毒” 水桶?这 n 只水桶里有且仅有一只有毒的桶。

提示

  1. 可以允许小猪同时饮用任意数量的桶中的水,并且该过程不需要时间。
  2. 小猪喝完水后,必须有 m 分钟的冷却时间。在这段时间里,只允许观察,而不允许继续饮水。
  3. 任何给定的桶都可以无限次采样(无限数量的猪)。

解题方案

思路

标签:数学

这道题初看的时候,很多人会纠结:到底需要多少只小猪,而每只小猪又应该具体如何喝水才能判断出哪只水桶有毒药?

这道题最开始不要去关注细节,去想到底应该怎么喂水。而是应该先思考在考察哪方面的问题,数组、链表、二叉树还是数学?那么仔细思考就能得出结论,本质上在考察数学中的 进制 问题。

举例说明:

  • 假设:总时间 minutesToTest = 60,死亡时间 minutesToDie = 15,pow(x, y) 表示 x 的 y 次方,ceil(x)表示 x 向上取整
  • 当前有 1 只小猪,最多可以喝 times = minutesToTest / minutesToDie = 4 次水
  • 最多可以喝 4 次水,能够携带 base = times + 1 = 5 个的信息量,也就是(便于理解从 0 开始):
    • (1) 喝 0 号死去,0 号桶水有毒
    • (2) 喝 1 号死去,1 号桶水有毒
    • (3) 喝 2 号死去,2 号桶水有毒
    • (4) 喝 3 号死去,3 号桶水有毒
    • (5) 喝了上述所有水依然活蹦乱跳,4 号桶水有毒
    • 结论是1只小猪最多能够验证 5 桶水中哪只水桶含有毒药,当 buckets ≤ 5 时,answer = 1
  • 那么 2 只小猪可以验证的范围最多到多少呢?我们把每只小猪携带的信息量看成是base进制数,2 只小猪的信息量就是 pow(base, 2) = pow(5, 2) = 25,所以当 5 ≤ buckets ≤ 25时,anwser = 2
  • 那么可以得到公式关系:pow(base, ans) ≥ buckets,取对数后即为:ans ≥ log(buckets) / log(base),因为ans为整数,所以 ans = ceil(log(buckets) / log(base))

时间复杂度:O(1)

看到这里我们再去关注细节,2只小猪到底怎么喂水,在上述假设下,能够最多验证25桶水呢?请看下方图画解答:

动图:

图片分解:

代码

  • Java 版本
class Solution {
    public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int times = minutesToTest / minutesToDie;
        int base = times + 1;
        // base ^ ans >= buckets 
        // ans >= log(buckets) / log(base)
        double temp = Math.log(buckets) / Math.log(base);
        int ans = (int)Math.ceil(temp)
        return ans;
    }
}
  • JavaScript 版本
/**
 * @param {number} buckets
 * @param {number} minutesToDie
 * @param {number} minutesToTest
 * @return {number}
 */
var poorPigs = function(buckets, minutesToDie, minutesToTest) {
    const times = minutesToTest / minutesToDie;
    const base = times + 1;
    // base ^ ans >= buckets 
    // ans >= log(buckets) / log(base)
    const temp = Math.log(buckets) / Math.log(base);
    const ans = Math.ceil(temp)
    return ans;
};

本文作者:灵魂画师牧码

编辑&版式:霍霍

声明:本文归作者版权所有,如需转载请联系。

本文分享自微信公众号 - 牧码啦(mumalo)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 画解算法 7-整数反转

    https://leetcode-cn.com/problems/reverse-integer/

    灵魂画师牧码
  • 画解算法:14. 最长公共前缀

    https://leetcode-cn.com/problems/longest-common-prefix/

    灵魂画师牧码
  • 画解算法 171-Excel表列序号

    https://leetcode-cn.com/problems/excel-sheet-column-number/

    灵魂画师牧码
  • Java进阶之路——如何从程序员到架构师,从码农到专家Java进阶技术方面

    怎样学习才能从一名Java初级程序员成长为一名合格的架构师,或者说一名合格的架构师应该有怎样的技术知识体系,这是不仅一个刚刚踏入职场的初级程序员也是工作三五年之...

    美的让人心动
  • SAP最佳业务实践:使用看板的生产制造(233)-11重复制造反冲

    1、MFBF重复制造反冲 此活动在单个步骤中执行多个活动,如产成品的收货、组件物料的反冲、成本到成本收集器的过帐以及物料和会计凭证的创建。 反冲时可能会出现错误...

    SAP最佳业务实践
  • Singularity入门之通过镜像定义文件创建镜像

    下面以 Redis 数据库为例,主要说说 %startscript 和 %runscript 的区别。

    kongxx
  • 微信小程序 自定义组件样式

    组件对应 wxss 文件的样式,只对组件wxml内的节点生效。编写组件样式时,需要注意以下几点:

    天天_哥
  • Hive之导出文件按逗号分隔到本地文件

        如下所示,默认导出的是用\t分隔的,需要使用管道符进行转换,经常使用到,记录下.

    克虏伯
  • Lua table之弱引用

    Lua采用了基于垃圾收集的内存管理机制,因此对于程序员来说,在很多时候内存问题都将不再困扰他们。然而任何垃圾收集器都不是万能的,在有些特殊情况下,垃圾收集器是无...

    晚晴幽草轩轩主
  • 小白博客 反弹shell 在公网服务器执行 nc –lvv 8888

    Lua采用了基于垃圾收集的内存管理机制,因此对于程序员来说,在很多时候内存问题都将不再困扰他们。然而任何垃圾收集器都不是万能的,在有些特殊情况下,垃圾收集器是...

    奶糖味的代言

扫码关注云+社区

领取腾讯云代金券