Jiran Bitwise 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. Jiran Bitwise XOR

Kesukaran: Sederhana

Topik: Tatasusunan, Manipulasi Bit

Kami diberi tatasusunan 0-indeks derived panjang n, dicipta dengan mengira XOR bitwise (⊕) nilai bersebelahan dalam tatasusunan binari original (juga panjang n). Peraturannya ialah:

• Jika i = n - 1, maka derived[i] = original[i] ⊕ original[0].
• Jika tidak, derived[i] = original[i] ⊕ original[i 1].

Tugas kami ialah untuk menentukan sama ada tatasusunan binari yang sah original wujud yang boleh menghasilkan tatasusunan derived yang diberikan. Kembalikan true jika tatasusunan sedemikian wujud, false sebaliknya. Tatasusunan binari hanya mengandungi 0s dan 1s.

Contoh 1:

• Input: derived = [1,1,0]
• Output: true
• Penjelasan: Tatasusunan original yang sah ialah [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

Contoh 2:

• Input: derived = [1,1]
• Output: true
• Penjelasan: Tatasusunan original yang sah ialah [0,1].

Contoh 3:

• Input: derived = [1,0]
• Output: false
• Penjelasan: Tiada tatasusunan original yang sah wujud.

Kekangan:

• n == derived.length
• 1 <= n <= 10^5
• Nilai dalam derived sama ada 0s atau 1s.

Petunjuk: Jumlah XOR bagi tatasusunan derived hendaklah 0.

Penyelesaian (PHP):

Pemerhatian utama ialah jumlah XOR bagi tatasusunan derived akan sentiasa 0 jika tatasusunan original yang sah wujud. Ini kerana setiap elemen original terlibat dalam dua operasi XOR (kecuali dalam kes tepi di mana elemen pertama dan terakhir di-XOR, tetapi walaupun begitu ia membatalkannya).

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

?>
Penyelesaian ini mempunyai kerumitan masa O(n) dan kerumitan ruang O(1).  Ia cekap menentukan kewujudan tatasusunan original yang sah tanpa perlu membinanya semula.

Atas ialah kandungan terperinci Jiran Bitwise XOR. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!