主題

LeetCode - 1927. Sum Game 解題心得

Not In My Back Yard | 2021-11-15 00:00:04 | 巴幣 0 | 人氣 42

題目連結:


題目意譯:
Alice 和 Bob 輪流玩著一個遊戲,由 Alice 擔任先手。

你被給定一個偶數長度的字串 num,其由數字以及字元 '?' 所組成。在每個回合中,只要 num 中還存在至少一個 '?',該玩家將做出以下動作:
選擇一個索引值 i 其中 num[i] == '?'。
將 num[i] 替換成 '0' 到 '9' 之間的任意數字。

遊戲結束於 num 中不存在任何 '?' 的時候。

對於 Bob 來說要贏的話,前半部的每個位數之和必須等於後半部每位數之和;對於 Alice 來說要贏的話,則兩邊總和不能相同。

例如,如果遊戲結束於 num = "243801",則 Bob 贏下此場遊戲因為 2 + 4 + 3 = 8 + 0 + 1。如果遊戲結束於 num = "243803",則 Alice 贏得該場遊戲因為 2 + 4 + 3 != 8 + 0 + 3。

假設 Alice 和 Bob 以最佳策略遊玩,回傳真(True)如果 Alice 將會贏。反之如果 Bob 會贏,回傳假(False)。

限制:
2 ≦ num.length ≦ 10 ^ 5
num.length 為偶數。
num 只由數字和 '?' 組成。



範例測資:
範例 1:
輸入: num = "5023"
輸出: false
解釋: 原先就沒有任何動作可以執行。
前半的和等於後半的和:5 + 0 = 2 + 3。

範例 2:
輸入: num = "25??"
輸出: true
解釋: Alice 可以將其中一個 '?' 替換成 '9',因此 Bob 就不可能使得總和相等。

範例 3:
輸入: num = "?3295???"
輸出: false
解釋: 可以證明 Bob 必贏。其中一種可能的結果為:
- Alice 將第一個 '?' 替換成 '9'。num = "93295???"。
- Bob 將右半其中一個 '?' 替換成 '9'。num = "932959??"。
- Alice 將右半其中一個 '?' 替換成 '2'。num = "9329592?"。
- Bob 將最後一個 '?' 替換成 '7'。num = "93295927"。
Bob 贏因為 9 + 3 + 2 + 9 = 5 + 9 + 2 + 7。


解題思維:
假設左半之和為 D1、右半之和為 D2、左半的 '?' 數為 B1 、右半的 '?' 數為 B2。

首先我們可以看到當 B1 等於 B2 時,結果將取決於 D1 是否等於 D2。如果等於則回傳假;反之回傳真。原因如下:
如果兩者相同,則不管 Alice 在哪一半替換出什麼數字,Bob 只要再另一半也替換同樣的數字即可保證兩半之和相等;
反之如果不同的話,Alice 只要選總和較大的那一半一直將 '?' 替換成數字 '9' 即可保持兩半不相等。



因此可以推得當兩邊都有 '?' 且兩邊數量不相同時,可以互相抵銷直到其中一半沒有 '?' 為止(因為「牽制」並抵銷對手的行動為最佳策略之一,簡單來講就是不虧)。

不失一般性地,我們假設右半沒有問號了(如果是左半沒有問號,只要整個數字左右翻轉即可,左半變右半、右半變左半),而左半有 X 個問號。再定義 D = D1 - D2。可以看到 Alice 將會替換 X 個 '?' 中的 ceil(X ÷ 2) 個,而 Bob 則是 floor(X ÷ 2) 個(因為當 X 為奇數時會多一個 '?',而 Alice 是先手,所以 Alice 將會比 Bob 多一個 '?')。

則當 D + 9 × ceil(X ÷ 2) > 0 或是 D + 9 × floor(X ÷ 2) < 0 時,則代表 Alice 可以保證著左右兩半各自的和不一樣,因此回傳真;兩個都不成立則回傳假。原因如下:
前者是因為如果光 Alice 就可以將左半的和調整到超過右半的話,則代表接下來 Bob 必定會束手無策,因此 Bob 必定會輸;
後者則是因為如果 Bob 每次都替換成最大值卻依舊無法使得左半的和調整為小於右半(這邊不含 Alice 的替換),則 Alice 要嘛也無法使左半小於右半、要嘛就是藉由加上 Bob 的替換(不管他換成什麼數字)來使得左半超過右半,而這兩者都會造成 Bob 之敗北。

那剩下的情況呢?
如果是 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 為奇數則其中一者必會成立;反之,Bob 將可以依據 Alice 所替換的數字來進行「彌補」的動作來使得最終兩半各自之和必相同。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作