黑板上寫著一個非負整數(shù)數(shù)組 nums[i] 。Alice 和 Bob 輪流從黑板上擦掉一個數(shù)字，Alice 先手。如果擦除一個數(shù)字后，剩余的所有數(shù)字按位異或運算得出的結(jié)果等于 0 的話，當前玩家游戲失敗。 (另外，如果只剩一個數(shù)字，按位異或運算得到它本身；如果無數(shù)字剩余，按位異或運算結(jié)果為 0。）

換種說法就是，輪到某個玩家時，如果當前黑板上所有數(shù)字按位異或運算結(jié)果等于 0，這個玩家獲勝。

假設(shè)兩個玩家每步都使用最優(yōu)解，當且僅當 Alice 獲勝時返回 true。

示例：

輸入: nums = [1, 1, 2]
輸出: false

解釋:
Alice 有兩個選擇: 擦掉數(shù)字 1 或 2。
如果擦掉 1, 數(shù)組變成 [1, 2]。剩余數(shù)字按位異或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意數(shù)字，因為 Alice 會成為擦掉最后一個數(shù)字的人，她總是會輸。
如果 Alice 擦掉 2，那么數(shù)組變成[1, 1]。剩余數(shù)字按位異或得到 1 XOR 1 = 0。Alice 仍然會輸?shù)粲螒颉?/p>

解題思路

奇偶不變

因為ALice和Bob是輪流取數(shù)字的，所以如果剛開始的元素個數(shù)是偶數(shù)個，那么Alice每次取元素時，元素都是偶數(shù)。

S^nums[i]=Si

設(shè)Si為數(shù)組去掉第i個元素以后的異或的結(jié)果，S為所有元素異或的結(jié)果,即有Si^{nums[i]=S，變形得S}nums[i]=Si

反證法

在數(shù)組長度為偶數(shù)并且S!=0(因為如果S=0，那么就勝負已經(jīng)確定了)的情況，假設(shè)無論取走的元素是哪個，都有Si=0
即S0=0，S1=0…,等價于S0^S1S2…=0,代入S^nums[i]=Si得

(S^nums[0])^(S^nums[1])^....=0

(S^S...)^(nums[0]^nums[1]....)=0

又因為S為所有元素異或的結(jié)果，并且數(shù)組長度為偶數(shù)，所以有偶數(shù)個S，因此

S^S…(奇數(shù)個S)=0，即S=0，與S！=0矛盾,所以可以得出無論取走的元素是哪個，都不存在Si=0，也就是說數(shù)組長度為偶數(shù)的那一方，可以使得另一方永遠產(chǎn)生不了剩下元素異或結(jié)果為0的情況。

所以Alice要想贏，只需要兩種情況

• 原數(shù)組異或的結(jié)果是0，因為Alice是先手，所以直接就贏了
• 原數(shù)組的長度為偶數(shù)

代碼

class Solution {public boolean xorGame(int[] nums) {int res=0;if((nums.length&1)==0) return true;for (int num : nums) {res^=num;}return res==0;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 810. 黑板异或游戏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。