1518. 换水问题

🟢   🔖  数学 模拟  🔗 力扣 LeetCode

题目

There are numBottles water bottles that are initially full of water. You can exchange numExchange empty water bottles from the market with one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Given the two integers numBottles and numExchange, return themaximum number of water bottles you can drink.

Example 1:

Input: numBottles = 9, numExchange = 3

Output: 13

Explanation: You can exchange 3 empty bottles to get 1 full water bottle.

Number of water bottles you can drink: 9 + 3 + 1 = 13.

Example 2:

Input: numBottles = 15, numExchange = 4

Output: 19

Explanation: You can exchange 4 empty bottles to get 1 full water bottle.

Number of water bottles you can drink: 15 + 3 + 1 = 19.

Constraints:

• 1 <= numBottles <= 100
• 2 <= numExchange <= 100

题目大意

超市正在促销，你可以用 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 <= 100
• 2 <= numExchange <= 100

解题思路

1. 初始化：

   • 用变量 total 记录总喝水数量，初始化为 numBottles。

2. 模拟换瓶过程：

   • 每当拥有的空瓶数 numBottles 大于或等于兑换所需的空瓶数 numExchange 时，可以用 numExchange 个空瓶换取 1 个新的水瓶。
   • 计算出可以换取的新水瓶数量为 exchange = Math.floor(numBottles / numExchange)。
   • 更新总喝水数量 total += exchange。
   • 换得的水瓶后再喝掉，空瓶数量会增加，更新剩余的空瓶数量 numBottles = exchange + (numBottles % numExchange)。
   • 模拟这个过程，直到不能再进行任何兑换。

3. 结束条件：

   • 当前空瓶数量 numBottles 小于 numExchange 时，不能再进行兑换，结束循环。

4. 返回结果：

   • 返回总喝水数量 total。

复杂度分析

• 时间复杂度：O(log(numBottles))，在每次兑换中，水瓶数量 numBottles 减少为 numBottles % numExchange + Math.floor(numBottles / numExchange)，循环执行次数为 O(log_numExchange(numBottles))。
• 空间复杂度：O(1)，没有使用额外的数据结构，仅使用了常数变量。

代码

/**
 * @param {number} numBottles
 * @param {number} numExchange
 * @return {number}
 */
var numWaterBottles = function (numBottles, numExchange) {
	let total = numBottles; // 初始化总喝水瓶数为初始水瓶数
	while (numBottles >= numExchange) {
		const exchange = Math.floor(numBottles / numExchange); // 计算可兑换的新水瓶数量
		total += exchange; // 更新总喝水瓶数
		numBottles = exchange + (numBottles % numExchange); // 更新剩余的空瓶数量
	}
	return total; // 返回结果
};

相关题目

题号	标题	题解	标签	难度	力扣
3100	换水问题 II		数学 模拟	🟠	🀄️ 🔗