LeetCode 解題筆記：1927. Sum Game

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


LeetCode 題目連結：1927. Sum Game

解題想法

中等難度題。題目給一個字串 $num$，其中只包含數字 0 ~ 9 及 ?，Alice 和 Bob 兩個人輪流行動，由 Alice 先行動，每次行動時可以將一個問𢛶山改成 0 ~ 9 之中的一個數字。如果最後 $num$ 的左半邊加總等於右半邊的加總則 Bob 獲勝，回傳 False；反之則 Alice 獲勝，回傳 True。這題困難的地方在於分析勝敗條件，程式碼反而很簡單。

如果 Bob 要獲勝，第一個條件是左、右兩側的問號數量必須相同，如果數量不同，Alice 會多行動一次，一次可以讓兩側的加總不相等。第二個條件是兩側的問號數量差乘以 9 必須等於兩側總和差乘以 2。先考慮兩側都有問號的狀況，如果 Alice 將左側一個問號改成數字 $x$，Bob 可以將右側的一個問號也改成數字 $x$，兩者的效果就會抵消。再考慮同側問號的狀況，因為 Alice 會盡量讓兩側加總差異越大越好，假設改成 $x$，Bob 為了讓兩側加總相等，會將同側另一個問號改成 $9 - x$。假設右側問號比左側問號多 $\Delta q$ 個，則多出來的問號產生的數字加總必須等於左側數字加總減去右側數字加總 $$ \frac{\Delta q}{2} \times 9 = lsum - rsum \Rightarrow \Delta q \times 9 = (lsum - rsum) \times 2 $$

Python 程式碼

Runtime: 59 ms, beats 50.00%. Memory: 19.68 MB, beats 98.82%.

class Solution:
    def sumGame(self, num: str) -> bool:
        # 1. 計算左、右兩側數字加總、問號數量
        n = len(num)  # 長度
        lsum, rsum = 0, 0  # 左側數字加總，右側數字加總
        lque, rque = 0, 0  # 左側問號數量，右側問號數量
        for i in range(n//2):
            if num[i] == '?':
                lque += 1
            else:
                lsum += int(num[i])
        for i in range(n//2, n):
            if num[i] == '?':
                rque += 1
            else:
                rsum += int(num[i])
        # 2. 問號數量如果是奇數，Alice 多行動一次，Alice 必勝
        if (lque + rque) % 2 == 1: return True
        # 3. dq = rque - lque，同側每一對問號可以產生數字總和 9
        # 必須抵消 lsum - rsum，Bob 才會獲勝
        return (rque - lque) * 9 != (lsum - rsum) * 2

C++ 程式碼

Runtime: 3 ms, beats 66.67%. Memory: 14.14 MB, beats 10.26%.

class Solution {
public:
    bool sumGame(string num) {
        /* 1. 計算左、右兩側數字加總、問號數量 */
        int n = (int)num.size();  // 長度
        int lsum = 0, rsum = 0;  // 左側數字加總，右側數字加總
        int lque = 0, rque = 0;  // 左側問號數量，右側問號數量
        for(int i = 0; i < n/2; i++) {
            if (num[i] == '?') lque++;
            else lsum += num[i] - '0';
        }
        for(int i = n/2; i < n; i++) {
            if (num[i] == '?') rque++;
            else rsum += num[i] - '0';
        }
        
        /* 2. 問號數量如果是奇數，Alice 多行動一次，Alice 必勝 */
        if ((lque + rque) % 2 == 1) return true;
        
        /* 3. 同側每一對問號可以產生數字總和 9
              必須抵消 lsum - rsum，Bob 才會獲勝 */
        return (rque - lque) * 9 != (lsum - rsum) * 2;
    }
};

C 語言程式碼

Runtime: 0 ms, beats 100.00%. Memory: 9.95 MB, beats 100.00%.

bool sumGame(char* num) {
    /* 1. 計算左、右兩側數字加總、問號數量 */
    int n = strlen(num);  // 長度
    int lsum = 0, rsum = 0;  // 左側數字加總，右側數字加總
    int lque = 0, rque = 0;  // 左側問號數量，右側問號數量
    for(int i = 0; i < n/2; i++) {
        if (num[i] == '?') lque++;
        else lsum += num[i] - '0';
    }
    for(int i = n/2; i < n; i++) {
        if (num[i] == '?') rque++;
        else rsum += num[i] - '0';
    }
    
    /* 2. 問號數量如果是奇數，Alice 多行動一次，Alice 必勝 */
    if ((lque + rque) % 2 == 1) return true;
    
    /* 3. 同側每一對問號可以產生數字總和 9
          必須抵消 lsum - rsum，Bob 才會獲勝 */
    return (rque - lque) * 9 != (lsum - rsum) * 2;
}