【每日一题】 1518. 换酒问题

曾经终败给现在 2022-11-19 07:53 68阅读 0赞

# 【每日一题】 1518. 换酒问题 #

> 避免每日太过咸鱼，一天搞定一道LeetCode算法题

## 一、题目描述 ##

小区便利店正在促销，用 numExchange 个空酒瓶可以兑换一瓶新酒。你购入了 numBottles 瓶酒。

如果喝掉了酒瓶中的酒，那么酒瓶就会变成空的。

请你计算 最多 能喝到多少瓶酒。

**提示：**

*  `1 <= grid.length == grid[0].length <= 30`
 *  `grid[i][j]` 是 `'/'`、`'\'`、或 `' '`。

**示例 1：**

输入：numBottles = 9, numExchange = 3
    输出：13
    解释：你可以用 3 个空酒瓶兑换 1 瓶酒。
    所以最多能喝到 9 + 3 + 1 = 13 瓶酒。

**示例 2：**

输入：numBottles = 15, numExchange = 4
    输出：19
    解释：你可以用 4 个空酒瓶兑换 1 瓶酒。
    所以最多能喝到 15 + 3 + 1 = 19 瓶酒。

**示例 3：**

输入：numBottles = 5, numExchange = 5
    输出：6

## 二、题解 ##

### 1. 解法 ###

### **解题思路：** ###

第一步，首先我们一定可以喝到 b 瓶酒，剩下 b 个空瓶。

第二步，接下来我们来考虑空瓶换酒，换完再喝，喝完再换的过程——每次换到一瓶酒就意味着多一个空瓶，所以每次损失的瓶子的数量为 e - 1，我们要知道这个过程能得到多少瓶酒，即希望知道第一个打破下面这个条件的 n 是多少：b*−*n\*(*e*−1)≥\*e

即我们要找到最小的 *n* 使得：*b*−*n*(*e*−1)<*e*.

当然我们要特别注意这里的前提条件是 b ≥e，试想如果 b<e，没有足够的瓶子再换酒了，就不能进行第二步了。

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

复杂度分析

*  时间复杂度：O(1)
 *  空间复杂度：O(1)

题目来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/distance-between-bus-stops

\--------------最后感谢大家的阅读，愿大家技术越来越流弊！--------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]

\--------------也希望大家给我点支持，谢谢各位大佬了！！！--------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]: /images/20221119/2eff8d7ee5cc4ed0949de61e98ef300c.png