LeetCode 题解工作台
换水问题
超市正在促销，你可以用 numExchange 个空水瓶从超市兑换一瓶水。最开始，你一共购入了 numBottles 瓶水。 如果喝掉了水瓶中的水，那么水瓶就会变成空的。 给你两个整数 numBottles 和 numExchange ，返回你 最多 可以喝到多少瓶水。 示例 1： 输入： numB…
2
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数学·结合·模拟
答案摘要
我们可以直接模拟整个过程。 初始时，我们有 `numBottles` 瓶水，因此可以喝到 `ans = numBottles` 瓶水，然后得到 `numBottles` 个空瓶子。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·结合·模拟 题型思路
题目描述
超市正在促销，你可以用 numExchange 个空水瓶从超市兑换一瓶水。最开始，你一共购入了 numBottles 瓶水。
如果喝掉了水瓶中的水，那么水瓶就会变成空的。
给你两个整数 numBottles 和 numExchange ，返回你 最多 可以喝到多少瓶水。
示例 1：
输入：numBottles = 9, numExchange = 3
输出：13
解释：你可以用 3 个空瓶兑换 1 瓶水。
所以最多能喝到 9 + 3 + 1 = 13 瓶水。
示例 2：
输入：numBottles = 15, numExchange = 4
输出：19
解释：你可以用 4 个空瓶兑换 1 瓶水。
所以最多能喝到 15 + 3 + 1 = 19 瓶水。
提示：
1 <= numBottles <= 1002 <= numExchange <= 100
解题思路
方法一：模拟
我们可以直接模拟整个过程。
初始时，我们有 numBottles 瓶水，因此可以喝到 ans = numBottles 瓶水，然后得到 numBottles 个空瓶子。
接下来，如果我们有 numExchange 个空瓶子，那么我们可以用它们兑换一瓶水并喝掉，此时我们剩余的空瓶子数量为 numBottles - numExchange + 1，然后我们累加喝到的水的数量，即 。
最后，返回 ans 即可。
时间复杂度 ，空间复杂度 。
class Solution:
def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
ans = numBottles
while numBottles >= numExchange:
numBottles -= numExchange - 1
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(\log_{M} N) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Assesses the candidate's ability to simulate a real-world process through efficient code.
- question_mark
Tests for clear and concise iteration handling within a loop.
- question_mark
Evaluates the candidate's attention to detail when managing both full and empty bottles.
常见陷阱
外企场景- error
Failing to correctly simulate the bottle exchange and drinking process.
- error
Not accounting for the scenario when no more full bottles can be obtained from empty ones.
- error
Overcomplicating the solution with unnecessary complexity or data structures.
进阶变体
外企场景- arrow_right_alt
Increase the number of empty bottles per exchange to test the candidate's ability to handle larger steps in the process.
- arrow_right_alt
Test with edge cases where the number of bottles is at its minimum (e.g., numBottles = 1).
- arrow_right_alt
Challenge with larger values for numBottles and numExchange to assess performance with bigger inputs.