推 Furina: 大師 01/17 10:28
推 Meaverzt: 大師 01/17 13:40
https://leetcode.com/problems/neighboring-bitwise-xor
2683. Neighboring Bitwise XOR
給定一長度為n的陣列derived
此陣列為長度為n的二進位陣列original的相鄰元素經由xor運算的結果
運算規則如下:
if index == n-1:
derived[i] = original[i] ^ original[0]
else:
derived[i] = original[i] ^ original[i+1]
請判斷是否存在有效的original
Example 1:
Input: derived = [1,1,0]
Output: true
Explanation: A valid original array that gives derived is [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
Example 2:
Input: derived = [1,1]
Output: true
Explanation: A valid original array that gives derived is [0,1].
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1
Example 3:
Input: derived = [1,0]
Output: false
Explanation: There is no valid original array that gives derived.
Constraints:
n == derived.length
1 <= n <= 105
The values in derived are either 0's or 1's
思路:
以例二為例
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1
derived[0] ^ derived[1] =
original[0] ⊕ original[1] ^ original[1] ⊕ original[0]
相同元素的xor會抵消 所以結果必為零
我們只要檢查derived所有元素的xor是不是0就有答案了
Python Code:
class Solution:
def doesValidArrayExist(self, derived: List[int]) -> bool:
result = 0
for n in derived:
result ^= n
if result == 1:
return False
else:
return True
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.179.129 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1737080296.A.69B.html