【5.11】LeetCode每日一题·解码异或后的序列

2021年05月11日 10时20分

标签： LeetCode 二进制数学

## 题目描述

给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个 奇数 。

它被加密成另一个长度为`n - 1`的整数数组`encoded`，满足`encoded[i] = perm[i] XOR perm[i + 1]`。比方说，如果`perm = [1,3,2]`，那么`encoded = [2,1]`。

给你`encoded`数组，请你返回原始数组`perm`。题目保证答案存在且唯一。

#### 示例1

```
输入：encoded = [3,1]
输出：[1,2,3]
解释：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]
```

#### 示例2

```
输入：encoded = [6,5,4,6]
输出：[2,4,1,5,3]
```

#### 提示

```
3 <= n < 10^5
n 是奇数。
encoded.length == n - 1
```

#### 来源

> 来源：力扣（LeetCode）
> 链接：[1734. 解码异或后的排列 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/decode-xored-permutation/)

## 解题思路

依旧考察亦或运算的性质。假设perm序列为$$(a_1, a_2, \cdots, a_n)$$，注意到这是$$1-n$$的全排列，因此有

$$a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0 \oplus 1 \oplus 2 \oplus \cdots \oplus n$$

该值可以通过亦或运算的**性质5**在$$O(1)$$内求出：

$$\forall i \in Z, 4i \oplus (4i+1) \oplus (4i+2) \oplus (4i+3) = 0$$

因为$$n$$为奇数，因此$$n \% 4$$只能为$$1$$或者$$3$$，

当$$n \% 4 = 1$$时，有$$ a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0 \oplus 1 \oplus 2 \oplus \cdots \oplus n = n\oplus (n-1)$$

当$$n \% 4 = 3$$时，有$$a_1 \oplus a_2 \oplus \cdots \oplus a_n = \oplus 1 \oplus 2 \oplus \cdots \oplus n = 0$$

而通过`encoded`数组，我们可以知道

$$encoded[0] = a_1\oplus a_2$$，

$$encoded[1] = a_2\oplus a_3$$，

即$$encoded[i] = a_{i+1} \oplus a_{i+2}$$，

记$$S = a_1 \oplus a_2 \oplus \cdots \oplus a_n$$，由于$$n$$为奇数，因此

$$a_1 = S \oplus (a_2 \oplus a_3) \oplus (a_4 \oplus a_5) \oplus \cdots \oplus (a_{n-1} \oplus a_n)$$

即

$$a_1 = S \oplus encoded[1] \oplus encoded[3] \oplus \cdots \oplus encoded[n-2]$$

得到$$a_1$$后，就可以通过

$$a_{i} = encoded[i-2] \oplus a_{i-1} \, (1\leq i \leq n)$$

递推求出`perm`数组中的每个值。

## 代码

```cpp
class Solution {
public:
    vector<int> decode(vector<int>& encoded) {
        int n = encoded.size() + 1, a = 0;
        if(n % 4 == 1){
            a = n ^ (n-1);
        }else if(n % 4 == 3){
            a = 0;
        }
        for(int i = 1; i < encoded.size(); i += 2){
            a = a ^ encoded[i];
        }
        vector<int> perm(n);
        perm[0] = a;
        for(int i = 0; i < encoded.size(); i++){
            a = a ^ encoded[i];
            perm[i+1] = a;
        }
        return perm;

}
};
```

## 用时和内存

> 执行用时：144 ms，在所有 C++提交中击败了91.63%的用户
> 内存消耗：99.8 MB，在所有 C++提交中击败了27.09%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【5.11】LeetCode每日一题·解码异或后的序列

所有评论

暂无评论

新增评论