换水问题
难度:
标签:
题目描述
超市正在促销，你可以用 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
代码结果
运行时间: 18 ms, 内存: 16.1 MB
/*
题目思路：
1. 使用Java Stream实现，类似于普通方法。
2. 每次兑换时，使用stream计算出新水瓶数并累加。
3. 重复计算直到无法再兑换。
*/
import java.util.stream.Stream;
public class WaterBottlesStream {
public int numWaterBottles(int numBottles, int numExchange) {
return Stream.iterate(new int[]{numBottles, 0}, p -> p[0] >= numExchange, p -> new int[]{p[0] / numExchange + p[0] % numExchange, p[1] + p[0] / numExchange})
.mapToInt(p -> p[1])
.sum() + numBottles;
}
}解释
方法:
此题解采用了模拟的方法来计算可以喝到的水的总瓶数。初始情况下，总喝水瓶数等于开始购买的水瓶数。在每次迭代中，首先检查当前空瓶的数量是否足以进行至少一次兑换。如果可以，则根据兑换比率计算出新兑换得到的水瓶数，并将这些新瓶加入到总瓶数中。同时更新空瓶数，新的空瓶数是未兑换的空瓶加上新兑换的水瓶产生的空瓶。重复此过程，直到空瓶不足以兑换一瓶水为止。
时间复杂度:
O(log_{numExchange}(numBottles))
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中提到的迭代次数是基于什么假设？为什么说是numExchange的对数？
▷🦆
如果numBottles小于numExchange，题解中的算法如何处理？还能正确返回结果吗？
▷🦆
题解中提到每次迭代空瓶数减少到原来的numExchange分之一，这个减少的逻辑是如何计算的？
▷🦆
在题解中，为什么没有考虑使用递归方法解决这个问题？递归方法会有什么潜在的缺点？
▷