Leetcode 1734. Decode XORed Permutation

[Woodyiiiiiii]

类似题目：

• 1734. Decode XORed Permutation
• 2527. Find Xor-Beauty of Array
• 1720. Decode XORed Array

这道题我想到了^的交换律，从而想到了只要求出数组内任意一个数，就可以求出全部数组，然而没想到如何求出一个数。因为我漏看了条件。

首先，XOR的交换律，即a^b=c就有a^c=b和b^c=a。这也是之前写swap方法(交换两个数)能够用XOR的原因。

然后，注意到题目中，数组是1~n的任意permutation。所以，对于a0，我们可以通过encoded[1],encoded[3]...得到a1^a2,a3^a4...得到其他所有的XOR结果，从而提前用1～n的所有XOR结果去XOR除a0外的XOR结果，得到a0，从而推出数组所有元素。

class Solution {
    public int[] decode(int[] encoded) {
        int sum = 0;
        for (int i = 1; i <= encoded.length + 1; ++i) {
            sum ^= i;
        }
        int others = 0;
        for (int i = 1; i < encoded.length; i += 2) {
            others ^= encoded[i];
        }
        int a = sum ^ others;
        int[] ans = new int[encoded.length + 1];
        ans[0] = a;
        for (int i = 1; i < ans.length; ++i) {
            ans[i] = encoded[i - 1] ^ a;
            a = ans[i];
        }
        return ans;
    }
}

---

• https://leetcode.com/problems/decode-xored-permutation/solutions/1031107/java-c-python-straight-forward-solution/?orderBy=hot