【技术分享-真题实战】找出前缀异或的原始数组（Java）

题目详情

给你一个长度为 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 <= 105
• 0 <= pref[i] <= 106


解题思路

整理题目需求：

1、两个数组

2、满足要求A[0] = B [0]    A[1] = B[0]^B[1]    A [2] = B[0]^B[1]^B[2]

即 A[i] =.  B[0] ^ B[1] ^...^B[i]

3、已知 A  求  B

做题思路：

1、什么是位运算^   :两个数进行位运算，即将两个数的二进制进行位运算，二进制相同为0，不同为1

如： 5^7 =.    101

   111

------------

    010       =    2

2、位运算的性质：   A ^ B = C    ===>    B  =   A ^C    

3、找规律：

arr[0] = pref[0]

pref[1] = arr[0]^arr[1];

arr[1] = pref[1]^arr[0] = pref[1] ^ pref[0];

arr[2] = pref[2]^arr[0]^arr[1] = pref[1]^pref[2];
arr[3] = pref[3] ^ arr[0]^arr[1]^arr[2] = pref[3]^pref[2];      

 ...

arr[i] = pref[i-1] ^ pref[i];

综上 arr[i] = pref[i-1] ^ pref[i];

publicint[] findArray(int[] pref) {
int []arr=newint[pref.length];
for (inti=0; i<arr.length; i++) {
if(i==0){
arr[i] =pref[0];
            }else {
arr[i] =pref[i] ^pref[i-1];
            }
        }
returnarr;
    }

本题难点：

1、不知道什么是异或运算。

2、没找到规律，不知道位运算的交换律，可能会将数组元素转为二进制硬算。