找出前缀异或的原始数组

简介: 找出前缀异或的原始数组

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。

题目描述

给你一个长度为 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,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。

目录
相关文章
|
3月前
|
C语言
用栈实现将一个十进制数值转换成八进制数值。即用该十进制数值除以8,并保留其余数;重复此操作,直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的八进制数值
这篇文章展示了如何使用栈(包括顺序栈和链栈)实现将十进制数值转换成八进制数值的方法,通过C语言编程演示了两种栈的实现方式和使用场景。
用栈实现将一个十进制数值转换成八进制数值。即用该十进制数值除以8,并保留其余数;重复此操作,直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的八进制数值
|
6月前
|
索引
Leetcode 给定一个数组,给定一个数字。返回数组中可以相加得到指定数字的两个索引
Leetcode 给定一个数组,给定一个数字。返回数组中可以相加得到指定数字的两个索引
|
存储 算法
算法之字符串问题(第415题字符串相加、第43题字符串相乘、第316题去除重复字母)
算法之字符串问题(第415题字符串相加、第43题字符串相乘、第316题去除重复字母)
74 0
|
存储 算法 C语言
【前缀和】1829. 每个查询的最大异或值
【前缀和】1829. 每个查询的最大异或值
99 0
题目:下列给定程序中函数fun的功能是:从p所指字符串中找出ASCII码值最大的字符,将其放在第一个位置上,并将该字符前的原字符向后顺序移动。
题目:下列给定程序中函数fun的功能是:从p所指字符串中找出ASCII码值最大的字符,将其放在第一个位置上,并将该字符前的原字符向后顺序移动。
|
存储 算法 JavaScript
设计并实现一个函数, 功能为给定一个存储为随机整数的数组,从中删除所有值为i的整数
设计并实现一个函数, 功能为给定一个存储为随机整数的数组,从中删除所有值为i的整数
定义一个长度为10的整型数组,循环输入10个整数。 然后将输入一个整数,查找此整数,找到后输出下标,没找到给出提示。
定义一个长度为10的整型数组,循环输入10个整数。 然后将输入一个整数,查找此整数,找到后输出下标,没找到给出提示。
215 0
定义一个包含10个整数元素的数组,初始值由用户给定。找出数组中的最大数并连同下标一起输出。
定义一个包含10个整数元素的数组,初始值由用户给定。找出数组中的最大数并连同下标一起输出。
219 0
数组与矩阵——3.数组中重复的数字
数组与矩阵——3.数组中重复的数字
|
JSON 数据格式
将字符串按指定的符号分割为集合或数组
将字符串按指定的符号分割为集合或数组
189 0
将字符串按指定的符号分割为集合或数组