企业官网建设流程全解析

LeetCode-Go 题解 | 1720. Decode XORed Array：异或编码数组的前缀递推解码实战

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇文章以 LeetCode-Go 仓库中 1720.Decode-XORed-Array 题解文档 为核心，完整讲解第 1720 题「解码异或数组」的数学原理、Go 语言实现、复杂度分析与单元测试验证，并对照仓库中的同主题姊妹题（1734.Decode-XORed-Permutation）辨析两种解码思路的差异。读完本文，你将掌握「已知相邻异或关系与首元素时利用 XOR 自反性递推还原数组」这一基础位运算技巧，并能直接复用仓库中的解法与测试模板完成本地验证。

题目陈述：从编码数组还原隐藏数组

存在一个未知的整数数组arr，由n个非负整数组成。它被编码成另一个长度为n - 1的整数数组encoded，编码规则为：

encoded[i] = arr[i] XOR arr[i + 1]

例如，若arr = [1,0,2,1]，则：

encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

题目给定编码后的数组encoded，以及原数组的第一个元素first（即arr[0]），要求返回原始数组arr。题目保证答案存在且唯一。

输入输出示例

示例 1：

输入：encoded = [1,2,3], first = 1 输出：[1,0,2,1] 解释：若 arr = [1,0,2,1]，则 first = 1，encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

示例 2：

输入：encoded = [6,2,7,3], first = 4 输出：[4,2,0,7,4]

数据约束

• 2 <= n <= 10^4
• encoded.length == n - 1
• 0 <= encoded[i] <= 10^5
• 0 <= first <= 10^5

数组规模最大为 10^4 级别，因此只要解法在 O(n) 时间复杂度内完成即可轻松通过，本题定位为简单题（Easy）。

数学原理：XOR 运算的自反性是解码的关键

XOR（异或）运算满足几个关键代数性质，它们是本解法的理论根基：

• 自反性：x ^ x = 0，任何数与自己异或结果为 0；
• 幺元性：x ^ 0 = x，任何数与 0 异或保持不变；
• 交换律与结合律：异或结果与运算顺序无关。

已知encoded[i] = arr[i] ^ arr[i + 1]，在等式两边同时异或arr[i]，利用自反性可得：

encoded[i] ^ arr[i] = arr[i] ^ arr[i + 1] ^ arr[i] = arr[i + 1]

即：

arr[i + 1] = arr[i] ^ encoded[i]

这说明：只要知道arr[i]，就能唯一确定arr[i + 1]。而题目恰好给出了arr[0] = first，因此可以从左到右逐位递推，把整个arr还原出来——这正是「前缀递推」的思路，编码过程完全可逆。

Go 实现：一行递推还原原数组

原题解文档给出的 Go 解法位于仓库 leetcode/1720.Decode-XORed-Array/1720. Decode XORed Array.go，实现如下：

package leetcode func decode(encoded []int, first int) []int { arr := make([]int, len(encoded)+1) arr[0] = first for i, val := range encoded { arr[i+1] = arr[i] ^ val } return arr }

逐行拆解这段代码：

1. arr := make([]int, len(encoded)+1)：原数组比编码数组多一个元素，因此直接按n = len(encoded) + 1预分配切片，避免后续动态扩容；
2. arr[0] = first：题目给出的第一个元素直接落位；
3. for i, val := range encoded：遍历编码数组，i是下标、val是encoded[i]；
4. arr[i+1] = arr[i] ^ val：利用arr[i+1] = arr[i] ^ encoded[i]逐位递推，每一步只依赖上一步的结果，无任何额外状态；
5. 最后返回完整的arr。

以示例 1（encoded = [1,2,3]，first = 1）手动推演一遍：

arr[0] = 1 arr[1] = arr[0] ^ encoded[0] = 1 ^ 1 = 0 arr[2] = arr[1] ^ encoded[1] = 0 ^ 2 = 2 arr[3] = arr[2] ^ encoded[2] = 2 ^ 3 = 1 最终结果：[1,0,2,1] ✅

复杂度分析

