一、题目描述

给定一个非负整数数组arr，经过编码后新数组encode的长度为n-1，编码的规则为encode[i] = arr[ i ] ★arr [i+1] (★为异或符)。给出编码后encode数组，和原来数组的第一个元素。返回解码后的arr数组。

输入：encoded = [1,2,3], first = 1
输出：[1,0,2,1]
输入：encoded = [6,2,7,3], first = 4
输出：[4,2,0,7,4]


二、题目分析

可以通过★运算反向推理的出

encode[i-1] = arr[ i ] ★ arr [i-1]

encode[i-1] ★ arr [i-1] = arr[ i ] ★arr [i-1] ★ arr [i-1]

encode[i-1] ★ arr [i-1] = arr[ i ]

注：

位运算这里指定是将整数先转换为二进制数，然后再进行位运算，1★1或 0★0 都为0，1★0为1；所以得0★任何数都为任何数。任何数★任何数都0；

三、解题思路

通过推导encode[i] ★ arr [i+1] = arr[ i ]得到每一位数。

代码实现：

public int[] decode(int[] encoded, int first) {
int n = encoded.length+1;
int[] arr = new int[n];
arr[0] = first;
for(int i = 1; i arr[i] = encoded[i-1] ^ arr[i-1];
}
return arr;
}