[数据结构与算法]【力扣】——解码异或后的数组

题目描述：数组arr由n个非负整数组成，经编码后变为长度为?n - 1?的另一个整数数组?encoded?，其中?encoded[i] = arr[i]^arr[i + 1]?

给你编码后的数组?encoded?和原数组?arr?的第一个元素?first（arr[0]）。

请解码返回原数组?arr?。可以证明答案存在并且是唯一的。

思路：对于异或来说，若a^b=c，那么就有a^c=b、b^c=a（在解题时找出的规律，后面会解释）所以除arr[0]为first外，arr[i]=arr[i-1]^encoded[i-1]

代码如下：

int* decode(int* encoded, int encodedSize, int first, int* returnSize){
    *returnSize=encodedSize+1;
    int *arr=(int*)malloc(sizeof(int)*(encodedSize+1));
    arr[0]=first;
    for(int i=1;i<encodedSize+1;++i)
    {
        arr[i]=encoded[i-1]^arr[i-1];
    }
    return arr;

}

结果：

?现在来解释为什么

关于异或操作符就不过多赘述，a^b的结果的二进制位展示了a和b二进制位中不同的地方

例：

7：00000000? 00000000? 00000000? 00000111

5：00000000? 00000000? 00000000? 00000101

7^5：00000000? 00000000? 00000000? 00000010

二者二进制位的第二位不同，所以结果为2

如果只给一个数字2，无法确定原来异或的两个数字，二进制中为0的地方无法确定原数字是1^1还是0^0,二进制中为1的地方也无法确定是哪一个数字的二进制位上的1

如果是给2和5的话，那么就可以确定下来

比如2的二进制第一位为0，5的二进制第一位是1，那么就可以确定另外的一个数字的二进制的第一位是1，其它二进制位同理

而2和5的二进制的第一位数字异或后结果就是1，其它二进制位也是如此，这样就能得出唯一的结果7

因为题目中规定arr由非负整数组成，在本地测试负数的时候结果也是正确的，但毕竟测试用例不多，不保证这个规律是一定正确的

完