⭐️前面的话⭐️

大家好！本篇文章将介绍力扣[1720. 解码异或后的数组]题解，展示代码语言暂时为：C语言与Java语言。（后续会更新C++代码）

?博客主页：未见花闻的博客主页
?欢迎关注?点赞?收藏⭐️留言?
?本文由未见花闻原创，CSDN首发！
?首发时间：?2021年11月12日?
✉️坚持和努力一定能换来诗与远方！
?刷题推荐书籍：?《剑指offer第1版》，?《剑指offer第2版》
?参考在线编程网站：?牛客网?力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
?作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

---

---

---

⭐️1720. 解码异或后的数组⭐️

?题目详情

一个未知整数数组 arr由n个非负整数组成。经编码后变为长度为 n - 1 的另一个整数数组encoded，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1]经编码后得到 encoded = [1,2,3] 。给你编码后的数组 encoded 和原数组arr 的第一个元素 first（arr[0]）。请解码返回原数组 arr 。可以证明答案存在并且是唯一的。

示例：

输入：encoded = [1,2,3], first = 1
输出：[1,0,2,1]
解释：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]
输入：encoded = [6,2,7,3], first = 4
输出：[4,2,0,7,4]

提示：

$2<=n<=104$
$encoded.length==n-1$
$0<=encoded[i]<=105$
$0<=first<=105$

来源：力扣（LeetCode）链接：1720. 解码异或后的数组

?解题思路

做这道题之前我们需要知道异或这个运算符的性质：

1. 相同两个数进行异或运算时，结果为$0$，即 a   ^   a = 0 a hat{} a=0 a ^ a=0
2. 任何数异或$0$，数值不改变，如 a   ^   0 = a a hat{} 0=a a ^ 0=a
3. 异或运算满足交换律与结合律，如 a   ^   b   ^   c = b   ^   a   ^   c a hat{} b hat{} c=b hat{} a hat{} c a ^ b ^ c=b ^ a ^ c， a   ^   ( b + c ) = a   ^   b + a   ^   c a hat{} (b+c)=a hat{} b+a hat{} c a ^ (b+c)=a ^ b+a ^ c
4. 异或运算具有自反性，即 a   ^   b   ^   a = b   ^   a   ^   a = b   ^   0 = b a hat{} b hat{} a=b hat{} a hat{} a=b hat{} 0=b a ^ b ^ a=b ^ a ^ a=b ^ 0=b

知道这些性质就能解决这道题了！
这道题告诉了我们异或后的数组$encoded$和原数组$arr$的第一个元素$first$，其中根据题意（假设数组下标为$i$）：
e n c o d e d [ i ] = a r r [ i ]   ^   a r r [ i + 1 ] encoded[i]=arr[i] hat{} arr[i+1] encoded[i]=arr[i] ^ arr[i+1]
当$i=0$时，$arr[i]=first$，根据异或运算的自反性，有以下推导：
a r r [ 0 ]   ^   a r r [ 1 ]   ^   f i r s t = e n c o d e d [ 0 ]   ^   f i r s t = a r r [ 1 ] arr[0] hat{} arr[1] hat{} first=encoded[0] hat{} first=arr[1] arr[0] ^ arr[1] ^ first=encoded[0] ^ first=arr[1]
让$first=arr[1]$，得:
a r r [ 1 ]   ^   a r r [ 2 ]   ^   f i r s t = e n c o d e d [ 1 ]   ^   f i r s t = a r r [ 2 ] arr[1] hat{} arr[2] hat{} first=encoded[1] hat{} first=arr[2] arr[1] ^ arr[2] ^ first=encoded[1] ^ first=arr[2]
再让$first=arr[2]$，以此类推能够求出数组$arr$所有元素。
a r r [ i ]   ^   a r r [ i + 1 ]   ^   a r r [ i ] = e n c o d e d [ i ]   ^   a r r [ i ] = a r r [ i + 1 ] arr[i] hat{} arr[i+1] hat{} arr[i]=encoded[i] hat{} arr[i]=arr[i+1] arr[i] ^ arr[i+1] ^ arr[i]=encoded[i] ^ arr[i]=arr[i+1]
a r r [ i + 1 ] = e n c o d e d [ i ]   ^   a r r [ i ] arr[i+1]=encoded[i] hat{} arr[i] arr[i+1]=encoded[i] ^ arr[i]
调整$first$使$first=arr[i]$，能够得到下面结论：
a r r [ i + 1 ] = e n c o d e d [ i ]   ^   f i r s t arr[i+1]=encoded[i] hat{} first arr[i+1]=encoded[i] ^ first
代码表示就是：

int i = 0;
arr[0] = first;
for (i = 0; i < encodedSize; i++) 
{
    arr[i + 1] = encoded[i] ^ first;
    first = arr[i + 1]; 
}

所以将数组$arr$首个元素与数组$encoded$首个元素异或就能得到原数组$arr$第2个元素，同理数组$arr$第2个元素与数组$encoded$第2个元素异或就能得到原数组$arr$第3个元素，以此类推遍历一遍$encoded$数组，就能将原数组$arr$所有元素都求出来。

?源代码

C语言：

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

Java语言：

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

?总结

本题的解题关键为异或运算的自反性。

觉得文章写得不错的老铁们，点赞评论关注走一波！谢谢啦！