佛山企业网站建设公司,建设信用卡积分兑换商城网站,跨境电商商城源码,wordpress自动发邮件给你一个长度为 n 的 整数 数组 pref 。找出并返回满足下述条件且长度为 n 的数组 arr #xff1a;
pref[i] arr[0] ^ arr[1] ^ … ^ arr[i]. 注意 ^ 表示 按位异或#xff08;bitwise-xor#xff09;运算。
可以证明答案是 唯一 的。
示例 1#xff1a;
输入#xf…给你一个长度为 n 的 整数 数组 pref 。找出并返回满足下述条件且长度为 n 的数组 arr
pref[i] arr[0] ^ arr[1] ^ … ^ arr[i]. 注意 ^ 表示 按位异或bitwise-xor运算。
可以证明答案是 唯一 的。
示例 1
输入pref [5,2,0,3,1] 输出[5,7,2,3,2] 解释从数组 [5,7,2,3,2] 可以得到如下结果
pref[0] 5pref[1] 5 ^ 7 2pref[2] 5 ^ 7 ^ 2 0pref[3] 5 ^ 7 ^ 2 ^ 3 3pref[4] 5 ^ 7 ^ 2 ^ 3 ^ 2 1 示例 2
输入pref [13] 输出[13] 解释pref[0] arr[0] 13
提示
1 pref.length 105 0 pref[i] 106
根据题意我们得到以下公式 pref[i - 1] arr[0] ^ arr[1] ^ … ^ arr[i - 1] pref[i] arr[0] ^ arr[1] ^ … ^ arr[i] pref[i - 1] ^ arr[i]
如果a ^ b c则b a ^ ca b ^ c因此arr[i] pref[i] ^ pref[i - 1]直接模拟即可
class Solution {
public:vectorint findArray(vectorint pref) { vector int res(1, pref[0]);for (int i 1; i pref.size(); i){res.push_back(pref[i - 1] ^ pref[i]);}return res;}
};如果pref的长度为n则此算法时间复杂度为O(n)空间复杂度为O(1)。
