lc 810 - 黑板異或游戲

難度 - 困難
原題鏈接 - 黑板異或游戲

題目描述

黑板上寫著一個非負整數數組 nums[i] 。
Alice 和 Bob 輪流從黑板上擦掉一個數字，Alice 先手。如果擦除一個數字后，剩余的所有數字按位異或運算得出的結果等于 0 的話，當前玩家游戲失敗。 另外，如果只剩一個數字，按位異或運算得到它本身；如果無數字剩余，按位異或運算結果為 0。
并且，輪到某個玩家時，如果當前黑板上所有數字按位異或運算結果等于 0 ，這個玩家獲勝。
假設兩個玩家每步都使用最優解，當且僅當 Alice 獲勝時返回 true。

示例1：
輸入: nums = [1,1,2]
輸出: false
解釋:
Alice 有兩個選擇: 擦掉數字 1 或 2。
如果擦掉 1, 數組變成 [1, 2]。剩余數字按位異或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意數字，因為 Alice 會成為擦掉最后一個數字的人，她總是會輸。
如果 Alice 擦掉 2，那么數組變成[1, 1]。剩余數字按位異或得到 1 XOR 1 = 0。Alice 仍然會輸掉游戲。

示例2：
輸入: nums = [0,1]
輸出: true

示例 3:
輸入: nums = [1,2,3]
輸出: true

提示：
1 <= nums.length <= 1000
0 <= nums[i] < 216

博弈論

如果接觸過博弈論，對于這種「判斷先手后手的必勝必敗」的題目，博弈論方向是一個優先考慮的方向。
根據題意，如果某位玩家在操作前所有數值異或和為0，那么該玩家勝利。要我們判斷給定序列時，先手是處于「必勝態」還是「必敗態」，如果處于「必勝態」返回 True，否則返回 False。

對于博弈論的題目，通常有兩類的思考方式：
經驗分析：見過類似的題目，猜一個性質，然后去證明該性質是否可推廣。
狀態分析：根據題目給定的規則是判斷「勝利」還是「失敗」來決定優先分析「必勝態」還是「必敗態」時具有何種性質，然后證明性質是否可推廣。

關于這道題，其實有兩種情況需要討論，第一個給出的數組異或和是否是0.
1.是0時，那么先手直接獲勝了返回true,這是必勝情況。
2.不是0時，那么根據題意，都是最優解的拿值，那么肯定誰拿到最后一個值，誰就輸。分析誰拿最后一個值，就只需要討論數組長度的奇偶性就可以了。
奇數Alice 拿到最后一個必輸，偶數bob 拿到最后一個，Alice 必贏。

代碼：

    public boolean xorGame(int[] nums) {int sum = 0;//先算出異或和，來討論不同的情況for(int i : nums){sum ^= i;}//和為0 直接獲勝，不為0 討論數組長度奇偶性，奇數輸，偶數贏return sum == 0 || nums.length  % 2 == 0;}

動態規劃

leetcode375. 猜數字大小 II