分析
-
本题的考点:数学。
-
首先明确一下必胜态和必败态:
(1)先手必胜状态:可以走到某一个必败状态;
(2)先手必败状态:只能走到必胜态。
- 假设
nums
中所有数据的异或和为s
,数组长度为n
,则本题的必胜态为:s=0
或者n
为偶数;必败态:s!=0
且n
为奇数。下面用数学归纳法证明:
(1)假设k
是当前剩余的元素个数,如果当前玩家面对的局面是k=0
,则当前玩家必胜;
(2)假设k<n
都成立,下面证明k=n
也成立。
(3)分为两种情况讨论:
(3.1)如果k
为奇数,则被拿走一个数据后,k
变为偶数,应转化为必胜态,此状态是必败态。
(3.2)如果k
为偶数,则被拿走一个数据后,k
变为奇数,则根据s
是否为0
又可以分为两种情况讨论:① 如果当前玩家面对的局面s=0
的话,则当前玩家必胜;② 如果当前玩家面对的局面s!=0
的话,则一定存在一种拿法使得拿过一个数据后s'
仍然不等于0
,可以使用反证法证明,假设不存在这样的方案,则无论怎么拿,s'
必为0
,因此s ^ nums[i] == 0
,所以nums[i] = s
,i
可以任意取值,因此所有的数据相同,所以s=0
,这和s=0
矛盾,因此一定存在一种拿法使得拿过一个数据后s'
仍然不等于0
,表明此状态可以转化为必败态,因此当前玩家必胜。
代码
- C++
class Solution {
public:
bool xorGame(vector<int> &nums) {
int s = 0;
for (auto x : nums) s ^= x;
return !s || nums.size() % 2 == 0;
}
};
- Java
class Solution {
public boolean xorGame(int[] nums) {
int s = 0;
for (int x : nums) s ^= x;
return s == 0 || nums.length % 2 == 0;
}
}
- Python
class Solution:
def xorGame(self, nums: List[int]) -> bool:
s = 0
for x in nums:
s ^= x
return s == 0 or len(nums) % 2 == 0
时空复杂度分析
-
时间复杂度:$O(n)$,
n
为数组长度。 -
空间复杂度:$O(1)$。