LeetCode1518:酒瓶兑换问题

概述

本文将详细解析LeetCode上的酒瓶兑换问题，提供两种解题方法，并分析其时间和空间复杂度。

题目描述

(原题链接: LeetCode 1518)

某便利店正在进行一项促销活动，顾客可以用 numExchange 个空酒瓶兑换一瓶新酒。假设你购买了 numBottles 瓶酒。当酒瓶中的酒被饮用后，这些酒瓶就变成了空瓶。请计算你能通过这种兑换方式最多喝到多少瓶酒。

示例 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. 初始化当前拥有的酒瓶数为 numBottles，同时记录总饮酒数量也为 numBottles。
2. 只要当前拥有的空瓶数大于或等于 numExchange，就可以进行一次兑换。
3. 每次兑换后，更新当前拥有的酒瓶数，并增加总饮酒数量。
4. 重复上述步骤，直到无法再进行兑换。

代码实现 (C++):

class Solution { public: int numWaterBottles(int numBottles, int numExchange) { int bottle = numBottles; int res = numBottles; while (bottle >= numExchange) { // 说明还可以兑换 bottle -= numExchange; // 兑换一个新瓶 res++; bottle++; } return res; } };

时间复杂度: O(n)，其中 n 是初始酒瓶的数量。

空间复杂度: O(1)，仅使用常数级额外空间。

方法二 - 数学法

数学法通过公式推导来简化问题。核心思想是利用每次兑换实际上消耗了 (numExchange - 1) 个酒瓶这一特性。因此，可以通过以下公式计算最大可饮用的酒瓶数：

n = (numBottles - numExchange) / (numExchange - 1) + 1 + numBottles

其中，n 表示通过兑换获得的额外酒瓶数。需要注意的是，只有当 numBottles 大于等于 numExchange 时才能进行兑换。

代码实现 (C++):

class Solution { public: int numWaterBottles(int numBottles, int numExchange) { return numBottles >= numExchange ? (numBottles - numExchange) / (numExchange - 1) + 1 + numBottles : numBottles; } };

时间复杂度: O(1)，计算过程为常数时间。

空间复杂度: O(1)，仅使用常数级额外空间。