原创 2021-11-30 19:25:17

题目描述

未知 整数数组 arr 由 n 个非负整数组成。

经编码后变为长度为 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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/decode-xored-array

答案解析

异或运算有如下特性:

  • 异或运算满足交换律和结合律。
  • 任何整数和自身做异或运算结果都是0。即X ^ X = 0;
  • 任意整数与0做异或运算,结果都是其自身。即 X ^ 0 = 0 ^ X = X;

根据其运算特性可知:

encoded[i - 1] = arr[i - 1] ^ arr[i];
两边同时对 arr[i - 1]做异或运算。
encoded[i - 1] ^ arr[i - 1]= arr[i - 1] ^ arr[i] ^ arr[i-1];
根据以上规律可得
encoded[i - 1] ^ arr[i - 1] = arr[i];
即: arr[i] = encoded[i - 1] ^ arr[i - 1];
class Solution {
    public int[] decode(int[] encoded, int first) {
        int n = encoded.length + 1;
        int[] arr = new int[n];
        arr[0] = first;
        for (int i = 1; i < n; i++) {
            arr[i] = arr[i - 1] ^ encoded[i - 1];
        }
        return arr;
    }
}
取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

分享从这里开始,精彩与您同在

延伸阅读
  1. leetCode第1480题(一维数组的动态和)
  2. leetCode第2011题(执行操作后的变量值)
  3. leetCode第1863题 找出所有子集的异或总和再求和
  4. 算法:0移动问题
发表评论