LeetCode 解題筆記：2029. Stone Game IX

作者：王一哲
日期：2026年8月16日


LeetCode 題目連結：2029. Stone Game IX

解題想法

中等難度題。題目給一個整數陣列 $stones$ 代表一列石頭各自的分數，Alice 和 Bob 輪流拿石頭，如果目前行動的玩家拿走石頭時所有被移除的石頭總分為 3 的倍數，目前行動的玩家輸掉比賽；如果所有的石頭都拿光了，Alice 輸掉比賽。如果 Alice 能夠獲勝回傳 True，反之回傳 False。這題真正困難的地方在於找出 Alice 獲勝的條件，程式碼反而很簡短。由於題目只關心被移除的石頭總分是否為 3 的倍數，所以我們不需要計算總分，只要計算移除的石頭分數對 3 的餘數。先計算石頭分數對 3 取餘數為 0、1、2 的數量分別為 $a, b, c$，Alice 獲勝的狀況有以下 2 種：

1. $a$ 為偶數且 $b > 0, c > 0$，Alice 第一回合可以拿走一顆餘數 1 或 2 的石頭，Bob 就算用餘數 0 的石頭拖時間，最後還是會拿到將總分湊成 3 的倍數的石頭。
2. $a$ 為奇數且 $abs(b - c) > 2$，Alice 第一回合可以拿走餘數 1 及 2 的石頭之中數量較多者，Bob 就算用餘數 0 的石頭拖時間，Alice 還能夠拿一顆與第一回合相同的石頭。

Python 程式碼

Runtime: 55 ms, beats 45.80%. Memory: 30.49 MB, beats 88.55%.

class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        # 石頭的分數對 3 取餘數，餘數 0、1、2 的數量
        a, b, c = 0, 0, 0
        for num in stones:
            rem = num % 3
            if rem == 0: a += 1
            elif rem == 1: b += 1
            else: c += 1
        # 狀況1，a 是偶數，如果 b, c 都大於 0，第1回合可以任意選 b 或 c，Alice 勝
        # 狀況2，a 是奇數，如果 b, c 相差大於 2，Alice 勝
        if a % 2 == 0:
            return b > 0 and c > 0  
        else:
            return abs(b - c) > 2

C++ 程式碼

Runtime: 1 ms, beats 82.74%. Memory: 131.32 MB, beats 33.50%.

class Solution {
public:
    bool stoneGameIX(vector<int>& stones) {
        // 石頭的分數對 3 取餘數，餘數 0、1、2 的數量
        int a = 0, b = 0, c = 0;
        for(int num : stones) {
            int rem = num % 3;
            if (rem == 0) a++;
            else if (rem == 1) b++;
            else c++;
        }
        // 狀況1，a 是偶數，如果 b, c 都大於 0，第1回合可以任意選 b 或 c，Alice 勝
        // 狀況2，a 是奇數，如果 b, c 相差大於 2，Alice 勝
        if (a % 2 == 0) {
            return b > 0 && c > 0;  
        } else {
            return abs(b - c) > 2;
        }
    }
};

C 語言程式碼

Runtime: 9 ms, beats 20.00%. Memory: 18.16 MB, beats 80.00%.

bool stoneGameIX(int* stones, int stonesSize) {
    // 石頭的分數對 3 取餘數，餘數 0、1、2 的數量
    int a = 0, b = 0, c = 0;
    for(int i = 0; i < stonesSize; i++) {
        int rem = stones[i] % 3;
        if (rem == 0) a++;
        else if (rem == 1) b++;
        else c++;
    }
    // 狀況1，a 是偶數，如果 b, c 都大於 0，第1回合可以任意選 b 或 c，Alice 勝
    // 狀況2，a 是奇數，如果 b, c 相差大於 2，Alice 勝
    if (a % 2 == 0) {
        return b > 0 && c > 0;  
    } else {
        return abs(b - c) > 2;
    }
}