LeetCode 异或题

青旅半醒 2023-01-20 02:58 49阅读 0赞

首先介绍一下异或运算：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70]  
异或的一些性质：  
`x XOR y = z`，那么 `x = y XOR z`。  
`x XOR x = 0`  
`x XOR 0 = x`

[1720. 解码异或后的数组][1720.]

未知 整数数组 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\]

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

[1734. 解码异或后的排列][1734.]

给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个 奇数 。

它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded\[i\] = perm\[i\] XOR perm\[i + 1\] 。比方说，如果 perm = \[1,3,2\] ，那么 encoded = \[2,1\] 。

给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。

示例 1：

> 输入：encoded = \[3,1\]  
> 输出：\[1,2,3\]  
> 解释：如果 perm = \[1,2,3\] ，那么 encoded = \[1 XOR 2,2 XOR 3\] = \[3,1\]

示例 2：

> 输入：encoded = \[6,5,4,6\]  
> 输出：\[2,4,1,5,3\]

我们发现这题与上一题不同之处在于我们不知道原本数据perm第一个数是什么，但是题目说perm是前n个正整数的排列，因此我们希望通过这个条件和编码后的encoded数组来反推出perm\[0\]

举个例子：  
假设原本数组 perm = \[A, B, C, D, E\]  
那么编码后数组 encoded = \[AB, BC, CD, DE\]

perm数组中所有元素异或记为 A^B^C^D^E (ABCDE)  
encoded数组中奇数元素异或为 B^C^D^E (BCDE)  
那么A = ABCDE ^ BCDE

class Solution {
        
    public:
        vector<int> decode(vector<int>& encoded) {
        
            int n = encoded.size(); // 得到编码后的长度
            vector<int> perm(n + 1); // 定义原本的整数数组perm
            int ABCDE = 0; // 初始化，这个变量用于存放perm中所有数值进行异或的结果
            for (int i = 1; i <= n + 1; i++) // perm中所有数值进行异或 
                ABCDE ^= i;
            int BCDE = 0; // 为了得到perm的第一个数值，需要初始化一个“BCDE”
            for (int i = 1; i < n; i += 2) //  “BCDE”的求值，就是encoded中从1开始，步长为2地取值进行异或的结果 
                BCDE ^= encoded[i];
            perm[0] = ABCDE ^ BCDE;  // 得到第一个数A
            for (int i = 1; i <= n; i++) 
                perm[i] = perm[i - 1] ^ encoded[i - 1]; // 此时，本题转换为力扣1720
            return perm;
        }
    };

[1310. 子数组异或查询][1310.]

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

对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr\[Li\] xor arr\[Li+1\] xor … xor arr\[Ri\]）作为本次查询的结果。

并返回一个包含给定查询 queries 所有结果的数组。

示例 1：

> 输入：arr = \[1,3,4,8\], queries = \[\[0,1\],\[1,2\],\[0,3\],\[3,3\]\]  
> 输出：\[2,7,14,8\]  
> 解释：  
> 数组中元素的二进制表示形式是：  
> 1 = 0001  
> 3 = 0011  
> 4 = 0100  
> 8 = 1000  
> 查询的 XOR 值为：  
> \[0,1\] = 1 xor 3 = 2  
> \[1,2\] = 3 xor 4 = 7  
> \[0,3\] = 1 xor 3 xor 4 xor 8 = 14  
> \[3,3\] = 8

class Solution {
        
    public:
        // 暴力肯定超时，所以使用类似于连续子数组和计算前缀和的方法，先计算前缀异或，然后根据查询值算结果。
        vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        
            int n = arr.size();
            vector<int> dp(n+1, 0);
            for(int i=1; i<=n; ++i){
        
                dp[i] = dp[i-1]^arr[i-1];
            }
        
            vector<int> res;
            for(int i=0; i<queries.size(); ++i){
        
                vector<int> u = queries[i];
                res.push_back(dp[u[1]+1]^dp[u[0]]);
            }
            return res;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2thcnJ5X3p6ag_size_16_color_FFFFFF_t_70]: /images/20221021/d1915f2891f444ab9dc5c07590b50c2f.png
[1720.]: https://leetcode-cn.com/problems/decode-xored-array/
[1734.]: https://leetcode-cn.com/problems/decode-xored-permutation/
[1310.]: https://leetcode-cn.com/problems/xor-queries-of-a-subarray/