今日题目

https://leetcode.com/problems/neighboring-bitwise-xor/description/

解题思路

  • 根据昨日题目中的结论，我们知道 $a\space xor\space a = 0$。
  • 因此，$\large{XOR}_{i=0}^{n} \small derived[i]$ 的结果必然为 0，因为所有 $original$ 的偏移量相互抵消。其中 n 表示序列的最后一个下标。
  • 接下来证明：当 $\large{XOR}_{i=0}^{n} \small derived[i] = 0$ 时，我们可以还原出完整的 $original$ 序列。
  • 令 $original[0]=0$，$original[k] = original[k-1]\space xor\space derived[k]$。
  • 现在只需证明 $original[n]\space xor\space original[0]=derived[n]$，即 $original[0] = original[n]\space xor\space derived[n]$。
  • 根据上述递推公式，$original[n] = \large{XOR}_{i=0}^{n-1} \small derived[i]\space xor\space original[0]$
  • 因为 $\large{XOR}_{i=1}^{n} \small derived[i] = 0$，
  • 所以 $original[n]\space xor\space derived[n] = original[0]\space xor\space \large{XOR}_{i=0}^{n} \small derived[i] = 0 = original[0]$。
  • 因此，该 $original$ 序列是合法的。

技巧

  • 现在我们只需判断序列的异或和是否为 0。由于这是一个二进制序列，可以将所有 0 和 1 分别归组，对全部元素做异或运算后，结果等价于 1 的个数的奇偶性。若 1 的个数为奇数，结果为 1；否则为 0。
  • 因此，最简单的解法就是对序列求和，再判断其奇偶性。

方法

对序列所有元素求和，判断结果是奇数还是偶数。

复杂度

  • 时间复杂度：$O(N)$，N 为序列长度。

  • 空间复杂度：$O(1)$，无需额外存储变量。

代码

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        return (sum(derived) & 1) == 0

image.png