LeetCode力扣算法题目|【算法学习】1486. 数组异或操作（java / c / c++ / python / go / rust） c语言|python|golang|rust|java

非常感谢你阅读本文~
欢迎【点赞】【?收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由二当家的白帽子 https://le-yi.blog.csdn.net/ 博客原创~

文章目录

1486. 数组异或操作：
样例 1
样例 2
样例 3
样例 4
提示
分析
题解
- java
- c
- c++
- python
- go
- rust
原题传送门

1486. 数组异或操作：给你两个整数，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 <= 1000
0 <= start <= 1000
n == nums.length

分析 【LeetCode力扣算法题目|【算法学习】1486. 数组异或操作（java / c / c++ / python / go / rust）】我们可以直接按照题意，暴力循环，那么时间复杂度就是O(n)，是否有时间复杂度为O(1)的算法呢？
记x为变量，^是异或操作，则异或运算满足以下性质：

x ^ x = 0；
x ^ 0 = x；
x ^ y = y ^ x（交换律）；
(x ^ y) ^ z = x ^ (y ^ z)（结合律）；
x ^ y ^ y = x（自反性）；
如果x是4的倍数，x ^ (x + 1) ^ (x + 2) ^ (x + 3) = 0；

本题要计算的结果公式为：start ^ (start + 2) ^ (start + 4) ^ ? ^(start + 2 * (n ? 1))。
如果有一个函数 sumXor(x) 可以计算 0 ^ 1 ^ 2 ^ ? ^ x 。
对于某变量x和n，计算sumXor(s - 1) ^ sumXor(s + n - 1)的结果，根据上面的性质1 可以将 0 ^ 1 ^ 2 ^ … ^ (s - 1) 的值抵消为0，就变成 0 ^ s ^ (s + 1) ^ (s + 2) ^ ? ^ (s + n - 1) ，根据性质2 可知与0做异或操作还是自己，最后结果就变成 s ^ (s + 1) ^ (s + 2) ^ ? ^ (s + n - 1) ，这个结果很接近我们要计算的内容。
如果我们令 s = start / 2 ，把结果公式转换成 (s ^ (s + 1) ^ (s + 2) ^ ? ^ (s + n - 1)) * 2，这样并不成立，因为在做除以2的操作时，最低位丢失了，但是我们可以单独处理最低位。
观察结果公式可知 (start + 2)，(start + 4) ，… ，(start + 2 * (n ? 1)) 的奇偶性质相同，而且和start一致，也就是最低位要么都是0，要么都是1，只有基数个1做异或操作时才会是1。也就是只有start是奇数并且n是奇数的时候，最终结果的最低位 e 才会是1。
这时结果公式可以转化为： ((sumXor(s - 1) ^ sumXor(s + n - 1)) * 2) | e 。

只要我们可以实现函数sumXor(x)，那么题目计算就可以做到O(1)的时间复杂度，根据性质6 和性质2 我们只需要考虑x除以4的余数，也就是最低2位，可以得到如下推导：
x % 4 = 0 的二进制位：xx…x00
x % 4 = 1 的二进制位：xx…x01
x % 4 = 2 的二进制位：xx…x10
x % 4 = 3 的二进制位：xx…x11

x % 4 = 0，sumXor(x) = x；
x % 4 = 1，sumXor(x) = (x - 1) ^ x，简化可得 sumXor(x) = 1；
x % 4 = 2，sumXor(x) = (x - 2) ^ (x - 1) ^ x，简化可得 sumXor(x) = x | 1；
x % 4 = 3，sumXor(x) = 0；
x % 4 等同于 x & 3 的操作，而且理论上 & 操作要比 % 操作更快；

题解 java

class Solution {public int xorOperation(int n, int start) {int s = start >> 1, e = n & start & 1; int ret = sumXor(s - 1) ^ sumXor(s + n - 1); return ret << 1 | e; }public int sumXor(int x) {switch (x & 3) {case 0: return x; case 1: return 1; case 2: return x | 1; default: // x & 3 == 3 return 0; } } }

int xorOperation(int n, int start) {int s = start >> 1, e = n & start & 1; int ret = sumXor(s - 1) ^ sumXor(s + n - 1); return ret << 1 | e; }int sumXor(int x) {switch (x & 3) {case 0: return x; case 1: return 1; case 2: return x | 1; default: // x & 3 == 3 return 0; } }

c++

class Solution {public: int xorOperation(int n, int start) {int s = start >> 1, e = n & start & 1; int ret = sumXor(s - 1) ^ sumXor(s + n - 1); return ret << 1 | e; }int sumXor(int x) {switch (x & 3) {case 0: return x; case 1: return 1; case 2: return x | 1; default: // x & 3 == 3 return 0; } } };

python

class Solution: def xorOperation(self, n: int, start: int) -> int: def sumXor(x): if x % 4 == 0: return x if x % 4 == 1: return 1 if x % 4 == 2: return x | 1 return 0 s = start >> 1 e = n & start & 1 ans = sumXor(s - 1) ^ sumXor(s + n - 1) return ans << 1 | e

func xorOperation(n, start int) (ans int) {s, e := start>>1, n&start&1 ret := sumXor(s-1) ^ sumXor(s+n-1) return ret<<1 | e }func sumXor(x int) int {switch x & 3 {case 0: return x case 1: return 1 case 2: return x | 1 default: return 0 } }

rust

impl Solution { pub fn xor_operation(n: i32, start: i32) -> i32 { let s = start >> 1; let e = n & start & 1; let ret = Solution::sum_xor(s - 1) ^ Solution::sum_xor(s + n - 1); return ret << 1 | e }fn sum_xor(x: i32) -> i32 { match x & 3 { 0 => x, 1 => 1, 2 => x | 1, _ => 0 } } }