<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中文網其他相關文章!