Leetcode 1518. wine change

leetcode 1518. Wine exchange

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

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/water-bottles

One

To the maximum extent , Greedily , Go to exchange wine , How many bottles of wine are there , Finish it first , After drinking, take the empty bottle as much as possible to exchange wine , Then drink all the wine you change （ That is to say sum += change）, Last update numBottles, By this time numBottles, At this time, the number of empty bottles in your hand has just been drunk change A few drinks , In addition, at the beginning, it was not enough to change the wine, resulting in the remaining empty bottles , That's the remainder .
With example2 For example ：
First put the in your hand 15 Drink a bottle of wine , Then there is 15 Empty bottles , Convertible 15 / 4 = 3 A bottle of wine , Drink these three bottles again , At this time, I drank 15+3=18 bottle , The number of empty bottles in your hand is 15 % 4 + 3 = 6 Empty bottles , Because it is larger than the exchange amount 4, So into the cycle , Convertible 6 / 4 = 1 A bottle of wine , The remaining 6 % 4 + 1 = 3 Empty bottles , Less than 4, Exit loop . A total of sum = 15 + 3 + 1 = 19 bottle

// Greedy strategy 
class Solution {
    
public:
    int numWaterBottles(int numBottles, int numExchange) {
    
        int sum = numBottles; // After drinking the drink in your hand 
        while(numBottles >= numExchange){
    
            int change = numBottles / numExchange;
            sum += change;
            numBottles = change + numBottles % numExchange;
        }
        return sum;
    }
};

Two

take numBottles = 15, numExchange = 4 To explain ：
At first, you can exchange 15 / 4 = 3 A bottle of wine , At this time, you have to drink 3 * 4 = 12 Only when you have a bottle of wine can you have an empty bottle to exchange , After the exchange, there is 15 - 3 * 4 + 3 = 6 A bottle of wine , As a parameter, it can be substituted into the function for recursion .

// Using recursion 
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;
    }
};

3、 ... and

① At the beginning, let's put the numBottles Drink up the bottle of wine , be left over numBottles Empty bottles .

② Because it's taking numExchange Change an empty wine bottle 1 Bottle of new wine , Therefore, the number of empty bottles equivalent to drinking an extra bottle of wine is numExchange - 1

（ It's understandable ： take numExchange Exchange an empty bottle for a bottle of wine , Drink up this bottle of wine . So at this point , Add this empty bottle just finished , At present, the number of empty bottles on hand is less than at the beginning numExchange - 1, But I went whoring to drink . ）

Until the remaining empty bottles cannot be exchanged for new wine , How many bottles can you drink at most , That's what's required n, Then there are ：

numBottles - n(numExchange - 1) < numExchange

Move items to get ：

At the same time, we have to pay special attention to the premise here is numBottles > numExchange.

The code is as follows ：

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