网站上传 文件夹结构,网站建设中的智能元素,网站备案,朝阳做网站给你一个整数数组 perm #xff0c;它是前 n 个正整数的排列#xff0c;且 n 是个 奇数 。
它被加密成另一个长度为 n - 1 的整数数组 encoded #xff0c;满足 encoded[i] perm[i] XOR perm[i 1] 。比方说#xff0c;如果 perm [1,3,2] #xff0c;那么 encoded [2,…给你一个整数数组 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]
解题思路
设x1 ^ 2 ^ 3 ^ …^n 那么perm[0]x ^ encoded[1] ^ encoded[3]… 因为encoded[i] perm[i] XOR perm[i 1]所以perm[i 1]encoded[i] XOR perm[i] 若知道了perm[0]自然可以推出perm[1],如此类推就可以推出所有
推导
为什么可知perm[0]x ^ encoded[1] ^ encoded[3]… 因为encoded[1] perm[1] XOR perm[2] encoded[3] perm[3] XOR perm[4]… 因此可得encoded[1] ^ encoded[3]… perm[1]^ perm[2]^ perm[3]^ perm[4]…
又因为perm是前 n 个正整数的排列所以 perm[0]perm[1] perm[2]^ perm[3]^ perm[4]…1 ^ 2 ^ 3 ^ …^nx
因此可得perm[0]x ^ encoded[1] ^ encoded[3]…
代码
func decode(encoded []int) []int {n:len(encoded)1odd:0for i : 1; i len(encoded) ; i2 {odd^encoded[i]}all:0for i : 1; i n ; i {all^i}pre:all^oddres : make([]int, n)res[0]prefor j, code : range encoded {cur:pre^coderes[j1]curprecur}return res
}