难度: Medium
给你一个长度为 n 的 整数 数组 pref 。找出并返回满足下述条件且长度为 n 的数组 arr ：
pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i].注意 ^ 表示 按位异或（bitwise-xor）运算。
可以证明答案是 唯一 的。
示例 1：
输入：pref = [5,2,0,3,1] 输出：[5,7,2,3,2] 解释：从数组 [5,7,2,3,2] 可以得到如下结果： - pref[0] = 5 - pref[1] = 5 ^ 7 = 2 - pref[2] = 5 ^ 7 ^ 2 = 0 - pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3 - pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1
示例 2：
输入：pref = [13] 输出：[13] 解释：pref[0] = arr[0] = 13
提示：
1 <= pref.length <= 1050 <= pref[i] <= 106运行时间: 56 ms
内存: 32.5 MB
class Solution:
def findArray(self, pref: List[int]) -> List[int]:
return [pref[0]] + [x^y for x,y in pairwise(pref)]
题解的核心思路是通过利用已知的前缀异或数组 pref 来还原原始数组 arr。首先，arr[0] 直接等于 pref[0]。接着，由于 pref[i] 表示从 arr[0] 到 arr[i] 的异或结果，可以得出 arr[i] = pref[i-1] ^ pref[i]，即当前元素与前一个元素的前缀异或。这是基于异或运算的性质：如果 a ^ b = c，则 c ^ b = a。因此，通过遍历 pref 数组，使用每两个相邻元素进行异或运算，即可逐步还原出原始数组 arr。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def findArray(self, pref: List[int]) -> List[int]:
# 初始化结果数组 arr，首元素直接为 pref[0]
arr = [pref[0]]
# 使用生成器表达式遍历 pref 数组的相邻两元素
# 对每对相邻元素进行异或运算，计算 arr 的当前元素
arr += [x^y for x,y in pairwise(pref)]
return arr
对于i=0的情况，公式`arr[i] = pref[i-1] ^ pref[i]`并不适用，因为当i=0时，不存在pref[i-1]。因此，对于i=0的情况，arr[0]直接等于pref[0]。这是一个特殊情况，需要单独处理。
解释中提到的公式`pref[i-1] ^ pref[i]`并不是用来得到`arr[0]`的。在算法实现中，`arr[0]`是直接从`pref[0]`得到的，即`arr[0] = pref[0]`。之后的数组元素，从`arr[1]`开始，才使用`pref[i-1] ^ pref[i]`来计算。
`pairwise`函数不是Python标准库中的函数。它可以通过使用`itertools`模块中的`pairwise`函数实现（Python 3.10及以上版本支持）。对于低版本的Python，可以手动实现一个类似的功能，例如使用列表推导和zip函数：`[x^y for x, y in zip(pref, pref[1:])]`。
异或运算具有可逆的特性。在这个题目中，已知`pref[i]`是从`arr[0]`到`arr[i]`的连续元素的异或结果。因此，`pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]`。如果我们知道`pref[i-1] = arr[0] ^ arr[1] ^ ... ^ arr[i-1]`，那么根据异或运算的性质，`pref[i-1] ^ pref[i]`的结果将会是`(arr[0] ^ ... ^ arr[i-1]) ^ (arr[0] ^ ... ^ arr[i-1] ^ arr[i])`。由于异或运算是自己与自己异或结果为0，非自身异或保持不变，所以这将简化为`arr[i]`。这样就利用了异或的性质，从已知的前缀异或结果中恢复出原数组的每个元素。