1720. 解码异或后的数组-蒲公英云

1720. 解码异或后的数组

困难题我唯唯诺诺，简单题我重拳出击

在这里插入图片描述
题目看着有点复杂，简单解释就是通过给出的公式
encoded[i] = arr[i] XOR arr[i + 1]，arr数组，其中encoded[] 为已知，arr[0] 为已知，算出arr[]。其实所以我们要推导出arr[i] = ?? 这么一个公式。

在推导前我们先复习一下异或的相关特点:

相同数值异或，结果为 0

x ^ x = 0
任意数值与 0 进行异或，结果为数值本身

x ^ 0 = x
异或本身满足交换律

a ^ b = b ^ a

更具上面的三个特征我们在根据encoded[i-1] = arr[i-1] XOR arr[i]进行推导

首先将等式两边同时加上异或arr[i-1],则等式变为如下

encoded[i-1] XOR arr[i-1] = arr[i-1] XOR arr[i] XOR arr[i-1]
由性质3得

encoded[i-1] XOR arr[i-1] = arr[i-1] XOR arr[i-1] XOR arr[i]
由性质1知

encoded[i-1] XOR arr[i-1] = 0 XOR arr[i]
由性质二知

arr[i] = encoded[i-1] XOR arr[i-1]

至此推导出了我们想要的公式：arr[i] = encoded[i-1] XOR arr[i-1]

实现代码如下：

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

时间复杂度: O(n), n 为encode数组的长度
空间复杂度: O(n), 返回的结果数组也算的话
参考