LeetCode.1518.换酒问题

力扣2021.12.17的每日一题

难度：easy

 目前想到两种方法：模拟法和数学法：

Java：

模拟法1：

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int totalNum = numBottles;       //统计最多能喝多少瓶酒
        while(numBottles >= numExchange) {
            int a = numBottles / numExchange;
            int b = numBottles % numExchange;
            totalNum += a;  //喝掉新兑换的酒
            numBottles = a + b;     //空瓶子
        }
        return totalNum;
    }
}

复杂度分析：

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

模拟法2：

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int totalNum = numBottles;
        while (numBottles >= numExchange) {
            numBottles -= numExchange;
            numBottles ++;
            totalNum ++;
        }
        return totalNum;
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1) 

数学法：

         很巧妙的方法，每次相当于减少(numExchange - 1)个瓶子，可以减少多少次就是可以兑换多少个空瓶子：numBottles / (numExchange - 1)，所以是一共可以喝numBottles + numBottles / (numExchange - 1)瓶啤酒，化简得(numBottles * numExchange ) / (numExchange - 1);然后注意下边界条件，带入3,4测试用例，修改一下：(numBottles * numExchange - 1) / (numExchange - 1);

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        return (numBottles * numExchange - 1) / (numExchange - 1);
    }
}

复杂度分析：

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

合理，nice！