一、题目描述

给定一个非负整数数组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<n; i++){
            arr[i] = encoded[i-1] ^ arr[i-1];
        }

        return arr;
    }