【5.6】LeetCode每日一题· 解码异或后的数组

2021年05月06日 8时16分

标签： LeetCode 递推数学

## 题目描述
未知 整数数组 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]
```

#### 提示
```
2 <= n <= 10^4
encoded.length == n - 1
0 <= encoded[i] <= 10^5
0 <= first <= 10^5

```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/decode-xored-array)

## 解题思路
因为`encoded[i] = arr[i] XOR arr[i+1]`，所以知道`arr[i]`和`encoded[i]`之后，可以得到`arr[i+1] = arr[i] XOR^(-1) encoded[i]`，其中`XOR^(-1)`表示亦或运算的逆运算。而我们已经知道了`first = arr[0]`，因此只要知道亦或运算的逆运算是什么，就可以从`arr[0]`和`encoded`数组，推出`arr`数组。

考虑亦或运算的性质，设$$x$$为未知数，有
$$0 \,\,\text{XOR}\,\, x = 0 \\Rightarrow x = 0 = 0 \,\,\text{XOR}\,\, 0$$
$$0 \,\,\text{XOR}\,\, x = 1 \\Rightarrow x = 1 = 0 \,\,\text{XOR}\,\, 1$$
$$1 \,\,\text{XOR}\,\, x = 0 \\Rightarrow x = 1 = 1 \,\,\text{XOR}\,\, 0$$
$$1 \,\,\text{XOR}\,\, x = 1 \\Rightarrow x = 0 = 1 \,\,\text{XOR}\,\, 1$$

由于上述运算规律对于非负整数的每一个二进制位都成立，因此
$$a \,\,\text{XOR}\,\, x = b \\Rightarrow x = a \,\,\text{XOR}\,\, b$$
其中$$a, x, b$$为整数。
因此，我们知道亦或运算的逆运算仍然是亦或运算，所以
`arr[i+1] = arr[i] XOR encoded[i]`。

## 代码
```cpp
class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        vector<int> res;
        res.emplace_back(first);
        for(int i = 0; i < encoded.size(); i++){
            res.emplace_back(res[i]^encoded[i]);
        }
        return res;
    }
};
```

## 用时和内存
> 执行用时：20 ms，在所有 C++提交中击败了98.80%的用户
> 内存消耗：25.5 MB，在所有 C++提交中击败了5.20%的用户

所有评论

176****2703 2021年05月06日 08:53:14
不错

参与主题/评论回复

176****2703 发表于2021年05月06日 08:53:14
不错

回复评论

邮箱

图形验证码

邮箱验证码

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【5.6】LeetCode每日一题· 解码异或后的数组

所有评论

新增评论