Medium

题目描述

长度为 n 的数组 derived 是通过对长度为 n 的二进制数组 original 中相邻值进行按位异或 (⊕) 运算得出的。

具体来说，对于范围 [0, n - 1] 中的每个索引 i：

  • 如果 i = n - 1，则 derived[i] = original[i] ⊕ original[0]
  • 否则，derived[i] = original[i] ⊕ original[i + 1]

给定数组 derived，你的任务是判断是否存在一个有效的二进制数组 original 可以形成 derived。

如果存在这样的数组，返回 true，否则返回 false。

注意： 二进制数组是仅包含 0 和 1 的数组。

示例 1：

输入：derived = [1,1,0]
输出：true
解释：能够生成 derived 的有效 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
解释：能够生成 derived 的有效 original 数组是 [0,1]。
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1

示例 3：

输入：derived = [1,0]
输出：false
解释：不存在能够生成 derived 的有效 original 数组。

约束条件：

  • n == derived.length
  • 1 <= n <= 10^5
  • derived 中的值只有 0 和 1

解题思路

这道题的关键在于理解异或运算的性质和循环数组的特点。

核心观察：

  1. 每个 original[i] 都会在 derived 数组中出现恰好两次（除了边界情况）
  2. original[0] 在 derived[n-1] 和 derived[0] 中各出现一次
  3. original[i] (i≠0) 在 derived[i-1] 和 derived[i] 中各出现一次

数学推导： 由于异或运算满足交换律和结合律，我们可以将所有 derived[i] 异或起来：

  • derived[0] ⊕ derived[1] ⊕ ... ⊕ derived[n-1]
  • = (original[0] ⊕ original[1]) ⊕ (original[1] ⊕ original[2]) ⊕ ... ⊕ (original[n-1] ⊕ original[0])

重新组合后，每个 original[i] 都出现了恰好两次，根据异或的性质 x ⊕ x = 0，所以整个表达式的结果应该为 0。

判断条件： 如果 derived 数组所有元素的异或结果为 0，则存在有效的 original 数组；否则不存在。

验证方法： 我们还可以通过假设 original[0] = 0，然后依次推导出其他元素来验证这个结论。

代码实现

class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        int xor_sum = 0;
        for (int x : derived) {
            xor_sum ^= x;
        }
        return xor_sum == 0;
    }
};

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        xor_sum = 0
        for x in derived:
            xor_sum ^= x
        return xor_sum == 0

public class Solution {
    public bool DoesValidArrayExist(int[] derived) {
        int xorSum = 0;
        foreach (int x in derived) {
            xorSum ^= x;
        }
        return xorSum == 0;
    }
}

/**
 * @param {number[]} derived
 * @return {boolean}
 */
var doesValidArrayExist = function(derived) {
    let xor = 0;
    for (let i = 0; i < derived.length; i++) {
        xor ^= derived[i];
    }
    return xor === 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)

相关题目