 模拟到 O(1) 数学规律的异或推导实战)
★ FEATURED ARTICLE 教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇技术指南围绕 LeetCode 第 1486 题「数组异或操作」展开完整讲解题目规则、四种语言的模拟实现以及将时间复杂度从 O(n) 压缩到 O(1) 的数学规律解法并深入剖析「右移提公因子 补回最低位」的异或推导全过程。读完后你不仅能直接 AC 本题还能掌握一类「连续整数段异或」问题的通用结论calc 函数并将其迁移到仓库中其他异或类题目如 1720. 解码异或后的数组、1310. 子数组异或查询的求解中。题目描述与 Tag这是 LeetCode 上的第1486题难度为简单Tag 为「数学」、「模拟」。给你两个整数n和start。数组nums定义为nums[i] start 2 * i下标从0开始且n nums.length。请返回nums中所有元素按位异或XOR后得到的结果。题目的四个示例示例 1 输入n 5, start 0 输出8 解释数组 nums 为 [0, 2, 4, 6, 8]其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) 8。^ 为按位异或 XOR 运算符。 示例 2 输入n 4, start 3 输出8 解释数组 nums 为 [3, 5, 7, 9]其中 (3 ^ 5 ^ 7 ^ 9) 8。 示例 3 输入n 1, start 7 输出7 示例 4 输入n 10, start 5 输出2数据范围提示1 n 10000 start 1000n nums.length也就是说数组长度n最大只有10^3量级而nums[i]是一个首项为start、公差为2的等差数列。解法一模拟O(n)数据范围只有10^3按照题目要求从头到尾模拟一遍即可先把首项start作为初始答案然后对i 1..n-1依次将start 2 * i异或进答案。Java 代码class Solution { public int xorOperation(int n, int start) { int ans start; for (int i 1; i n; i) { int x start 2 * i; ans ^ x; } return ans; } }C 代码class Solution { public: int xorOperation(int n, int start) { int ans start; for (int i 1; i n; i) { int x start 2 * i; ans ^ x; } return ans; } };Python 代码class Solution: def xorOperation(self, n: int, start: int) - int: ans start for i in range(1, n): x start 2 * i ans ^ x return ansTypeScript 代码function xorOperation(n: number, start: number): number { let ans start; for (let i 1; i n; i) { let x start 2 * i; ans ^ x; } return ans; };复杂度分析时间复杂度O(n)需要遍历n - 1个元素。空间复杂度O(1)只使用常数个变量。模拟解法思路直观、代码简洁是面试中最稳妥的保底方案。解法二数学规律O(1)为什么需要数学解法如果数据范围出到10^8上述模拟解法大概率会发生 TLE。事实上如果数据范围放大到10^8本题难度应该会被归为「中等」甚至「困难」。因此掌握本题背后的数学规律是有价值的。原式子为start ⊕ (start 2) ⊕ (start 4) ⊕ ... ⊕ (start 2 * (n - 1))第一步提出公因子 2我们发现原式子中只有数值2是固定系数由题目给定考虑将其提出得到新式子(s ⊕ (s 1) ⊕ (s 2) ⊕ ... ⊕ (s (n - 1))) * 2其中 s start / 2之所以进行这样的转换是因为我们想利用1 ⊕ 2 ⊕ 3 0的异或性质。但是转换到这一步我们发现「新式子」与「原式子」其实并不相等。我们需要考虑两者之间的差值关系。第二步理解右移一位的本质不难发现将「原式」转化成「新式」的集体除以2的操作相当于将每个item进行「右移一位」。而「异或运算」是每一位独立计算的因此「右移一位」不会影响移动部分除最低位以外的部分的计算结果。本质上「原式」转化成「新式」是将最终答案ans进了「右移」一位的操作。因此如果要重新得到ans我们需要将其重新「左移」一位并把最后一位异或结果补回即原式结果 新式结果 1 | e其中e为最后一位异或结果只能是0或者1其余高位为0。第三步补回最低位 e重新观察「原式」式子中每个item奇偶性相同都是start 2i与start同奇偶这意味着它们二进制的最低位相同。根据n和start的奇偶数搭配不难得出最后一位的结果e n start 1若start为偶数所有元素最低位均为0最低位异或结果为0若start为奇数每个元素最低位均为1n个1异或的结果取决于n的奇偶性即n 1。两者综合即为n start 1。第四步O(1) 计算连续整数段的异或剩下的问题在于如何在不遍历的情况下计算「新式」结果。前面说到转化的目的是为了利用1 ⊕ 2 ⊕ 3 0的异或特性。事实上这个式子存在一般性的推广结论4i ⊕ (4i 1) ⊕ (4i 2) ⊕ (4i 3) 0因为每四个连续整数恰好覆盖了一个「二进制低位两位」的完整周期异或结果恒为0。因此只需要对最后一项进行% 4讨论即可这部分属于「结论」即代码中的calc函数calc(x) x % 4 0 → x x % 4 1 → 1 x % 4 2 → x 1 x % 4 3 → 0它给出的是0 ⊕ 1 ⊕ 2 ⊕ ... ⊕ x的闭式结果。总结一下假设最终答案为ans整个处理过程就是把原式中的每个item右移一位除以2计算ans中除了最低一位以外的结果然后再将ans左移一位重新乘以2把原本丢失的最后一位结果重新补上。补上的过程利用了n和start的「奇偶性」讨论。各语言实现Java 代码class Solution { int calc(int x) { if (x % 4 0) return x; else if (x % 4 1) return 1; else if (x % 4 2) return x 1; else return 0; } public int xorOperation(int n, int start) { // 整体除以 2利用 %4 结论计算 ans 中除「最低一位」的结果 int s start 1; int prefix calc(s - 1) ^ calc(s n - 1); // 利用「奇偶性」计算 ans 中的「最低一位」结果 int last n start 1; int ans prefix 1 | last; return ans; } }C 代码class Solution { public: int calc(int x) { if (x % 4 0) return x; else if (x % 4 1) return 1; else if (x % 4 2) return x 1; else return 0; } int xorOperation(int n, int start) { int s start 1; int prefix calc(s - 1) ^ calc(s n - 1); int last n start 1; int ans (prefix 1) | last; return ans; } };Python 代码class Solution: def calc(self, x): if x % 4 0: return x elif x % 4 1: return 1 elif x % 4 2: return x 1 else: return 0 def xorOperation(self, n: int, start: int) - int: s start 1 prefix self.calc(s - 1) ^ self.calc(s n - 1) last n start 1 ans (prefix 1) | last return ansTypeScript 代码function calc(x: number): number { if (x % 4 0) return x; else if (x % 4 1) return 1; else if (x % 4 2) return x 1; else return 0; } function xorOperation(n: number, start: number): number { let s start 1; let prefix calc(s - 1) ^ calc(s n - 1); let last n start 1; let ans (prefix 1) | last; return ans; };复杂度分析时间复杂度O(1)整个计算过程只包含常数次位运算与取模运算。空间复杂度O(1)。关键知识点异或运算的三大性质本题以及仓库中大量位运算题目反复使用异或运算的以下三条基本性质值得单独总结相同数值异或结果为 0a ^ a 0任意数值与 0 异或结果为数值本身a ^ 0 a异或满足交换律与结合律a ^ b b ^ a(a ^ b) ^ c a ^ (b ^ c)。这些性质在本题中的具体体现连续四个整数4i, 4i1, 4i2, 4i3异或为0本质是「每位上恰好出现偶数次 1」补回最低位时e n start 1本质是「同奇偶的若干个数最低位异或结果取决于个数奇偶性」。在仓库的 Index/位运算.md 索引中围绕这些性质展开的同类题目还包括解码异或后的数组简单利用encoded[i-1] ^ arr[i-1] arr[i]递推解码核心正是「两边同异或arr[i-1]后利用性质 1、2 化简」子数组异或查询中等利用xor(l, r) xor(1, r) ⊕ xor(1, l - 1)的前缀异或容斥本质同样是「偶数次异或结果为 0」只出现一次的数字 II中等利用 32 位逐位统计后mod 3还原唯一元素只出现一次的数字 III中等先整体异或得到两个唯一数的异或值再按某一位是否为 1 分组求解黑板异或游戏困难把「去掉某个数等价于在异或和上异或该数」用于博弈论推导。两种解法对比小结解法思路时间复杂度空间复杂度适用场景模拟按nums[i] start 2i逐项异或O(n)O(1)数据范围小如本题n 1000时最稳妥数学规律提出公因子 2、整体右移一位计算再补回最低位O(1)O(1)数据范围大如n达10^8时唯一可行方案两道解法的核心差异在于是否理解「异或按位独立、与整除 2 可交换」这两个性质。模拟解法作为保底手段在任何情况下都正确数学解法将区间异或问题规约为% 4结论与奇偶性讨论代码量同样极小值得作为模板记忆遇到同类型「等差数列异或」或「连续整数段异或」问题可直接套用。仓库中的相关资源本题原文LeetCode/1481-1490/1486. 数组异或操作简单.md位运算专题索引Index/位运算.md数学专题索引Index/数学.md异或类姊妹题1720. 解码异或后的数组、1310. 子数组异或查询、137. 只出现一次的数字 II本文是「刷穿 LeetCode」系列中针对第No.1486篇的完整技术解读。该系列文章除讲解解题思路外还会给出尽可能简洁的代码涉及通解时还会给出相应的代码模板。在仓库地址中你可以找到系列文章的题解链接、对应代码、LeetCode 原题链接以及其他优选题解。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐手把手跑通黑苹果EFIOpCore-Simplify从2天到半小时手把手跑通黑苹果EFIOpCore Simplify从2天到半小时 花了两天、翻了十几页英文文档开机还是那个红色禁止标志——这是黑苹果新手最常见的下场。 O教程文档LeetCode 1310 子数组异或查询从暴力到前缀异或的 O(1) 区间查询实战LeetCode 1310 子数组异或查询从暴力到前缀异或的 O 1 区间查询实战 导读 本文以 LeetCode 1310「子数组异或查询」为核心讲解如何文档教程知识库LeetCode 1835 题解所有数对按位与结果的异或和——从逐位计数到 O(mn) 的整体异或推导LeetCode 1835 题解所有数对按位与结果的异或和——从逐位计数到 O mn 的整体异或推导 本篇是 LeetCode 题解仓库中第 1835 题「文档教程知识库上一篇3步搞定B站视频下载难题DownKyi下载姬新手完全指南下一篇哔哩下载姬完全指南免费高效的B站视频下载终极方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
阅读完成 · 觉得有帮助？
