<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>
难度:中等
主题:数组、位操作
我们得到一个长度为 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中文网其他相关文章!