leetcode 1518. 换酒问题

leetcode 1518. 换酒问题

Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle.

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

Return the maximum 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.

Example 3:

Input: numBottles = 5, numExchange = 5
Output: 6

Example 4:

Input: numBottles = 2, numExchange = 3
Output: 2

Constraints:
·1 <= numBottles <= 100
·2 <= numExchange <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/water-bottles

一

最大限度地，贪心地，去兑换酒，手中有多少瓶酒，先喝完再说，喝完后再最大限度地拿空瓶去换酒，再把换回来的酒全喝光（也就是sum += change），最后更新下numBottles，这时候的numBottles，也就是这时候手中的空瓶个数是刚刚喝光的change个数的酒，外加一开始凑不够数换酒导致剩下的空瓶，也就是余数。
以example2为例：
先把手中的15瓶酒喝了，这时就有15个空瓶，可以兑换15 / 4 = 3瓶酒，再把这三瓶给喝了，这时一共喝了15+3=18瓶，手中的空瓶数有15 % 4 + 3 = 6个空瓶，因为大于兑换数4，所以进入循环，可以兑换6 / 4 = 1瓶酒，剩余6 % 4 + 1 = 3个空瓶，小于4，退出循环。总共喝了sum = 15 + 3 + 1 = 19瓶

//贪心策略
class Solution {
    
public:
    int numWaterBottles(int numBottles, int numExchange) {
    
        int sum = numBottles; //喝完手中的饮料再说
        while(numBottles >= numExchange){
    
            int change = numBottles / numExchange;
            sum += change;
            numBottles = change + numBottles % numExchange;
        }
        return sum;
    }
};

二

拿numBottles = 15, numExchange = 4来解释：
刚开始可以兑换 15 / 4 = 3 个瓶酒，这时候就得喝掉3 * 4 = 12瓶酒才能有空瓶去兑换，那兑换完后剩下 15 - 3 * 4 + 3 = 6 瓶酒，作为参数代入函数内进行递归即可。

//用递归
class Solution {
    
public:
    int numWaterBottles(int numBottles, int numExchange) {
    
        if(numBottles < numExchange){
    
            return numBottles;
        }
        int change = numBottles / numExchange;
        int sum = change * numExchange;
        sum += numWaterBottles(numBottles % numExchange + change, numExchange);
        return sum;
    }
};

三

①一开始我们先把手中的numBottles瓶酒给喝光，剩下numBottles个空瓶。

②因为是拿numExchange个空酒瓶换1瓶新酒，所以等价于多喝一瓶酒就得损失的空瓶的数量为 numExchange - 1

（可以这么理解：拿numExchange个空瓶子换回一瓶酒，把这瓶酒喝光。那么这个时候，加上这个刚喝完的空瓶，目前手上的空瓶数比最开始少了numExchange - 1，但我却嫖到了酒喝。 ）

直到剩余空酒瓶无法换取新酒，那最多可以多喝几瓶呢，就是要求的n，则有：

numBottles - n(numExchange - 1) < numExchange

进行移项整理得：

同时我们还得特别注意这里的前提条件是numBottles > numExchange。

代码如下：

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