难度: Medium
给你一个整数数组 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 < 105n 是奇数。encoded.length == n - 1运行时间: 80 ms
内存: 32.2 MB
class Solution:
def decode(self, encoded: List[int]) -> List[int]:
n, a, b = len(encoded) + 1, 0, 0
ans = [0] * n
for i in range(0,n - 1,2):
a ^= encoded[i]
for i in range(1,n + 1):
b ^= i
ans[n - 1] = a ^ b
for i in range(n - 2,-1,-1):
ans[i] = ans[i + 1] ^ encoded[i]
return ans
'''
它是前 n 个正整数的排列，且 n 是个 奇数 。
x ^ y = 6
y ^ z = 7
x ^ z = 8
'''
'''
en[i] = pe[i] ^ pe[i + 1]
en[i + 1] = pe[i + 1] ^ pe[i + 2]
en[i + 2] = pe[i + 2] ^ pe[i + 3]
'''
题解利用了异或运算的性质（自反性：a ^ a = 0和交换律），首先计算出perm数组的最后一个元素。由于perm是前n个正整数的排列，通过异或所有1到n的整数得到b，同时通过异或编码数组中的奇数位置元素得到a。由于n是奇数，perm数组中的奇数位置元素和偶数位置元素分别异或，最终差异将体现在最后一个元素上。因此，通过a ^ b得到perm的最后一个元素。之后，利用encoded数组和已知的perm中的最后一个元素，通过逆向解码还原整个perm数组。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def decode(self, encoded: List[int]) -> List[int]:
n, a, b = len(encoded) + 1, 0, 0 # 初始化n, a, b
ans = [0] * n # 初始化输出数组
for i in range(0, n - 1, 2):
a ^= encoded[i] # 计算所有奇数位置的异或结果
for i in range(1, n + 1):
b ^= i # 计算1到n的所有数字的异或结果
ans[n - 1] = a ^ b # 计算原数组的最后一个元素
for i in range(n - 2, -1, -1):
ans[i] = ans[i + 1] ^ encoded[i] # 逆向利用encoded还原原数组的其余部分
return ans
在解码过程中，首先计算perm数组的最后一个元素是因为通过异或编码数组中奇数位置的元素和1到n的所有数字的异或结果，可以直接得到perm的最后一个元素。由于异或运算具有自反性和交换律，这种方法可以有效地利用编码数组的结构特性。而如果从第一个元素开始计算，会因为缺乏足够的信息（即不知道后面的元素情况）而难以直接确定任何一个元素。因此，首先确定最后一个元素，再逆向解码是一种更加直接和高效的策略。
选择计算所有奇数位置的异或结果得到变量a是因为，这样可以利用异或运算的性质排除掉偶数位置的元素影响，从而与1到n所有数字的异或结果（变量b）结合来直接计算出perm数组的最后一个元素。由于编码数组的奇数位置元素是由perm数组中两个相邻元素异或得到，这样的计算方式可以有效地利用编码数组提供的信息结构，简化计算过程。
计算1到n的所有数字的异或结果（变量b），并将其与所有奇数位置元素的异或结果（变量a）结合，可以确保正确还原perm数组的最后一个元素，因为所有其他元素在异或运算中相互抵消。由于perm是1到n的一个排列，所以包含所有这些数字一次，而奇数位置上使用了perm数组的元素，其结合方式确保了能够通过a^b直接获取到perm数组的最后一个元素。
逆向解码的步骤和原理基于已知perm数组的最后一个元素和encoded数组的特性。已知perm数组的最后一个元素后，我们可以使用encoded数组中的最后一个元素和perm的倒数第二个元素的关系（因为encoded[i] = perm[i] ^ perm[i+1]），逆向计算出perm的倒数第二个元素。然后，继续使用encoded数组中的前一个元素和perm数组中新计算出的元素，重复此过程，直到计算出perm的第一个元素。这种逆向解码有效地利用了异或运算的性质，即每次可以使用已知元素和encoded数组中的对应元素来恢复出前一个元素。