• 时间复杂度：O(n)，仅需一趟线性遍历；
• 空间复杂度：O(n)，用于存储结果数组arr（若将first就地写入encoded尾部则可降为 O(1)，但可读性优先，仓库解法选择新建数组）。

单元测试验证：仓库测试模板解读

LeetCode-Go 仓库为每道题配套了标准测试文件，本题对应 1720. Decode XORed Array_test.go，采用「参数表驱动」的测试风格：

package leetcode import ( "fmt" "testing" ) type question1720 struct { para1720 ans1720 } // para 是参数 // one 代表第一个参数 type para1720 struct { encoded []int first int } // ans 是答案 // one 代表第一个答案 type ans1720 struct { one []int } func Test_Problem1720(t *testing.T) { qs := []question1720{ { para1720{[]int{1, 2, 3}, 1}, ans1720{[]int{1, 0, 2, 1}}, }, { para1720{[]int{6, 2, 7, 3}, 4}, ans1720{[]int{4, 2, 0, 7, 4}}, }, } fmt.Printf("------------------------Leetcode Problem 1720------------------------\n") for _, q := range qs { _, p := q.ans1720, q.para1720 fmt.Printf("【input】:%v 【output】:%v\n", p, decode(p.encoded, p.first)) } fmt.Printf("\n\n\n") }

这个测试结构揭示了仓库的通用测试约定：para1720封装输入参数（encoded与first），ans1720封装期望输出，两者组合成question1720用例表；测试通过decode(p.encoded, p.first)调用真实解法并打印结果，两个用例与题目的官方示例一一对应。这也印证了仓库 README 中「100% test coverage」的工程实践——每个题解目录都遵循题号.题目名.go+题号.题目名_test.go+README.md的三件套结构。

在本地运行测试

仓库根目录的 gotest.sh 提供了统一的测试入口，对全部题解执行覆盖率为 atomic 模式的测试：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

也可以只针对本题所在包单独运行：

go test -v ./leetcode/1720.Decode-XORed-Array/

姊妹题辨析：1734. Decode XORed Permutation 的差异

本题属于 LeetCode 的「Decode XORed」系列，仓库中还收录了升级版 1734.Decode-XORed-Permutation 题解文档，两题编码规则完全一致（encoded[i] = perm[i] XOR perm[i + 1]），但有一个关键差异：

• 1720：题目直接给出arr[0] = first，递推起点已知，一维线性递推即可；
• 1734：题目只给出encoded，没有给出首元素，但额外声明原数组是「前 n 个正整数的排列」且 n 为奇数，需要先利用x ^ x = 0的性质求出perm[0]，再进行同样的递推。

1734 题的具体做法是：先把[1, n+1]区间内所有数异或得到total，再把encoded中奇数下标的元素异或得到odd，两者相异或即可得到perm[0]（因为重复出现的元素在异或中抵消）；拿到perm[0]后，后续递推与 1720 完全一致。建议将两题对照阅读，可以更深刻地理解「XOR 自反性」在不同信息条件下的两种应用形态。

边界情况与易错点小结

1. 结果数组长度：arr的长度是len(encoded) + 1，漏加 1 会导致最后一个元素丢失；
2. 递推起点：arr[0]必须等于first，不能把first与encoded[0]弄混；
3. 数据范围：encoded[i]与first均不超过 10^5，所有中间结果不会溢出int，无需特殊处理；
4. 最小规模：当n = 2时encoded只有一个元素，此时arr = [first, first ^ encoded[0]]，代码天然覆盖该分支。

总结

LeetCode 第 1720 题是 XOR 位运算入门的经典简单题：核心只有一条递推式arr[i+1] = arr[i] ^ encoded[i]，背后是 XOR 自反性x ^ x = 0。在 LeetCode-Go 仓库中，本题以「题解文档 + 解法源码 + 表驱动测试」三件套的形式沉淀于 leetcode/1720.Decode-XORed-Array/ 目录，解法 O(n) 时间、O(n) 空间，结构清晰可直接复用；将其与 1734.Decode-XORed-Permutation 对照学习，即可完整掌握 XOR 编码/解码问题的两条经典解题路径。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go