1518.换酒问题:「模拟」&「数学」

题目描述

这是 LeetCode 上的 1518. 换酒问题 ，难度为 简单。

Tag : 「模拟」、「数学」

小区便利店正在促销，用 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 瓶酒。
复制代码

示例 3：

输入：numBottles = 5, numExchange = 5

输出：6
复制代码

示例 4：

输入：numBottles = 2, numExchange = 3

输出：2
复制代码

提示：

• 
  $1 <= numBottles <= 100$

  1<= numBottles<=100

• 
  $2 <= numExchange <= 100$

  2<= numExchange<=100

模拟

根据题意进行模拟即可，使用

ans 统计答案，

n 为空瓶子个数。

起始有

n 瓶酒，因此

ans=n，此时空瓶子个数为

n，当且仅当空瓶子个数

n 大于等于兑换个数

m 时，可以继续喝到酒（能够更新

ans），兑换后得到酒的个数为

a=⌊mn​⌋，剩余空瓶子个数等于「兑换酒的个数

a」和「兑换后剩余的酒瓶子个数

b=n(modm)」之和。

代码：

class Solution {
    public int numWaterBottles(int n, int m) {
        int ans = n;
        while (n >= m) {
            int a = n / m, b = n % m;
            ans += a;
            n = a + b;
        }
        return ans;
    }
}
复制代码

• 时间复杂度：循环次数「不超过」能换新酒的数量，能够新酒的数量最多为
  $\left \lfloor \frac{n}{m - 1}\right \rfloor$

  ⌊m−1n​⌋ 瓶。复杂度为

  $O(\left \lfloor \frac{n}{m - 1}\right \rfloor)$

  O(⌊m−1n​⌋)。进一步，当

  $m = 2$

  m=2 时，兑换酒的数量最多，此时复杂度为

  $O(\log{n})$

  O(logn)

• 空间复杂度：
  $O(1)$

  O(1)

数学

起始有

n 瓶酒，使用

m 个空酒瓶能够换得一瓶新酒（饮用数量加一，且新瓶子数量加一）。即对于每次交换而言，会损失掉

m−1 个瓶子。

利用每个回合损失的瓶子个数

m−1 为定值，可直接算出最大交换次数（额外饮用次数）

cnt=⌊m−1n​⌋，加上起始酒的个数即是答案。

注意边界条件：当

n 为

m−1 的倍数时，最后一个回合不满足兑换条件。

代码：

class Solution {
    public int numWaterBottles(int n, int m) {
        int cnt = n / (m  - 1);
        return n % (m - 1) == 0 ? n + cnt - 1 : n + cnt;
    }
}
复制代码

• 时间复杂度：
  $O(1)$

  O(1)

• 空间复杂度：
  $O(1)$

  O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1518 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。