Benachbartes bitweises XOR

<code class="language-php"><?php
/**
 * @param Integer[] $derived
 * @return Boolean
 */
function doesValidArrayExist($derived) {
    $xorSum = 0;
    foreach ($derived as $num) {
        $xorSum ^= $num;
    }
    return $xorSum === 0;
}

// Example 1
$derived1 = [1, 1, 0];
echo doesValidArrayExist($derived1) ? 'true' : 'false'; // Output: true

// Example 2
$derived2 = [1, 1];
echo doesValidArrayExist($derived2) ? 'true' : 'false'; // Output: true

// Example 3
$derived3 = [1, 0];
echo doesValidArrayExist($derived3) ? 'true' : 'false'; // Output: false
?></code>

2683. Benachbartes bitweises XOR

Schwierigkeit:Mittel

Themen:Array, Bit-Manipulation

Wir erhalten ein 0-indiziertes Array derived der Länge n, das durch Berechnen des bitweisen XOR (⊕) benachbarter Werte in einem binären Array original (ebenfalls der Länge n) erstellt wurde. Die Regel lautet:

• Wenn i = n - 1, dann derived[i] = original[i] ⊕ original[0].
• Sonst derived[i] = original[i] ⊕ original[i 1].

Unsere Aufgabe besteht darin, festzustellen, ob ein gültiges binäres Array original existiert, das das angegebene derived-Array erzeugen könnte. Geben Sie true zurück, wenn ein solches Array vorhanden ist, andernfalls false. Ein binäres Array enthält nur Nullen und Einsen.

Beispiel 1:

• Eingabe: derived = [1,1,0]
• Ausgabe: true
• Erklärung: Ein gültiges original-Array ist [0,1,0].
  • derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1
  • derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
  • derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0

Beispiel 2:

• Eingabe: derived = [1,1]
• Ausgabe: true
• Erklärung: Ein gültiges original-Array ist [0,1].

Beispiel 3:

• Eingabe: derived = [1,0]
• Ausgabe: false
• Erklärung:Kein gültiges originalArray vorhanden.

Einschränkungen:

• n == derived.length
• 1 <= n <= 10^5
• Die Werte in derived sind entweder 0 oder 1.

Hinweis: Die XOR-Summe des derived-Arrays sollte 0 sein.

Lösung (PHP):

Die wichtigste Beobachtung ist, dass die XOR-Summe des derived-Arrays immer 0 ist, wenn ein gültiges original-Array vorhanden ist. Dies liegt daran, dass jedes Element von original an genau zwei XOR-Operationen beteiligt ist (außer in Randfällen, in denen das erste und das letzte Element XOR-verknüpft werden, aber selbst dann wird es aufgehoben).

<?php
function doesValidArrayExist(array $derived): bool {
    $xorSum = 0;
    foreach ($derived as $val) {
        $xorSum ^= $val;
    }
    return $xorSum === 0;
}

// Test cases
$derived1 = [1, 1, 0];
echo doesValidArrayExist($derived1) ? "true\n" : "false\n"; // true

$derived2 = [1, 1];
echo doesValidArrayExist($derived2) ? "true\n" : "false\n"; // true

$derived3 = [1, 0];
echo doesValidArrayExist($derived3) ? "true\n" : "false\n"; // false

$derived4 = [1,0,1,0,1];
echo doesValidArrayExist($derived4) ? "true\n" : "false\n"; //true

$derived5 = [1,0,1,0,0];
echo doesValidArrayExist($derived5) ? "true\n" : "false\n"; //false

?>
Diese Lösung hat eine zeitliche Komplexität von O(n) und eine räumliche Komplexität von O(1).  Es bestimmt effizient die Existenz eines gültigen original-Arrays, ohne dass es rekonstruiert werden muss.

Das obige ist der detaillierte Inhalt vonBenachbartes bitweises XOR. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!