2683. 相邻值的按位异或

🟠   🔖  位运算 数组  🔗 力扣 LeetCode

题目

A 0-indexed array derived with length n is derived by computing the bitwise XOR (⊕) of adjacent values in a binary array original of length n.

Specifically, for each index i in the range [0, n - 1]:

• If i = n - 1, then derived[i] = original[i] ⊕ original[0].
• Otherwise, derived[i] = original[i] ⊕ original[i + 1].

Given an array derived, your task is to determine whether there exists a valid binary array original that could have formed derived.

Return true if such an array exists or false otherwise.

• A binary array is an array containing only 0 's and 1 's

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 <= 10^5
• The values in derived are either 0 's or 1 's

题目大意

下标从 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 。

解题思路

题目考察的是一个数组是否可以通过异或操作还原成有效的原始数组。关键点在于：

1. 异或的性质：
   • a ^ b = c，那么 b = a ^ c。
   • 因此，异或操作具有可逆性。
2. 原始数组的有效性：
   • 如果能形成一个循环的异或关系（即首尾元素连接后满足规则），那么原始数组是有效的。

由于数组是循环的，可以通过假设 original[0] 的初值为 0 或 1 两种情况进行模拟：

1. 假设 1：original[0] = 0：
   • 根据公式 derived[i] = original[i] ^ original[i + 1] 推算整个数组。
   • 判断推导出的 original 是否有效（即形成闭环，满足 original[n] = original[0]）。
2. 假设 2：original[0] = 1：
   • 同样推导数组并判断闭环条件。

如果任一假设成立，则返回 true；否则返回 false。

• 用两个变量 case1 和 case2 表示假设 original[0] = 0 和 original[0] = 1 的推导结果。
• 遍历 derived 数组，用异或公式更新 case1 和 case2。
• 判断最终结果是否满足闭环条件。

复杂度分析

• 时间复杂度：O(n)，只需遍历一次 derived。
• 空间复杂度：O(1)，使用常量空间。

代码

/**
 * @param {number[]} derived
 * @return {boolean}
 */
var doesValidArrayExist = function (derived) {
	let case1 = 0, // 假设 original[0] = 0
		case2 = 1; // 假设 original[0] = 1
	for (let num of derived) {
		case1 = num ^ case1;
		case2 = num ^ case2;
	}
	// 如果任一闭环成立，返回 true
	return case1 === 0 || case2 === 1;
};

相关题目

题号	标题	题解	标签	难度	力扣
3173	相邻元素的按位或 🔒		位运算 数组	🟢	🀄️ 🔗