相鄰位異或

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

2683. 相鄰位異或

難度：中

主題：陣列、位元操作

我們得到一個長度為 derived 的 0 索引數組 n，透過計算二進位數組 original（長度也是 n）中相鄰值的位元異或 (⊕) 來建立。 規則是：

• 如果i = n - 1，則derived[i] = original[i] ⊕ original[0]。
• 否則，derived[i] = original[i] ⊕ original[i 1]。

我們的任務是確定是否存在可以產生給定 original 陣列的有效二進位陣列 derived。 如果存在這樣的數組，則傳回 true，否則傳回 false。 二進制數組僅包含 0 和 1。

範例1：

• 輸入： derived = [1,1,0]
• 輸出： true
• 解釋： 有效的 original 陣列是 [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

範例2：

• 輸入： derived = [1,1]
• 輸出： true
• 解釋： 有效的 original 陣列是 [0,1]。

範例 3：

• 輸入： derived = [1,0]
• 輸出： false
• 解釋： 不存在有效的 original 陣列。

約束：

• n == derived.length
• 1
• derived 中的值為 0 或 1。

提示： derived 陣列的異或和應為 0。

解（PHP）：

關鍵的觀察是，如果存在有效的 derived 數組，則 original 數組的異或和將始終為 0。 這是因為 original 的每個元素都涉及兩次 XOR 運算（除了第一個和最後一個元素進行 XOR 運算的邊緣情況，但即使這樣它也會抵消）。

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

?>

此解的時間複雜度為 O(n)，空間複雜度為 O(1)。 它可以有效地確定有效 original 數組是否存在，而無需重建它。

以上是相鄰位異或的詳細內容。更多資訊請關注PHP中文網其他相關文章！