README.md

1734. 解码异或后的排列

English Version

题目描述

给你一个整数数组 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 < 105
• n 是奇数。
• encoded.length == n - 1

解法

Python3

class Solution:
    def decode(self, encoded: List[int]) -> List[int]:
        n = len(encoded) + 1
        a = b = 0
        for i in range(0, n - 1, 2):
            a ^= encoded[i]
        for i in range(n + 1):
            b ^= i
        ans = [a ^ b]
        for e in encoded[::-1]:
            ans.append(ans[-1] ^ e)
        return ans[::-1]

Java

class Solution {

    public int[] decode(int[] encoded) {
        int n = encoded.length + 1;
        int[] ans = new int[n];
        int a = 0;
        int b = 0;
        for (int i = 0; i < n - 1; i += 2) {
            a ^= encoded[i];
        }
        for (int i = 0; i < n + 1; ++i) {
            b ^= i;
        }
        ans[n - 1] = a ^ b;
        for (int i = n - 2; i >= 0; --i) {
            ans[i] = ans[i + 1] ^ encoded[i];
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> decode(vector<int>& encoded) {
        int n = encoded.size() + 1;
        vector<int> ans(n);
        int a = 0, b = 0;
        for (int i = 0; i < n - 1; i += 2) a ^= encoded[i];
        for (int i = 0; i < n + 1; ++i) b ^= i;
        ans[n - 1] = a ^ b;
        for (int i = n - 2; i >= 0; --i) ans[i] = ans[i + 1] ^ encoded[i];
        return ans;
    }
};

Go

func decode(encoded []int) []int {
	n := len(encoded) + 1
	ans := make([]int, n)
	a, b := 0, 0
	for i := 0; i < n-1; i += 2 {
		a ^= encoded[i]
	}
	for i := 0; i < n+1; i++ {
		b ^= i
	}
	ans[n-1] = a ^ b
	for i := n - 2; i >= 0; i-- {
		ans[i] = ans[i+1] ^ encoded[i]
	}
	return ans
}

...