LeetCode 题解工作台
可怜的小猪
有 buckets 桶液体，其中 正好有一桶 含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。 喂猪的规则如下： 选择若干活猪进行喂养 可以允许小…
3
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
class Solution: def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
有 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 <= 10001 <= minutesToDie <= minutesToTest <= 100
解题思路
方法一
class Solution:
def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
base = minutesToTest // minutesToDie + 1
res, p = 0, 1
while p < buckets:
p *= base
res += 1
return res
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's understanding of state transition problems in dynamic programming.
- question_mark
Evaluate how well the candidate applies combinatorics to optimize the problem solution.
- question_mark
Check for a clear explanation of how binary representation is used to model outcomes.
常见陷阱
外企场景- error
Not considering the optimal distribution of pigs across buckets, leading to unnecessary pigs for fewer buckets.
- error
Overcomplicating the problem by not using binary or combinatorial representations effectively.
- error
Failing to account for the time constraints and misjudging how many pigs are needed based on the number of test rounds.
进阶变体
外企场景- arrow_right_alt
Increasing the number of buckets or test time constraints to assess scalability of the approach.
- arrow_right_alt
Allowing pigs to be reused across multiple tests, which changes the dynamic of how the problem is solved.
- arrow_right_alt
Introducing more than one poisonous bucket, requiring more sophisticated state transition models.