1 題目描述

2 解題思路

·根據游戲規則，輪到某個玩家時，如果當前黑板上所有數字異或結果等于 0，則當前玩家獲勝。由于 Alice 是先手，因此如果初始時黑板上所有數字異或結果等于 0，則Alice 獲勝。

?

如果初始時黑板上所有數字異或結果不等于 0：

由于兩人交替擦除數字，且每次都恰好擦掉一個數字，因此對于這兩人中的任意一人，其每次在擦除數字前，黑板上剩余數字的個數的奇偶性一定都是相同的。

我們從數組nums 長度的奇偶性來討論，看看奇偶性和Alice的輸贏有沒有關系。

Alice 面臨失敗的狀態只有一種情況，即無論擦掉哪一個數字，剩余所有數字的異或結果都等于 0，下面證明這是不可能的

根據上述計算，可以得到?S=0，與這時候的假設?S≠0?矛盾

?

因此當數組的長度是偶數時，先手Alice?總能找到一個數字，在擦掉這個數字之后剩余的所有數字異或結果不等于?0。

?

在 Alice 擦掉這個數字后，黑板上剩下奇數個數字，無論Bob 擦掉哪個數字，留給Alice 的一定是偶數個數字，此時Alice 要么獲勝，要么仍可以找到一個數字，在擦掉這個數字之后剩余的所有數字異或結果不等于0。因此當Alice先手，且數組的長度是偶數的時候，Alice每輪至少不敗。當黑板上數字異或之和為0，或者沒有數的時候，Alice贏。

同理可得，當數組的長度是奇數時，Alice 在擦掉一個數字之后，留給 Bob 的一定是黑板上剩下偶數個數字，因此Bob 每輪至少不敗。當黑板上數字異或之和為0，或者沒有數的時候，Bob贏。

?

綜上所述，當且僅當以下兩個條件至少滿足一個時，Alice 必勝：

數組 nums 的全部元素的異或結果等于 0；

數組nums 的長度是偶數。

?

分析完之后，代碼就很簡單了：

class Solution:def xorGame(self, nums: List[int]) -> bool:if(len(nums)%2==0):return Truesum=0for i in nums:sum=sum^iif(sum==0):return Truereturn False

?

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。