Java实现 LeetCode 458 可怜的小猪
2023-09-14 08:58:05 时间
458. 可怜的小猪
有 1000 只水桶,其中有且只有一桶装的含有毒药,其余装的都是水。它们从外观看起来都一样。如果小猪喝了毒药,它会在 15 分钟内死去。
问题来了,如果需要你在一小时内,弄清楚哪只水桶含有毒药,你最少需要多少只猪?
回答这个问题,并为下列的进阶问题编写一个通用算法。
进阶:
假设有 n 只水桶,猪饮水中毒后会在 m 分钟内死亡,你需要多少猪(x)就能在 p 分钟内找出 “有毒” 水桶?这 n 只水桶里有且仅有一只有毒的桶。
提示:
可以允许小猪同时饮用任意数量的桶中的水,并且该过程不需要时间。
小猪喝完水后,必须有 m 分钟的冷却时间。在这段时间里,只允许观察,而不允许继续饮水。
任何给定的桶都可以无限次采样(无限数量的猪)。
PS:
如果 minutesToTest / minutesToDie = 0,那么每一只猪只有一种状态,即存活。
如果 minutesToTest / minutesToDie = 1,那么每一只猪有两种状态,存活或者死亡。
进一步而言,如果 minutesToTest / minutesToDie = 2,那么每一只猪有三种状态,存活、在第一次测试后死亡、在第二次测试后死亡。 因此每一只猪的状态数量为 states = minutesToTest / minutesToDie + 1。
1 只猪可以测试 1 个水桶
2 只猪可以测试 4 个水桶。
x 只猪可以测试 2^x 个水桶。
class Solution {
public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
int states = minutesToTest / minutesToDie + 1;
return (int) Math.ceil(Math.log(buckets) / Math.log(states));
}
}
相关文章
- java static 变量存在哪_Java中的静态方法和静态变量存储在哪里?
- java 阶乘算法_Java 实现阶乘算法
- java生成license_使用truelicense实现用于JAVA工程license机制(包括license生成和验证)…
- Java的定时器_JAVA定时任务
- java webservice接口开发教程_JAVA入门教程
- 数据库Java实现Oracle数据库监控(java监听oracle)
- 服务器实现Java远程访问Linux服务器(java远程linux)
- Java连接SQL Server:实现数据库完美对接(java链接sqlserver)
- 挑战未来:学习Linux与Java(学linux还是java)
- Java中使用Redis包实现高效缓存(redis包java)
- 使用Java连接MySQL实现查询功能(java连接mysql查询)
- Java编程实现MySQL表备份(java备份mysql表)
- Java实现MySQL数据插入(java插入mysql)
- Java与MySQL的无缝衔接:实现高效数据操作(java中使用mysql)
- 使用Java连接MySQL数据库的具体操作方法(java连接mysql代码)
- Linux测试搭配Java快速实现稳定性验证(linux测试java)
- Java迭代Oracle实现数据库更高性能(java迭代oracle)