尧图网站设计 尧图网站设计YAOTU DESIGN
ARTICLE DETAIL

资讯详情

深耕网站设计与一线实操的经验洞察。

1734. Decode XORed Permutation:利用 XOR 自反性还原奇数长度排列(LeetCode-Go 解法全解)

1734. Decode XORed Permutation:利用 XOR 自反性还原奇数长度排列(LeetCode-Go 解法全解) 1734. Decode XORed Permutation利用 XOR 自反性还原奇数长度排列LeetCode-Go 解法全解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本题1734. Decode XORed Permutation 仓库中的实现为主线从 XOR 的三个基本性质出发推导出如何借助全集异或与奇数位异或先锁定perm[0]再沿编码链逐位还原整个数组并给出复杂度分析与可运行的测试验证帮助读者掌握一类已知相邻差分还原序列的位运算通解。一、题目回顾与核心难点1.1 题意重述有一个整数数组perm它是前n个正整数的排列即1, 2, ..., n各出现一次且n恒为奇数。它被编码为长度为n - 1的数组encoded编码规则为encoded[i] perm[i] XOR perm[i 1]例如perm [1, 3, 2]时encoded [1 XOR 3, 3 XOR 2] [2, 1]。题目保证答案存在且唯一给定encoded要求还原出原始数组perm。1.2 约束条件3 n 10^5n是奇数encoded.length n - 11.3 示例示例 1Input: encoded [3,1] Output: [1,2,3]验证perm [1,2,3]时encoded [1 XOR 2, 2 XOR 3] [3,1]。示例 2Input: encoded [6,5,4,6] Output: [2,4,1,5,3]1.4 核心难点表面上看n - 1个方程、n个未知数似乎信息不足。真正让题目可解的关键有两点排列的封闭性perm是前n个正整数的排列意味着perm[0] XOR perm[1] XOR ... XOR perm[n-1]等于1 XOR 2 XOR ... XOR n这个值不需要知道排列顺序也能直接算出来n 为奇数的结构性保证n是奇数才能让编码数组奇数下标的异或恰好覆盖perm[1]到perm[n-1]的全部元素从而构造出total ^ odd消去冗余、单点定位perm[0]。二、算法基石XOR 的三大性质本题整个解题过程只依赖异或运算的三条性质性质表达式说明自反性x XOR x 0相同值异或结果为 0恒等性x XOR 0 x与 0 异或保持不变交换律与结合律a XOR b b XOR a(a XOR b) XOR c a XOR (b XOR c)异或顺序不影响结果其中自反性是本题的核心武器任何出现偶数次的元素会在整体异或中互相抵消。这与仓库中 136. Single Number 的解法 一脉相承——第 136 题正是利用result ^ nums[i]让成对出现的数字全部抵消、留下唯一落单者。原文档解题思路部分也明确指出这一题与第 136 题和第 137 题思路类似借用x ^ x 0这个性质解题。三、推导过程如何锁定 perm[0]3.1 第一步计算全集异或 total由于perm是1 ~ n的排列无论顺序如何全部元素异或的结果恒等于total 1 XOR 2 XOR 3 XOR ... XOR n这一步不需要知道排列只需要知道n时间复杂度为 O(n)。3.2 第二步计算奇数下标异或 odd考察encoded中奇数下标的元素odd encoded[1] XOR encoded[3] XOR ... XOR encoded[n-2]由于encoded[i] perm[i] XOR perm[i1]把上式展开odd (perm[1] XOR perm[2]) XOR (perm[3] XOR perm[4]) XOR ... XOR (perm[n-2] XOR perm[n-1])注意n是奇数所以encoded的长度n - 1是偶数其奇数下标取值为1, 3, ..., n-2恰好覆盖了perm[1]到perm[n-1]的全部元素。这就是题目保证 n 为奇数的意义所在——若不是奇数这一步就无法精确覆盖除 perm[0] 外的所有元素。3.3 第三步total XOR odd 得到 perm[0]将 total 与 odd 异或total XOR odd (perm[0] XOR perm[1] XOR ... XOR perm[n-1]) XOR (perm[1] XOR perm[2] XOR ... XOR perm[n-1]) perm[0] // 其余元素成对出现经 x XOR x 0 全部抵消perm[1] ~ perm[n-1]在两个集合中各出现一次异或后相互抵消归零只剩下perm[0]。由此成功锚定第一个原始元素。3.4 第四步沿编码链递推还原全部元素拿到perm[0]后问题就变成了简单的链式递推。因为encoded[i] perm[i] XOR perm[i1]两边同时异或perm[i]perm[i1] perm[i] XOR encoded[i]逐层推导encoded[0] perm[0] XOR perm[1] perm[0] XOR encoded[0] perm[0] XOR (perm[0] XOR perm[1]) perm[1] perm[1] XOR encoded[1] perm[1] XOR (perm[1] XOR perm[2]) perm[2] ... perm[n-2] XOR encoded[n-2] perm[n-1]依次类推即可还原出原数组perm中的所有数。四、仓库源码逐行剖析4.1 核心实现原文档给出的解法与仓库中的实际源码完全一致位于 1734. Decode XORed Permutation.gopackage leetcode func decode(encoded []int) []int { n, total, odd : len(encoded), 0, 0 for i : 1; i n1; i { total ^ i } for i : 1; i n; i 2 { odd ^ encoded[i] } perm : make([]int, n1) perm[0] total ^ odd for i, v : range encoded { perm[i1] perm[i] ^ v } return perm }逐段解读代码段作用细节说明n, total, odd : len(encoded), 0, 0初始化n即原始数组长度len(perm)因为encoded长度为n-1所以perm长度为n1for i : 1; i n1; i { total ^ i }计算全集异或total 1 XOR 2 XOR ... XOR (n1)对应原始文档中的[1, n1]区间for i : 1; i n; i 2 { odd ^ encoded[i] }计算奇数下标异或步长为 2遍历encoded[1], encoded[3], ...perm : make([]int, n1)分配结果数组长度为n1恰好等于len(encoded) 1perm[0] total ^ odd锚定首元素见上文 3.3 节推导for i, v : range encoded { perm[i1] perm[i] ^ v }链式递推利用perm[i1] perm[i] XOR encoded[i]逐个还原return perm返回结果直接返回无需额外处理4.2 边界情况与正确性说明n 最小为 3当n 3时encoded长度为 2total 1 XOR 2 XOR 3 0odd encoded[1]perm[0] 0 XOR encoded[1] encoded[1]随后perm[1] perm[0] XOR encoded[0]、perm[2] perm[1] XOR encoded[1]逻辑依然成立答案唯一性题目保证答案存在且唯一因此在3 n 10^5的约束下上述推导不会出现歧义无需排序整个算法不依赖对perm排序仅靠位运算性质完成还原这是相对朴素做法的最大优势。五、测试用例与运行验证仓库为本题配套了完整的单元测试位于 1734. Decode XORed Permutation_test.go覆盖了题目给出的两个示例package leetcode import ( fmt testing ) type question1734 struct { para1734 ans1734 } // para 是参数 // one 代表第一个参数 type para1734 struct { encoded []int } // ans 是答案 // one 代表第一个答案 type ans1734 struct { one []int } func Test_Problem1734(t *testing.T) { qs : []question1734{ { para1734{[]int{3, 1}}, ans1734{[]int{1, 2, 3}}, }, { para1734{[]int{6, 5, 4, 6}}, ans1734{[]int{2, 4, 1, 5, 3}}, }, } fmt.Printf(------------------------Leetcode Problem 1734------------------------\n) for _, q : range qs { _, p : q.ans1734, q.para1734 fmt.Printf(【input】:%v 【output】:%v\n, p, decode(p.encoded)) } fmt.Printf(\n\n\n) }测试用例逐一手动推演验证用例一encoded [3, 1]期望[1, 2, 3]n 2encoded 长度perm长度 3total 1 XOR 2 XOR 3 0odd encoded[1] 1perm[0] 0 XOR 1 1perm[1] 1 XOR 3 2perm[2] 2 XOR 1 3得到[1, 2, 3]正确。用例二encoded [6, 5, 4, 6]期望[2, 4, 1, 5, 3]n 4perm长度 5total 1 XOR 2 XOR 3 XOR 4 XOR 5 1odd encoded[1] XOR encoded[3] 5 XOR 6 3perm[0] 1 XOR 3 2递推perm[1] 2 XOR 6 4perm[2] 4 XOR 5 1perm[3] 1 XOR 4 5perm[4] 5 XOR 6 3得到[2, 4, 1, 5, 3]正确。读者可以在仓库根目录通过go test ./leetcode/1734.Decode-XORed-Permutation/运行该测试验证实现与期望输出一致。六、复杂度分析与正确性论证6.1 时间复杂度整个算法共有四段线性遍历计算totalO(n)计算oddO(n/2)递推还原permO(n)。总时间复杂度为O(n)在n 10^5的约束下非常高效。与 LeetCode-Go 项目对单题解法runtime beats 100%的目标定位一致具体性能表现以实际评测为准本文不引用未经证实的性能数据。6.2 空间复杂度只额外分配了结果数组perm长度为n 1辅助变量为常数个因此空间复杂度为O(n)结果数组本身不计入辅助空间时为 O(1) 额外空间视 LeetCode 判题约定而定。6.3 为什么 n 必须是奇数——一个反例推演为帮助读者理解题目条件这里做一个反例推演。假设n 4偶数则encoded长度为 3奇数下标只有encoded[1]odd perm[1] XOR perm[2]此时odd只覆盖了perm[1], perm[2]并未覆盖perm[3]。计算total XOR odd(perm[0] XOR perm[1] XOR perm[2] XOR perm[3]) XOR (perm[1] XOR perm[2]) perm[0] XOR perm[3]得到的不是单一元素无法锚定perm[0]。这就是题目强制n为奇数的根本原因只有奇数长度才能保证奇数下标编码与去掉 perm[0] 的剩余元素集合一一对应。七、同源思路LeetCode-Go 中的 XOR 系列问题本题的核心思想——用整体异或抵消成对元素——在 LeetCode-Go 仓库中是一个反复出现的模式可以串联学习题号题目与本题的关系136. Single Number找出唯一落单元素最基础的x XOR x 0应用全部异或即得答案137. Single Number II找出只出现一次的元素其余出现 3 次在自反性基础上引入按位统计的进阶变形1734. Decode XORed Permutation还原 XOR 相邻差分排列在全集异或基础上进一步利用奇数下标编码覆盖剩余集合构造锚点原文档解题思路明确指出本题与第 136、137 题思路类似。第 136 题的源码136. Single Number.go只用了一个循环func singleNumber(nums []int) int { result : 0 for i : 0; i len(nums); i { result ^ nums[i] } return result }对比可见第 136 题是全集异或的零成本应用因为目标元素天然唯一而第 1734 题由于需要还原整个序列必须在全集异或之外再构造一个剔除锚点元素的集合这正是odd存在的意义。理解这一层递进关系有助于在面试中面对差分 排列类问题时快速定位解题方向。八、方法总结与扩展思考8.1 解题方法论沉淀遇到相邻差分类还原问题先检查是否具备全集封闭特性如本题的排列性质若有则可直接计算出全集异或利用奇偶位置构造子集使子集与全集去掉某个元素形成精确互补从而用total XOR subset单点定位锚定一个元素后其余元素可沿差分链线性递推无需任何比较或排序操作整个过程可以总结为一句口诀全集异或除锚点锚点异或差分还原。8.2 变体与扩展若题目改为给定encoded与perm[0]的值则total与odd都不再需要直接沿链递推即可问题降级为纯 O(n) 遍历若perm不是排列而是任意数组则缺少全集封闭条件本题的 O(n) 解法不再成立需要其他约束位运算解法的可读性依赖对 XOR 性质的熟悉程度在代码评审或面试讲解中建议先口述成对抵消的直观含义再展示代码。8.3 在 LeetCode-Go 仓库中阅读本题的路径题目文档leetcode/1734.Decode-XORed-Permutation/README.md核心实现1734. Decode XORed Permutation.go单元测试1734. Decode XORed Permutation_test.go关联基础题136. Single Number、137. Single Number II结语1734 题是位运算 排列结构结合的经典题目n为奇数的条件、total ^ odd的锚点构造、以及沿编码链的线性递推三步环环相扣最终得到一个 O(n) 时间、O(n) 空间的优雅解法。掌握本题不仅能应对同类相邻 XOR 差分还原问题更能加深对异或自反性在算法设计中应用的理解——这也是 LeetCode-Go 仓库将其作为 XOR 系列重要一环的价值所在。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考
返回列表