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 <= 1001<=numBottles<=100
• 2 <= numExchange <= 1002<=numExchange<=100

模拟

根据题意进行模拟即可，使用 ansans 统计答案，nn 为空瓶子个数。

起始有 nn 瓶酒，因此 ans = nans=n，此时空瓶子个数为 nn，当且仅当空瓶子个数 nn 大于等于兑换个数 mm 时，可以继续喝到酒（能够更新 ansans），兑换后得到酒的个数为 a = \left \lfloor \frac{n}{m} \right \rfloora=⌊mn⌋，剩余空瓶子个数等于「兑换酒的个数 aa」和「兑换后剩余的酒瓶子个数 b = n \pmod mb=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 = 2m=2 时，兑换酒的数量最多，此时复杂度为 O(\log{n})O(logn)
• 空间复杂度：O(1)O(1)

数学

起始有 nn 瓶酒，使用 mm 个空酒瓶能够换得一瓶新酒（饮用数量加一，且新瓶子数量加一）。即对于每次交换而言，会损失掉 m - 1m−1 个瓶子。

利用每个回合损失的瓶子个数 m - 1m−1 为定值，可直接算出最大交换次数（额外饮用次数）cnt = \left \lfloor \frac{n}{m - 1}\right \rfloorcnt=⌊m−1n⌋，加上起始酒的个数即是答案。

注意边界条件：当 nn 为 m - 1m−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 原题链接和其他优选题解。