Easy

题目描述

有 numBottles 瓶装满水的水瓶。你可以用 numExchange 个空水瓶从市场上换取一瓶装满水的水瓶。

喝掉一瓶装满水的水瓶会使其变成空瓶。

给定两个整数 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. 先喝掉所有初始的水瓶，得到相应数量的空瓶
  2. 用空瓶按比例换新瓶，喝掉新瓶又得到空瓶
  3. 重复步骤2，直到空瓶数量不足以换取新瓶

方法二：数学公式 我们可以观察到一个规律：每 numExchange 个空瓶可以换 1 瓶水，喝掉后又产生 1 个空瓶。实际上相当于用 numExchange - 1 个空瓶换 1 瓶水的机会。

因此总的喝水数 = 初始水瓶数 + 能换到的水瓶数 = numBottles + (numBottles - 1) / (numExchange - 1)

这里推荐使用方法一，因为代码更容易理解且数据规模较小。

代码实现

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int total = numBottles;
        int empty = numBottles;
        
        while (empty >= numExchange) {
            int newBottles = empty / numExchange;
            total += newBottles;
            empty = empty % numExchange + newBottles;
        }
        
        return total;
    }
};

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        total = numBottles
        empty = numBottles
        
        while empty >= numExchange:
            new_bottles = empty // numExchange
            total += new_bottles
            empty = empty % numExchange + new_bottles
            
        return total

public class Solution {
    public int NumWaterBottles(int numBottles, int numExchange) {
        int total = numBottles;
        int empty = numBottles;
        
        while (empty >= numExchange) {
            int newBottles = empty / numExchange;
            total += newBottles;
            empty = empty % numExchange + newBottles;
        }
        
        return total;
    }
}

var numWaterBottles = function(numBottles, numExchange) {
    let total = numBottles;
    let empty = numBottles;
    
    while (empty >= numExchange) {
        let newBottles = Math.floor(empty / numExchange);
        total += newBottles;
        empty = empty % numExchange + newBottles;
    }
    
    return total;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(log n)，其中 n 是 numBottles。每次兑换后空瓶数量大约减少为原来的 1/numExchange
空间复杂度O(1)，只使用了常数级别的额外空间

相关题目