【算法学习】1486. 数组异或操作(java / c / c++ / python / go / rust)

简介: 给你两个整数,n 和 start 。数组 nums 定义为:nums[i] = start + 2 * i(下标从 0 开始)且 n == nums.length 。请返回 nums 中所有元素按位异或(XOR)后得到的结果。

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

分析

我们可以直接按照题意,暴力循环,那么时间复杂度就是O(n),是否有时间复杂度为O(1)的算法呢?

记x为变量,^是异或操作,则异或运算满足以下性质:

  1. x ^ x = 0;
  2. x ^ 0 = x;
  3. x ^ y = y ^ x(交换律);
  4. (x ^ y) ^ z = x ^ (y ^ z)(结合律);
  5. x ^ y ^ y = x(自反性);
  6. 如果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;
        }
    }
}

c

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

go

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
    }
  }
}

在这里插入图片描述


原题传送门


非常感谢你阅读本文~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~

相关文章
|
6天前
|
设计模式 测试技术 Go
学习Go语言
【10月更文挑战第25天】学习Go语言
16 4
WK
|
5天前
|
安全 Java 编译器
C++和Java哪个更好用
C++和Java各具优势,选择取决于项目需求、开发者偏好及目标平台特性。C++性能出色,适合游戏、实时系统等;Java平台独立性强,适合跨平台、安全敏感应用。C++提供硬件访问和灵活编程范式,Java有自动内存管理和丰富库支持。两者各有千秋,需根据具体需求选择。
WK
6 1
|
9天前
|
IDE Java 程序员
C++ 程序员的 Java 指南
一个 C++ 程序员自己总结的 Java 学习中应该注意的点。
16 5
|
27天前
|
Rust 资源调度 安全
为什么使用 Rust over C++ 进行 IoT 解决方案开发
为什么使用 Rust over C++ 进行 IoT 解决方案开发
53 7
WK
|
4天前
|
开发框架 移动开发 Java
C++和Java哪个更适合开发移动应用
本文对比了C++和Java在移动应用开发中的优劣,从市场需求、学习难度、开发效率、跨平台性和应用领域等方面进行了详细分析。Java在Android开发中占据优势,而C++则适合对性能要求较高的场景。选择应根据具体需求和个人偏好综合考虑。
WK
11 0
|
24天前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
292 0
高精度算法(加、减、乘、除,使用c++实现)
WK
|
5天前
|
安全 Java 编译器
C++和Java哪个更适合开发web网站
在Web开发领域,C++和Java各具优势。C++以其高性能、低级控制和跨平台性著称,适用于需要高吞吐量和低延迟的场景,如实时交易系统和在线游戏服务器。Java则凭借其跨平台性、丰富的生态系统和强大的安全性,广泛应用于企业级Web开发,如企业管理系统和电子商务平台。选择时需根据项目需求和技术储备综合考虑。
WK
8 0
|
29天前
|
缓存 并行计算 Java
C++矢量运算与java矢量运算
本文探讨了C++和Java中的矢量运算与标量运算的性能比较,解释了矢量运算的原理和为什么它比标量运算快,包括并行性、数据局部性、指令优化和数据重用等优势。文章还提供了C++和Java的矢量运算示例代码,并展示了运行结果,以证明矢量运算在处理大量数据时的性能优势。
17 0
C++矢量运算与java矢量运算
|
1月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
1月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)