力扣 1518. 换酒问题

题目说明

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

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

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

提示：

  • 1 <= numBottles <= 100
  • 2 <= numExchange <= 100

示例

示例 1:

img

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

示例 2:

img

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

示例 3:

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

示例 4:

1
2
输入：numBottles = 2, numExchange = 3
输出：2

笔者理解

此题是一道数学算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题我们直接模拟换算的过程即可，让我们来看看具体如何实现的吧。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    /**
     * 数学
     * 模拟
     */
    public int numWaterBottles(int numBottles, int numExchange) {
        if (numBottles < numExchange) {
            return numBottles;
        }
        return count(numBottles, 0, numExchange);
    }
    
    /**
     * now: 现在拥有的酒数
     * preRemain: 上次剩下的酒瓶子数
     * numExchange: 交换比例
     */
    public int count(int now, int preRemain, int numExchange) {
        int result = now;

        if ((now + preRemain) >= numExchange) {
            // 酒瓶交换的酒数
            int exchangeNum = (now + preRemain) / numExchange;
            // 交换剩下的酒瓶数
            int remain = (now + preRemain) % numExchange;
            result += count(exchangeNum, remain, numExchange);
        }

        return result;
    }
}

时间和空间效率还行，可见此解法还比较适合此题。

image-20211217205854842

总结

本题是今天的每日一题，难度是为简单，感兴趣的朋友都可以去尝试一下，此题还有其他更多的解法，朋友们可以自己逐一尝试。