LeetCode 1518. 换水问题
题目描述
题意分析
最初有若干满水瓶，喝完后变成空瓶；每
numExchange个空瓶可以换一瓶新水，新水喝完又会留下空瓶。求整个过程最多能喝多少瓶。兑换比例始终不变，已有的水都可以喝完，够数的空瓶也都可以继续兑换。因此按轮模拟“喝完本轮水，再兑换下一轮水”，直到无法获得新水即可。
解法：按轮模拟喝水和兑换
核心思路
[!blue]
numBottles表示本轮还没喝的满瓶数，empty表示上一轮兑换后留下的空瓶，answer表示累计喝水量。先把本轮满瓶全部喝掉，让answer和empty都增加numBottles。此时设共有
S个空瓶，兑换门槛为E，可以换出S/E瓶水，并留下S%E个空瓶。商成为下一轮的满瓶数，余数必须保留，之后还能与新喝完的空瓶合并。代码先计算商，再把empty覆盖为余数，保证两个计算都使用兑换前的完整数量。只要还有满瓶，喝掉就能增加答案，而且不会减少后续兑换机会；够数的空瓶马上兑换也不会比延后兑换少得水，因为比例不变。循环一直执行这些可用操作，停止时既没有满瓶，空瓶数又小于门槛，已经没有办法继续喝水，因此得到最大值。
题目保证
E >= 2。每兑换并喝掉一瓶水，空瓶数量净减少E-1，所以兑换不可能无限继续。初始瓶数不足兑换门槛时，也会在喝完第一轮后自然结束。
解题步骤
- 初始化
answer = 0、empty = 0，输入的numBottles作为第一轮满瓶数。- 只要
numBottles > 0，就把这些水计入答案，并把喝完产生的空瓶加入empty。- 令
numBottles = empty/numExchange，得到下一轮满瓶数。- 令
empty %= numExchange，保留兑换后剩余的空瓶。- 没有满瓶后返回累计答案。
代码实现
class Solution {
public int numWaterBottles(int numBottles, int numExchange) {
int answer = 0;
// empty 含上一轮兑换后剩下的找零，不能丢弃。
int empty = 0;
// 有满水就一定会喝，用满瓶数作为终止条件。
while (numBottles > 0) {
// 两行都基于本轮的满瓶数，必须在覆盖 numBottles 之前执行。
answer += numBottles;
// 本轮喝完的瓶子与以前余下的空瓶共同参与兑换。
empty += numBottles;
// 整数除法天然表达「只能换整瓶」。
numBottles = empty / numExchange;
// 先算兑换再取余，顺序反了会用被截断的空瓶数去换。
empty %= numExchange;
}
return answer;
}
}
func numWaterBottles(numBottles int, numExchange int) int {
answer := 0
// empty 含上一轮兑换后剩下的找零，不能丢弃。
empty := 0
// 有满水就一定会喝，用满瓶数作为终止条件。
for numBottles > 0 {
// 两行都基于本轮的满瓶数，必须在覆盖 numBottles 之前执行。
answer += numBottles
// 本轮喝完的瓶子与以前余下的空瓶共同参与兑换。
empty += numBottles
// 整数除法天然表达「只能换整瓶」。
numBottles = empty / numExchange
// 先算兑换再取余，顺序反了会用被截断的空瓶数去换。
empty %= numExchange
}
return answer
}
复杂度分析
- 时间复杂度：$O(\log(N+1))$ 上界，
N为初始瓶数。每轮开始时余下空瓶R < E，若本轮满瓶为F，下一轮满瓶至多为ceil(F/E)；当F > 1时，下一轮满瓶数-1 <= (F-1)/E，因此这一数量按比例缩小。进入只剩一瓶的阶段后，最多再执行两轮，避免把余数影响误说成每轮满瓶都严格减半。- 空间复杂度：$O(1)$。只维护满瓶数、空瓶余数和累计答案。
关键点总结
[!green]
- 本轮先喝水，再用新产生的空瓶和此前余数一起兑换。
- 商表示下一轮的新水，余数表示仍可留到下一轮的空瓶，两者都不能遗漏。
- 满瓶为零时，空瓶已经是小于兑换门槛的余数，循环可以直接结束。
易错点总结
[!yellow]
- 只计算第一次兑换，忽略新水喝完后还能继续产生空瓶。
- 丢掉每轮余数，会漏掉它与新空瓶凑成的后续兑换。
- 先把
empty取余再计算商，得到的空瓶数已经不足一次兑换，会提前终止。- 在累加答案和空瓶之前覆盖
numBottles，会把本轮喝水量错误地换成下一轮的量。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 3100. 换水问题 II | 中等 | 本题兑换比率固定，原题每次兑换后提高比率，需要逐步维护新的兑换条件。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！