说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。
题目描述
给你一个长度为 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] = 5 - pref[1] = 5 ^ 7 = 2 - pref[2] = 5 ^ 7 ^ 2 = 0 - pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3 - pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1
示例 2:
输入:pref = [13] 输出:[13] 解释:pref[0] = arr[0] = 13
提示:
- 1 <= pref.length <= 10^5
- 0 <= pref[i] <= 10^6
思路分析
首先我们要先理解一下题目的意思,题目会给我们一个数组pref,数组中的每一个元素pref[i] = arr[0] ^ arr[1] ^ … ^ arr[i], ^ 表示 按位异或(bitwise-xor)运算。
按位异或:如果两个相应的二进制位值不同则为1,否则为0
如果两个相应 bit 位相同,则结果为 0,否则为 1。 即: 0^0 = 0, 1^0 = 1, 0^1 = 1, 1^1 = 0
异或运算的性质
a ^ b = c 那么a = c ^ b ,因为c^b = (a^b)^b = a^(b^b) = a^0 = a; 所以 res[i] = pref[i-1] ^ pref[i];
知道了这个性质之后,我们就可以很快写出代码了。
完整AC代码如下:
AC代码
/** * @param {number[]} pref * @return {number[]} */ var findArray = function(pref) { let res = [pref[0]]; for(let i = 1; i < pref.length; i++){ res.push(pref[i - 1] ^ pref[i]); } return res; };
公众号
关注公众号『前端也能这么有趣
』,获取更多有趣内容。
说在后面
🎉 这里是 JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『
前端也能这么有趣
』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。