相邻位异或

<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. 相邻位异或

难度：中等

主题：数组、位操作

我们得到一个长度为 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 <= n <= 10^5
• 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中文网其他相关文章！