2683. 相邻值的按位异或

Problem: 2683. 相邻值的按位异或

思路

1. 假设数组第一个元素为 0 或 1。
2. 根据 derived 数组的定义，依次推导原始数组 original 的其他元素。例如：

• 如果 derived[0] = original[0] ^ original[1]，那么 original[1] = original[0] ^ derived[0]。
• 得出original[i] = original[i - 1] ^ drived [i - 1]。
• 以此类推，直到推导出 original 的所有元素。

3. 验证最后一个元素：

• 根据 derived 数组的最后一个元素的定义（derived[n - 1] = original[n - 1] ^ original[0]），验证推导出的 original 数组是否满足这个条件。

复杂度

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$

Code

class Solution {
public:bool doesValidArrayExist(vector<int>& derived) {int n = derived.size();// 假设数组第一个数为0vector<int> original(n, 0);for (int i = 1; i < n; i++) {original[i] = derived[i - 1] ^ original[i - 1];}if ((original.back() ^ original[0]) == derived.back()) {return true;}// 假设第一个数为1original.assign(n, 1);for (int i = 1; i < n; i++) {original[i] = derived[i - 1] ^ original[i - 1];}return (original.back() ^ original[0]) == derived.back();}
};