Skip to main content

1720. 解码异或后的数组

caution

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

思路​

这里主要用了异或的性质。

  1. 两个相同的数做异或结果为 0
  2. 0 与 任何数异或都是他本身
  3. 满足交换律

对于原式 encoded[i] = arr[i] ^ arr[i + 1]，两边同时异或 arr[i] 得：

arr[i] ^ encoded[i] = arr[i] ^ arr[i + 1] ^ arr[i]

运用性质 3，交换 arr[i] 和 arr[i + 1] 得：

arr[i] ^ encoded[i] = arr[i + 1] ^ arr[i] ^ arr[i]

运用性质 1，得：

arr[i] ^ encoded[i] = arr[i + 1] ^ 0

运用性质 2，得：

arr[i] ^ encoded[i] = arr[i + 1]

即 arr[i + 1] = arr[i] ^ encoded[i]

代码​

class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        vector<int> res;
        res.push_back(first);
        for (int i = 1; i <= encoded.size(); i++) {
            res.push_back(res[i - 1] ^ encoded[i - 1]);
        }
        return res;
    }
};