前言
经过前期的基础训练以及部分实战练习,粗略掌握了各种题型的解题思路。后续开始专项练习。
描述
未知 整数数组
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
。可以证明答案存在并且是唯一的。示例 1:
输入: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]示例 2:
输入:encoded = [6,2,7,3], first = 4 输出:[4,2,0,7,4]
实现原理与步骤
异或演化公式推导
encoded[i] = arr[i] ^ arr[i + 1]
=>encoded[i]^arr[i]=arr[i]^arr[i]^arr[i+1]
=>encoded[i]^arr[i]=0^arr[i+1]
=>encoded[i]^arr[i]=arr[i+1]
=>arr[i]=encode[i-1]^arr[i-1]
arr[0]=first
代码实现
class Solution {
/**
* 异或的性质:
* 1.异或自己为0
* 2.异或0等于自身
* 3.异或满足交换律和结合率
* encoded[i]=arr[i] ^ arr[i+1]
*=> encoded[i]^arr[i]=arr[i+1]
*/
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]=arr[i-1]^encoded[i-1];
}
return arr;
}
}