专栏首页江涛的博客leetcode - 解码异或后的数组

leetcode - 解码异或后的数组

题意

未知 整数数组 arrn 个非负整数组成。

经编码后变为长度为 n - 1 的另一个整数数组 encoded,其中 encoded[i] = arr[i] XOR arr[i + 1]。例如,arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3]

给你编码后的数组 encoded 和原数组 arr 的第一个元素 first(arr[0])

请解码返回原数组 arr 。可以证明答案存在并且是唯一的。

示例

示例 1:

输入:encoded = [1,2,3], first = 1
输出:[1,0,2,1]
解释:若 arr = [1,0,2,1] ,那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

示例 2:

输入:encoded = [6,2,7,3], first = 4
输出:[4,2,0,7,4]

提示

  • 2 <= n <= 104
  • encoded.length == n - 1
  • 0 <= encoded[i] <= 105
  • 0 <= first <= 105

出处

链接:https://leetcode-cn.com/problems/decode-xored-array

思路

这题考的是异或的交换律,会这题就是送分。简单的说 a ^ b = c, 那么a ^ c = b也是成立的。所以这题我们知道 first,倒推回去也很简单。

代码

/**
 * @param {number[]} encoded
 * @param {number} first
 * @return {number[]}
 */
const decode = function (encoded, first) {
  const arr = [first];
  for (let i = 0; i < encoded.length; i++) {
    const res = encoded[i] ^ arr[i];
    arr.push(res);
  }
  return arr;
};

export default decode;

测试

import decode from '../../code/leetcode/1720';

describe('test function decode: ', () => {
  test('test case encoded = [1,2,3], first = 1', () => {
    const res = decode([1, 2, 3], 1);
    expect(res).toEqual([1, 0, 2, 1]);
  });

  test('test case encoded = [6,2,7,3], first = 4', () => {
    const res = decode([6, 2, 7, 3], 4);
    expect(res).toEqual([4, 2, 0, 7, 4]);
  });
});

说明

本文首发于 GitHub 仓库https://github.com/ataola/coding,线上阅读地址:https://zhengjiangtao.cn/coding/,转载请注明出处,谢谢!

本文分享自微信公众号 - 前端路桥(ataola),作者:丰臣正一

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-01-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 1720. 解码异或后的数组(位运算)

    经编码后变为长度为 n - 1 的另一个整数数组 encoded ,其中 encoded[i] = arr[i] XOR arr[i + 1] 。 例如,ar...

    Michael阿明
  • 一起玩转算法:解码异或后的数组

    经编码后变为长度为 n - 1 的另一个整数数组 encoded ,其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如,arr ...

    Rouse
  • LeetCode 1734. 解码异或后的排列(位运算)

    它被加密成另一个长度为 n - 1 的整数数组 encoded , 满足 encoded[i] = perm[i] XOR perm[i + 1] 。 比方...

    Michael阿明
  • LeetCode 1486. 数组异或操作

    数组 nums 定义为:nums[i] = start + 2*i(下标从 0 开始)且 n == nums.length 。

    Michael阿明
  • LeetCode 1310. 子数组异或查询(前缀异或)

    有一个正整数数组 arr,现给你一个对应的查询数组 queries,其中 queries[i] = [Li, Ri]。

    Michael阿明
  • LeetCode 1442. 形成两个异或相等数组的三元组数目(前缀异或)

    现需要从数组中取三个下标 i、j 和 k ,其中 (0 <= i < j <= k < arr.length) 。

    Michael阿明
  • 图解 LeetCode 第 421 题:数组中两个数的最大异或值

    今天分享的题目来源于 LeetCode 第 421 号问题:数组中两个数的最大异或值。在 异或 这个知识点里面属于一个中高难度的题目。

    五分钟学算法
  • LeetCode 每日一题 1486. 数组异或操作

    数组 nums 定义为:nums[i] = start + 2*i(下标从 0 开始)且 n == nums.length 。

    村雨遥
  • LeetCode 1442. 形成两个异或相等数组的三元组数目

    遍历数组中的每个元素,从这个元素为起点,只要找到一段区间 i,k 的 xor 为 0,则区间中的任意一个位置都可以作为 j(j≠i,k)

    Yano_nankai
  • LeetCode 421. 数组中两个数的最大异或值(Trie树)

    给定一个非空数组,数组中元素为 a0, a1, a2, … , an-1,其中 0 ≤ ai < 231 。

    Michael阿明
  • LeetCode 1707. 与数组中元素的最大异或值(Trie树)

    给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ,其中 queries[i] = [xi, mi] 。

    Michael阿明
  • LeetCode 476. 数字的补数(移位 异或^)

    Michael阿明
  • 【LeetCode每日一题】1442. 形成两个异或相等数组的三元组数目

    现需要从数组中取三个下标 i、j 和 k ,其中 (0 <= i < j <= k < arr.length) 。

    公众号guangcity
  • 2021-05-13:数组中所有数都异或起来的结果,叫做异或和。给定一个数组arr,返回arr的最大子数组异或和。

    2021-05-13:数组中所有数都异或起来的结果,叫做异或和。给定一个数组arr,返回arr的最大子数组异或和。

    福大大架构师每日一题
  • 【LeetCode每日一题】1707. 与数组中元素的最大异或值

    给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ,其中 queries[i] = [xi, mi] 。

    公众号guangcity
  • LeetCode 136. 只出现一次的数字(异或^)

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

    Michael阿明
  • LeetCode 1879. 两个数组最小的异或值之和(状态压缩DP)

    两个数组的 异或值之和 为 (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n...

    Michael阿明
  • 给定一个数组,求子数组的最大异或和

     直接说这道题时间复杂度O(n)的做法,构建前缀树。假设将0-0、0-1、0-2、...、0-i-1的异或结果全部装在前缀树中,那么以i结尾的最大异或和就是0到...

    mathor
  • 给定一个数组,求子数组的最大异或和

    大学里的混子

扫码关注云+社区

领取腾讯云代金券