传送门

思路

往位运算想就是想复杂了。根据题目意思，perm[i]的范围是[1,n]，且每个perm[i]不重复。这就意味着perm[0]^perm[1]^…^perm[n]是已知的。
假设：

perm=[a,b,c,d,e]，encoded=[f,g,h,i];

显然有：

f = a^b;
g = b^c;
h = c^d;
i = d^e;

我们再设已知的perm[0]^perm[1]^…^perm[n]=k，根据异或的性质：一个数异或自己得到0，任意一个数异或0等于它自己。所以我们可以用k去异或g = b^c与i = d^e来让k==a，这样我们就算出了perm[0]。再根据递推关系perm[i+1] = perm[i]^encoded[i]就可以算出整个perm。

代码

class Solution {
public:
    vector<int> decode(vector<int>& encoded) {
        vector<int> perm;
        int a = 0;
        const int  n = encoded.size() + 1;

        for (int i = 1; i <= n; i++) {
            a ^= i;
        }
        for (int i = 1; i <= encoded.size() - 1; i += 2) {
            a ^= encoded[i];
        }

        perm.push_back(a);
        for (int i = 0; i < encoded.size(); i++) {
            perm.push_back(perm[i] ^ encoded[i]);
        }

        return perm;
    }
};