超市正在促销，你可以用 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
前言
记一开始有 b 瓶酒，e 个空瓶换一瓶酒。
方法一：模拟
思路与算法
首先我们一定可以喝到 b 瓶酒，剩下 b 个空瓶。接下来我们可以拿瓶子换酒，每次拿出 e 个瓶子换一瓶酒，然后再喝完这瓶酒，得到一个空瓶。以此类推，我们可以统计得到答案。
代码
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int numWaterBottles(int numBottles, int numExchange) {
int bottle = numBottles, ans = numBottles;
while (bottle >= numExchange) {
bottle -= numExchange;
++ans;
++bottle;
}
return ans;
}
};
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int numWaterBottles(int numBottles, int numExchange) {
int bottle = numBottles, ans = numBottles;
while (bottle >= numExchange) {
bottle -= numExchange;
++ans;
++bottle;
}
return ans;
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
| public class Solution {
public int NumWaterBottles(int numBottles, int numExchange) {
int bottle = numBottles, ans = numBottles;
while (bottle >= numExchange) {
bottle -= numExchange;
++ans;
++bottle;
}
return ans;
}
}
|
[sol1-Python3]1
2
3
4
5
6
7
8
| class Solution:
def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
bottle, ans = numBottles, numBottles
while bottle >= numExchange:
bottle -= numExchange
ans += 1
bottle += 1
return ans
|
[sol1-C]1
2
3
4
5
6
7
8
9
| int numWaterBottles(int numBottles, int numExchange){
int bottle = numBottles, ans = numBottles;
while (bottle >= numExchange) {
bottle -= numExchange;
++ans;
++bottle;
}
return ans;
}
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
| func numWaterBottles(numBottles int, numExchange int) int {
bottle, ans := numBottles, numBottles
for bottle >= numExchange {
bottle = bottle - numExchange
ans++
bottle++
}
return ans
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
| var numWaterBottles = function(numBottles, numExchange) {
let bottle = numBottles, ans = numBottles;
while (bottle >= numExchange) {
bottle -= numExchange;
++ans;
++bottle;
}
return ans;
};
|
复杂度分析
方法二：数学
思路与算法
第一步，首先我们一定可以喝到 b 瓶酒，剩下 b 个空瓶。
第二步，接下来我们来考虑空瓶换酒，换完再喝，喝完再换的过程——每次换到一瓶酒就意味着多一个空瓶，所以每次损失的瓶子的数量为 e - 1，我们要知道这个过程能得到多少瓶酒，即希望知道第一个打破下面这个条件的 n 是多少：
b - n(e - 1) \geq e
即我们要找到最小的 n 使得：
b - n(e - 1) < e
我们得到 n_{\min} = \lfloor \dfrac{b - e}{e - 1} + 1\rfloor。
当然我们要特别注意这里的前提条件是 b \geq e，试想如果 b < e，没有足够的瓶子再换酒了，就不能进行第二步了。
代码
[sol2-C++]1
2
3
4
5
6
| class Solution {
public:
int numWaterBottles(int numBottles, int numExchange) {
return numBottles >= numExchange ? (numBottles - numExchange) / (numExchange - 1) + 1 + numBottles : numBottles;
}
};
|
[sol2-Java]1
2
3
4
5
| class Solution {
public int numWaterBottles(int numBottles, int numExchange) {
return numBottles >= numExchange ? (numBottles - numExchange) / (numExchange - 1) + 1 + numBottles : numBottles;
}
}
|
[sol2-C#]1
2
3
4
5
| public class Solution {
public int NumWaterBottles(int numBottles, int numExchange) {
return numBottles >= numExchange ? (numBottles - numExchange) / (numExchange - 1) + 1 + numBottles : numBottles;
}
}
|
[sol2-Python3]1
2
3
| class Solution:
def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
return (numBottles - numExchange) // (numExchange - 1) + 1 + numBottles if numBottles >= numExchange else numBottles
|
[sol2-C]1
2
3
| int numWaterBottles(int numBottles, int numExchange){
return numBottles >= numExchange ? (numBottles - numExchange) / (numExchange - 1) + 1 + numBottles : numBottles;
}
|
[sol2-Golang]1
2
3
4
5
6
| func numWaterBottles(numBottles int, numExchange int) int {
if numBottles < numExchange {
return numBottles
}
return (numBottles - numExchange) / (numExchange - 1) + 1 + numBottles
}
|
[sol2-JavaScript]1
2
3
| var numWaterBottles = function(numBottles, numExchange) {
return numBottles >= numExchange ? Math.floor((numBottles - numExchange) / (numExchange - 1)) + 1 + numBottles : numBottles;
};
|
复杂度分析
