解码异或后的数组

发表于
本文字数： 769 阅读时长 ≈ 1 分钟

LeetCode题目，5649. Decode XORed Array

先看题目描述

sluetP.png

大意就是有一个数组 arr 由 n 个整数构成，将 arr 编码后得到长度为 n - 1 的 encoded 数组，编码规则为 encoded[i] = arr[i] XOR arr[i+1]，现在给定编码后得到的 encoded 数组和 arr 数组的第一个元素 first，让我们求出 arr 数组并返回

算法和思路

这题一开始不知道怎么做，后来在草稿纸上试了下，发现了异或的性质，才意识到这题确实很简单

首先异或的计算规则是两数相同得 0，不同得 1。异或还存在如下性质：

  • 异或存在结合律和交换律
  • a ^ a = 0
  • a ^ 0 = a
  • 由前三个性质，可以推出若 a ^ b = c，则有 a ^ c = b

最后一个性质的推导如下：若 a ^ b = c，则 a ^ c = a ^ (a ^ b) = (a ^ a) ^ b = 0 ^ b = b

只要发现了异或的最后这个性质，这题就迎刃而解了

算法源码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int[] decode(int[] encoded, int first) {
        int len = encoded.length;
        int[] res = new int[len + 1];
        res[0] = first;
        for (int i = 0; i < len; i++) {
            res[i + 1] = res[i] ^ encoded[i];
        }
        return res;
    }
}