[1734] 解码异或后的排列

[1734] 解码异或后的排列
[https://leetcode-cn.com/problems/decode-xored-permutation/](https://leetcode-cn.com/problems/decode-xored-permutation/)
	给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个 奇数 。
	它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。
	给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。

题解：
 + 题中表示 n为奇数，且perm为前n个正整数的排列，则可得
		perm[0] ^ perm[1] ^ ... ^ perm[n] = 1 ^ 2 ^ 3 ^ ... ^ n;
 + 又根据异或的性质 有 a ^ b = c ==>  a ^ c = b
		perm[0] ^ perm[1] = encoded[0]
		perm[1] ^ perm[2] = encoded[1]
		==>
		perm[0] ^ perm[2] = encoded[1] ^encoded[0] ==> perm[2] = encoded[0] ^ encoded[1] ^ perm[0]
		perm[3] = perm[2] ^ encoded[2] = encoded[0] ^ encoded[1] ^ enconded[2] ^ perm[0]
		perm[n] = encoded[0] ^ encoded[1] ^ ... ^ enconded[n - 1] ^ perm[0]
		==>
		perm[0] ^ perm[1] ^ perm[2] ^ ... ^ perm[n] =  perm[0] ^ (encoded[0] ^ perm[0]) ^ (encoded[0] ^ encoded[1] ^ perm[0])...
		==>
		perm[0] ^ perm[1] ^ perm[2] ^ ... ^ perm[n] =  n个perm[0] 的异或（n为奇数） + encoded[0] ^ encoded[0] ^ encoded[1] ^ encoded[0] ^ encoded[1] ^ encoded[2] ...
		perm[0] ^ perm[1] ^ perm[2] ^ ... ^ perm[n] =  n个perm[0] 的异或（n为奇数） + (n - 1)个encoded[0] + (n - 2)个encoded[1] + ... (n-(n-1))个encoded[n - 1]
 + 因为异或相同为0  偶数倍的异或可约去 则
		perm[0] ^ perm[1] ^ perm[2] ^ ... ^ perm[n] =  perm[0] ^ encoded[1] ^ encoded[3] ^ ... ^ encoded[n - 1]
 +此时等式左边已知，右边只有perm[0]是未知数，则可求得perm[0]

代码如下：
```CPP
class Solution {
public:
    vector<int> decode(vector<int>& encoded) {
        std::vector<int> perm;
        int n = (int)encoded.size() + 1;    //perm数组的长度
        int all_num_sum = 0;        //用于保存perm所有数据的异或值
        int encoded_num_sum = 0;    //用于计算所有奇数位的encoded数据的异或值
        for(int i = 0; i < n; ++i)
        {
            all_num_sum = all_num_sum ^ (i + 1);
            if(i % 2 == 1 && i < (int)encoded.size())
            {
                encoded_num_sum = encoded_num_sum ^ encoded[i];
            }
        }
		
		//已知开始数值 可根据encoded[i] = perm[i] XOR perm[i + 1] 依次获得计算结果
        int start_num = encoded_num_sum ^ all_num_sum;
        perm.push_back(start_num);
        for(int i = 0; i < (int)encoded.size(); ++i)
        {
            start_num = start_num ^ encoded[i];
            perm.push_back(start_num);
        }

return perm;
    }
};
```