1518. Water Bottles

這道題目的主要內容如下:

給你兩個整數 numBottles 和 numExchange。最初你有 numBottles 個裝滿水的瓶子。你可以用 numExchange 個空瓶子換一個裝滿水的瓶子。

問題是:你最多能喝到多少瓶水?

解題思路:

1. 首先,你可以喝掉所有最初的水瓶(numBottles)。
2. 然後,你可以用這些空瓶子去換新的裝滿水的瓶子。
3. 重複步驟2,直到剩下的空瓶子數量少於 numExchange。

解題步驟:

• res 變數用來記錄總共喝掉的水瓶數量。
• while 迴圈會持續執行,直到剩下的瓶子數量小於可以換一個新瓶子所需的數量。
• 在每次迴圈中:
  • m = numBottles % numExchange 計算無法換新瓶子的剩餘瓶子數。
  • res += numBottles - m 將這次能喝的瓶子數(當前所有瓶子減去無法換的瓶子)加到結果中。
  • numBottles = m + numBottles / numExchange 更新剩餘的瓶子數,包括無法換的瓶子(m)和換來的新瓶子(numBottles / numExchange)。
• 迴圈結束後,return res + numBottles 返回總結果,包括迴圈中喝掉的瓶子(res)和剩下無法再換的瓶子(numBottles)。

這個問題考察了簡單的數學運算和迴圈控制。主要難點在於理解題意和正確處理瓶子交換的過程。

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange)
    {
        // 記錄總共喝掉的水瓶數量
        int res = 0;

        // while 迴圈會持續執行,直到剩下的瓶子數量小於可以換一個新瓶子所需的數量
        while (numBottles >= numExchange)
        {
            // 計算無法換新瓶子的剩餘瓶子數
            int m = numBottles % numExchange;

            // 將這次能喝的瓶子數(當前所有瓶子減去無法換的瓶子)加到結果中。
            res += numBottles - m;

            // 更新剩餘的瓶子數,包括無法換的瓶子(m)和換來的新瓶子(numBottles / numExchange)
            numBottles = m + numBottles / numExchange;
        }
        return res + numBottles;
    }
};

• T: $O(\log n)$
• S: $O(1)$