⭐️前面的话⭐️
大家好！本篇文章将介绍力扣[1720. 解码异或后的数组]题解，展示代码语言暂时为：C语言与Java语言。（后续会更新C++代码）
博客主页：未见花闻的博客主页
欢迎关注点赞收藏⭐️留言
本文由未见花闻原创，CSDN首发！
首发时间：2021年11月12日
✉️坚持和努力一定能换来诗与远方！
刷题推荐书籍：《剑指offer第1版》，《剑指offer第2版》
参考在线编程网站：牛客网力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！
导航小助手
- ⭐️1720. 解码异或后的数组⭐️
- 题目详情
- 解题思路
- 源代码
- 总结
⭐️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
2 <= n <= 104
2<=n<=104
e
n
c
o
d
e
d
.
l
e
n
g
t
h
=
=
n
−
1
encoded.length == n - 1
encoded.length==n−1
0
<
=
e
n
c
o
d
e
d
[
i
]
<
=
105
0 <= encoded[i] <= 105
0<=encoded[i]<=105
0
<
=
f
i
r
s
t
<
=
105
0 <= first <= 105
0<=first<=105
| 来源：力扣（LeetCode）链接：1720. 解码异或后的数组 |
|---|
做这道题之前我们需要知道异或这个运算符的性质：
- 相同两个数进行异或运算时，结果为 0 0 0，即 a ^ a = 0 a hat{} a=0 a ^ a=0
- 任何数异或 0 0 0，数值不改变，如 a ^ 0 = a a hat{} 0=a a ^ 0=a
- 异或运算满足交换律与结合律，如 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
- 异或运算具有自反性，即 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
知道这些性质就能解决这道题了！
这道题告诉了我们异或后的数组
e
n
c
o
d
e
d
encoded
encoded和原数组
a
r
r
arr
arr的第一个元素
f
i
r
s
t
first
first，其中根据题意（假设数组下标为
i
i
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
i=0
i=0时，
a
r
r
[
i
]
=
f
i
r
s
t
arr[i]=first
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]
让
f
i
r
s
t
=
a
r
r
[
1
]
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]
再让
f
i
r
s
t
=
a
r
r
[
2
]
first = arr[2]
first=arr[2]，以此类推能够求出数组
a
r
r
arr
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]
调整
f
i
r
s
t
first
first使
f
i
r
s
t
=
a
r
r
[
i
]
first=arr[i]
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];
}
所以将数组 a r r arr arr首个元素与数组 e n c o d e d encoded encoded首个元素异或就能得到原数组 a r r arr arr第2个元素，同理数组 a r r arr arr第2个元素与数组 e n c o d e d encoded encoded第2个元素异或就能得到原数组 a r r arr arr第3个元素，以此类推遍历一遍 e n c o d e d encoded encoded数组，就能将原数组 a r r arr 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;
}
}
总结
本题的解题关键为异或运算的自反性。
