从数组中,我需要找到通过对连续子阵列进行异或所获得的值,然后对如此获得的值进行异或运算.
INPUT
一行包含作为数组元素的整数.
例如[1,2,3]
OUTPUT
在单独的行中打印与每个测试用例相对应的答案.
到目前为止,我设法使用循环和递归方法构建两个策略.
我的所有方法都没有在大输入尺寸上提供良好的性能.
例如1 XOR 2 XOR 3 XOR(1 XOR 2)XOR(2 XOR 3)XOR(1 XOR 2 XOR 3)= 2
你能建立一个更好的算法吗？也许是动态编程方法？
from functools import reduce
# Calculate the XOR
def XOR(L):
return reduce(lambda x,y: x ^ y,L)
# Recursive approach
def allSubArraysXOR(L,L2=None):
if L2==None:
L2 = L[:-1]
if L==[]:
if L2==[]:
return 0
return allSubArraysXOR(L2,L2[:-1])
return XOR(L) ^ allSubArraysXOR(L[1:],L2)
# Loop - yielding approach
def getAllWindows(L):
for w in range(1,len(L)+1):
for i in range(len(L)-w+1):
yield XOR(L[i:i+w])
a = [int(a_temp) for a_temp in input().strip().split(' ')]
print(allSubArraysXOR(a))
# print(XOR(getAllWindows(a)))
解决方法
我们不需要枚举(2 ** n)个子阵列来解决这个问题.
XOR有一些有用的属性,我们可以利用它来在O(n)时间内解决这个问题.特别：
>对于任何k：k XOR k == 0;
>对于任何k：k XOR 0 == k.
> XOR is both commutative and associative.
要解决您的问题,我们首先需要计算每个元素在子数组中出现的次数.出现偶数次的任何元素都可以忽略不计.其余的需要一起进行异或(每次只需一次).
让我们看看这如何适用于您的示例：
1 XOR 2 XOR 3 XOR (1 XOR 2) XOR (2 XOR 3) XOR (1 XOR 2 XOR 3) = # open brackets 1 XOR 2 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3 XOR 1 XOR 2 XOR 3 = # reorder 1 XOR 1 XOR 1 XOR 2 XOR 2 XOR 2 XOR 2 XOR 3 XOR 3 XOR 3 = # group (1 XOR 1 XOR 1) XOR (2 XOR 2 XOR 2 XOR 2) XOR (3 XOR 3 XOR 3) = # remove pairs 1 XOR 0 XOR 3 = 1 XOR 3 = 2
以下是这个想法的O(n)实现：
def xor_em(lst):
n = len(lst)
ret = 0
for i,el in enumerate(lst):
count = (i + 1) * (n - i)
if count % 2:
ret ^= el
return ret
print xor_em([1,3])
子阵列的计数是通过
count = (i + 1) * (n - i)
使用观察结果,当前元素(包括其自身)左边有1个元素,右边有n – i(也包括自身).将两者相乘得出从当前元素的左侧开始并且在其右侧结束的子阵列的数量.
我们现在已经将问题减少到寻找产品为奇数的对(i 1)和(n – i).观察到获得奇数乘积的唯一方法是将两个本身相乘的数相乘(这可以通过考虑两个被乘数的主要因子来看出).
有两种情况需要考虑：
>当n为偶数时,(i 1)和(n-i)之一总是偶数.这意味着对于偶数长度的列表,算法总是返回零.
>当n为奇数时,(i 1)*(n-i)对于i = 0,4,…,(n-1)是奇数.
这导致以下简化的解决方案：
def xor_em(lst):
if len(lst) % 2 == 0:
return 0
else:
return reduce(operator.xor,lst[::2])