编程知识 cdmana.com

【算法學習】1486. 數組异或操作(java / c / c++ / python / go / rust)

非常感謝你閱讀本文~
歡迎【點贊】【收藏】【評論】~
放弃不難,但堅持一定很酷~
希望我們大家都能每天進步一點點~
本文由 二當家的白帽子 https://le-yi.blog.csdn.net/ 博客原創~



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://cdmana.com/2021/10/20211014012901075a.html

Scroll to Top