力扣1518. 换水问题

题目链接

力扣1518. 换水问题

简单方法(模拟)

思路

对换水进行模拟，每次喝完 $numExchange$ 瓶水后就去换一瓶水，直到不能再兑换为止，也就是剩余水的数量小于 $numExchange$时，不再模拟。故可以得出以下的代码：

代码

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int emptyBottles = 0;							// 用来兑换的空水瓶的总数
        while (numBottles >= numExchange) {
            numBottles = numBottles - numExchange + 1;	// 用numExchange个空水瓶兑换一瓶水
            emptyBottles += numExchange;				// 用来兑换的空水瓶数 += 本轮循环兑换的空水瓶数
        }
        return emptyBottles + numBottles;				// 此时的numBottles为剩余的无法兑换的水
    }
}

简单方法的优化

思路

先对简单方法进行分析，费时的操作在哪里？

可以看到，换水的次数太多了，所以要减少换水的次数。

怎样减少换水的次数？

换水时直接将所有水先喝完，最大化本次换水的瓶数。设用来兑换一瓶水的瓶数为 $n$、本次的总空瓶数为 $m$、本次兑换的水瓶数为 $a$、本次用来兑换的空瓶数为 $e$，则有这样的关系式 $a=m/n,e=a\ast n$，并且 $a$ 要向下取整。

代码

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int emptyBottles = 0;							// 用来兑换的空水瓶的总数
        while (numBottles >= numExchange) {
            int addition = numBottles / numExchange;	// 用numExchange个空水瓶兑换最多瓶水的瓶数
            numBottles %= numExchange;					// 最大化本次换水的数量
            numBottles += addition;						// 让总水瓶数加上本次换的水瓶数
            emptyBottles += addition * numExchange;		// 用来兑换的空水瓶的总数 += 本次用来兑换的空瓶数
        }
        return emptyBottles + numBottles;				// 此时的numBottles为剩余的无法兑换的水
    }
}