编程知识 cdmana.com

[apprentissage de l'algorithme] 1486. Fonctionnement exclusif du tableau (Java / C / C + + / python / go / Rust)

Merci beaucoup de lire cet article~
Bienvenue【- Oui.】【Collection】【Commentaires】~
Il n'est pas difficile d'abandonner,Mais ça doit être cool d'insister~
J'espère que nous progresserons tous un peu tous les jours~
Cet article est rédigé par Deux chapeaux blancs https://le-yi.blog.csdn.net/ Blog original~



1486. Tableau Xor Operation:

Deux entiers.,n Et start .

Tableau nums Défini comme suit::nums[i] = start + 2 * i(Indice de 0 C'est parti.)Et n == nums.length .

Veuillez revenir. nums Tous les éléments en bitxor(XOR)Résultats ultérieurs.

Exemple 1

Entrée:
	n = 5, start = 0
Produits:
	8
Explication:
	Tableau nums Pour [0, 2, 4, 6, 8],Parmi eux (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 .
     "^" Xor bitwise XOR Opérateur.

Exemple 2

Entrée:
	n = 4, start = 3
Produits:
	8
Explication:
	Tableau nums Pour [3, 5, 7, 9],Parmi eux (3 ^ 5 ^ 7 ^ 9) = 8.

Exemple 3

Entrée:
	n = 1, start = 7
Produits:
	7

Exemple 4

Entrée:
	n = 10, start = 5
Produits:
	2

Conseils

  • 1 <= n <= 1000
  • 0 <= start <= 1000
  • n == nums.length

Analyse

On peut suivre l'ordre du jour.,Le cycle de la violence,Donc la complexité temporelle estO(n),Si la complexité temporelle estO(1)Et l'algorithme de?

NotexVariable,^Est une opération XOR,L'opération Xor satisfait aux propriétés suivantes::

  1. x ^ x = 0;
  2. x ^ 0 = x;
  3. x ^ y = y ^ x(Loi d'échange);
  4. (x ^ y) ^ z = x ^ (y ^ z)(Droit de l'Union);
  5. x ^ y ^ y = x(Réflexivité);
  6. Six- Oui.4Multiple de,x ^ (x + 1) ^ (x + 2) ^ (x + 3) = 0;
  • À calculer Formule de résultat Pour:start ^ (start + 2) ^ (start + 4) ^ ⋯ ^(start + 2 * (n − 1)).
  • S'il y a une fonction sumXor(x) Peut être calculé 0 ^ 1 ^ 2 ^ ⋯ ^ x .
  • Pour une variablexEtn,CalculsumXor(s - 1) ^ sumXor(s + n - 1)Les résultats de,D'après ce qui précède Nature1 Vous pouvez 0 ^ 1 ^ 2 ^ … ^ (s - 1) La valeur de0,C'est devenu 0 ^ s ^ (s + 1) ^ (s + 2) ^ ⋯ ^ (s + n - 1) ,Selon Nature2 Et0Faire une opération Xor ou vous - même,Et le résultat final est s ^ (s + 1) ^ (s + 2) ^ ⋯ ^ (s + n - 1) ,Ce résultat est très proche de ce que nous allons calculer..
  • Si on commande s = start / 2 ,Prends ça. Formule de résultat Convertir en (s ^ (s + 1) ^ (s + 2) ^ ⋯ ^ (s + n - 1)) * 2,Ce n'est pas vrai.,Parce que c'est fait divisé par2Pendant le fonctionnement de,Le BIT le plus bas est perdu.,Mais nous pouvons gérer les bits les plus bas individuellement.
  • Observation Formule de résultat C'est clair. (start + 2),(start + 4) ,… ,(start + 2 * (n − 1)) Les mêmes propriétés impaires et paires,EtstartD'accord.,C'est le plus bas ou les deux.0,Ou les deux.1,Base seulement1Seulement si l'opération Xor est effectuée1.C'est juste questartEst impair etnC'est un nombre impair.,Le résultat final le plus bas e C'est ça.1.
  • À ce moment - là, Formule de résultat Peut être transformé en: ((sumXor(s - 1) ^ sumXor(s + n - 1)) * 2) | e .

Tant que nous pouvons implémenter la fonctionsumXor(x),Alors le calcul du problème peut être faitO(1)La complexité temporelle de,Selon Nature6 Et Nature2 On doit juste y réfléchir.xDivisé par4Le reste de,C'est le plus bas.2Bits,On peut déduire ce qui suit::

x % 4 = 0 Binaire de:xx…x00
x % 4 = 1 Binaire de:xx…x01
x % 4 = 2 Binaire de:xx…x10
x % 4 = 3 Binaire de:xx…x11

  • x % 4 = 0,sumXor(x) = x;
  • x % 4 = 1,sumXor(x) = (x - 1) ^ x,Disponibilité simplifiée sumXor(x) = 1;
  • x % 4 = 2,sumXor(x) = (x - 2) ^ (x - 1) ^ x,Disponibilité simplifiée sumXor(x) = x | 1;
  • x % 4 = 3,sumXor(x) = 0;
  • x % 4 équivalent à x & 3 Fonctionnement,Et en théorie, & L'opération est plus efficace que % Fonctionnement plus rapide;

Explication du problème

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

Insérer la description de l'image ici


Porte d'entrée d'origine


版权声明
本文为[Deux chapeaux blancs.]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211014012901075a.html

Scroll to Top