网站列表页模板,建设企业网站怎么样,网站开发的学习路线,微博推广方案黑板异或游戏 lc 810 - 黑板异或游戏题目描述博弈论 动态规划 lc 810 - 黑板异或游戏 难度 - 困难 原题链接 - 黑板异或游戏 题目描述 黑板上写着一个非负整数数组 nums[i] 。 Alice 和 Bob 轮流从黑板上擦掉一个数字#xff0c;Alice 先手。如果擦除一个数字后#xff0c;剩… 黑板异或游戏 lc 810 - 黑板异或游戏题目描述博弈论 动态规划 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
