每日一题——1518. 换酒问题

1518. 换酒问题

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

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

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

public class Solution {
    public int NumWaterBottles(int numBottles, int numExchange) {
        int ans = numBottles;
        int nullBottles = numBottles;
        while(nullBottles/numExchange != 0)
        {
            ans += nullBottles/numExchange;
            nullBottles = nullBottles/numExchange + nullBottles%numExchange;
        }

        return ans;
    }
}

简单题,主要是来讨论有没有优化的空间

我的做法很一般,就是硬算

循环里面来计算

每次都更新答案和空瓶子的数目

如果除完结果为0就证明除不动了

就该退出去循环了

ans的默认值是购买的酒的数量

否则不进入循环的情况就没计算了


数学思路

以下参考的三叶姐的思路

起始有 n 瓶酒,使用 m 个空酒瓶能够换得一瓶新酒(饮用数量加一,且新瓶子数量加一)

即对于每次交换而言,会损失掉 m – 1 个瓶子。

利用每个回合损失的瓶子个数 m – 1为定值,可直接算出最大交换次数(额外饮用次数)

cnt = n/m-1

加上起始酒瓶的数量就是答案了

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

 

发表评论

您的电子邮箱地址不会被公开。