class Solution {
public:
vector<int> decode(vector<int>& encoded) {
}
};
1734. 解码异或后的排列
给你一个整数数组 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原站题解
golang 解法, 执行用时: 128 ms, 内存消耗: 9.1 MB, 提交时间: 2022-11-20 17:19:20
func decode(encoded []int) []int {
n := len(encoded)
total := 0
for i := 1; i <= n+1; i++ {
total ^= i
}
odd := 0
for i := 1; i < n; i += 2 {
odd ^= encoded[i]
}
perm := make([]int, n+1)
perm[0] = total ^ odd
for i, v := range encoded {
perm[i+1] = perm[i] ^ v
}
return perm
}
python3 解法, 执行用时: 164 ms, 内存消耗: 30.3 MB, 提交时间: 2022-11-20 17:18:37
class Solution:
def decode(self, encoded: List[int]) -> List[int]:
n = len(encoded) + 1
total = reduce(xor, range(1, n + 1))
odd = 0 # 奇数异或和
for i in range(1, n - 1, 2):
odd ^= encoded[i] # encoded[1] = perm[1] * perm[2]
perm = [total ^ odd]
for i in range(n - 1):
perm.append(perm[-1] ^ encoded[i])
return perm