題目連結(jié)：
題目意譯：
Alice 和 Bob 輪流玩著一個遊戲，由 Alice 擔(dān)任先手。
你被給定一個偶數(shù)長度的字串 num，其由數(shù)字以及字元 '?' 所組成。在每個回合中，只要 num 中還存在至少一個 '?'，該玩家將做出以下動作：
選擇一個索引值 i 其中 num[i] == '?'。
將 num[i] 替換成 '0' 到 '9' 之間的任意數(shù)字。
遊戲結(jié)束於 num 中不存在任何 '?' 的時候。
對於 Bob 來說要贏的話，前半部的每個位數(shù)之和必須等於後半部每位數(shù)之和；對於 Alice 來說要贏的話，則兩邊總和不能相同。
例如，如果遊戲結(jié)束於 num = "243801"，則 Bob 贏下此場遊戲因?yàn)?2 + 4 + 3 = 8 + 0 + 1。如果遊戲結(jié)束於 num = "243803"，則 Alice 贏得該場遊戲因?yàn)?2 + 4 + 3 != 8 + 0 + 3。
假設(shè) Alice 和 Bob 以最佳策略遊玩，回傳真（True）如果 Alice 將會贏。反之如果 Bob 會贏，回傳假（False）。
限制：
2 ≦ num.length ≦ 10 ^ 5
num.length 為偶數(shù)。
num 只由數(shù)字和 '?' 組成。
範(fàn)例測資：
範(fàn)例 1：
輸入： num = "5023"
輸出： false
解釋： 原先就沒有任何動作可以執(zhí)行。
前半的和等於後半的和：5 + 0 = 2 + 3。
範(fàn)例 2：
輸入： num = "25??"
輸出： true
解釋： Alice 可以將其中一個 '?' 替換成 '9'，因此 Bob 就不可能使得總和相等。
範(fàn)例 3：
輸入： num = "?3295???"
輸出： false
解釋： 可以證明 Bob 必贏。其中一種可能的結(jié)果為：
- Alice 將第一個 '?' 替換成 '9'。num = "93295???"。
- Bob 將右半其中一個 '?' 替換成 '9'。num = "932959??"。
- Alice 將右半其中一個 '?' 替換成 '2'。num = "9329592?"。
- Bob 將最後一個 '?' 替換成 '7'。num = "93295927"。
Bob 贏因?yàn)?9 + 3 + 2 + 9 = 5 + 9 + 2 + 7。
解題思維：
假設(shè)左半之和為 D1、右半之和為 D2、左半的 '?' 數(shù)為 B1 、右半的 '?' 數(shù)為 B2。
首先我們可以看到當(dāng) B1 等於 B2 時，結(jié)果將取決於 D1 是否等於 D2。如果等於則回傳假；反之回傳真。原因如下：
如果兩者相同，則不管 Alice 在哪一半替換出什麼數(shù)字，Bob 只要再另一半也替換同樣的數(shù)字即可保證兩半之和相等；
反之如果不同的話，Alice 只要選總和較大的那一半一直將 '?' 替換成數(shù)字 '9' 即可保持兩半不相等。
因此可以推得當(dāng)兩邊都有 '?' 且兩邊數(shù)量不相同時，可以互相抵銷直到其中一半沒有 '?' 為止（因?yàn)椤笭恐啤箒K抵銷對手的行動為最佳策略之一，簡單來講就是不虧）。
不失一般性地，我們假設(shè)右半沒有問號了（如果是左半沒有問號，只要整個數(shù)字左右翻轉(zhuǎn)即可，左半變右半、右半變左半），而左半有 X 個問號。再定義 D = D1 - D2。可以看到 Alice 將會替換 X 個 '?' 中的 ceil(X ÷ 2) 個，而 Bob 則是 floor(X ÷ 2) 個（因?yàn)楫?dāng) X 為奇數(shù)時會多一個 '?'，而 Alice 是先手，所以 Alice 將會比 Bob 多一個 '?'）。
則當(dāng) D + 9 × ceil(X ÷ 2) > 0 或是 D + 9 × floor(X ÷ 2) < 0 時，則代表 Alice 可以保證著左右兩半各自的和不一樣，因此回傳真；兩個都不成立則回傳假。原因如下：
前者是因?yàn)槿绻?Alice 就可以將左半的和調(diào)整到超過右半的話，則代表接下來 Bob 必定會束手無策，因此 Bob 必定會輸；
後者則是因?yàn)槿绻?Bob 每次都替換成最大值卻依舊無法使得左半的和調(diào)整為小於右半（這邊不含 Alice 的替換），則 Alice 要嘛也無法使左半小於右半、要嘛就是藉由加上 Bob 的替換（不管他換成什麼數(shù)字）來使得左半超過右半，而這兩者都會造成 Bob 之?dāng)”薄?/div>
那剩下的情況呢？
如果是 D + 9 × ceil(X ÷ 2) < 0，可以看到此時後者會成立；
如果是 D + 9 × floor(X ÷ 2) > 0，可以看到此時前者會成立；
那如果是 D + 9 × ceil(X ÷ 2) = 0 或是 D + 9 × floor(X ÷ 2) = 0 呢？此時，如果 X 為奇數(shù)則其中一者必會成立；反之，Bob 將可以依據(jù) Alice 所替換的數(shù)字來進(jìn)行「彌補(bǔ)」的動作來使得最終兩半各自之和必相同。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達(dá)人
