目标
下标从 0 开始、长度为 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 ，请判断是否存在一个能够派生得到 derived 的 有效原始二进制数组 original 。
如果存在满足要求的原始二进制数组，返回 true ；否则，返回 false 。
- 二进制数组是仅由 0 和 1 组成的数组。
示例 1：
输入：derived = [1,1,0]
输出：true
解释：能够派生得到 [1,1,0] 的有效原始二进制数组是 [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
解释：能够派生得到 [1,1] 的有效原始二进制数组是 [0,1] ：
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1示例 3：
输入：derived = [1,0]
输出：false
解释：不存在能够派生得到 [1,0] 的有效原始二进制数组。说明：
- n == derived.length
- 1 <= n <= 10^5
- derived 中的值不是 0 就是 1 。
思路
给定一个 二进制 数组 derived，判断它是否是某个 循环二进制 数组相邻元素按位异或的结果。
可以假定原数组第一个元素是 1，根据 derived 数组可以推出其余元素 original[i + 1] = derived[i] ^ original[i]。当得到 original[n - 1] 时，只需验证 original[n - 1] ^ original[0] == derived[n - 1]。
代码
/**
* @date 2025-07-31 8:45
*/
public class DoesValidArrayExist2683 {
public boolean doesValidArrayExist(int[] derived) {
int n = derived.length;
int first = 1;
int prev = first;
for (int i = 1; i < n; i++) {
prev ^= derived[i - 1];
}
return (prev ^ first) == derived[n - 1];
}
}
性能
