Vison's Blog
所有文章
文章总览
编辑器
Publications
About Me
Search
目录
#toc-container
下载Markdown文件
【5.7】LeetCode每日一题·数组异或操作
2021年05月07日 12时10分
标签：
LeetCode
数组
模拟
数学
## 题目描述 给你两个整数，n 和 start 。 数组`nums`定义为：`nums[i] = start + 2*i`（下标从`0`开始）且`n == nums.length`。 请返回`nums`中所有元素按位异或（**XOR**）后得到的结果。 #### 示例1 ``` 输入：n = 5, start = 0 输出：8 解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。 "^" 为按位异或 XOR 运算符。 ``` #### 示例2 ``` 输入：n = 4, start = 3 输出：8 解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8. ``` #### 示例3 ``` 输入：n = 1, start = 7 输出：7 ``` #### 示例4 ``` 输入：n = 10, start = 5 输出：2 ``` #### 提示 ``` 1 <= n <= 1000 0 <= start <= 1000 n == nums.length ``` #### 来源 > 来源：力扣（LeetCode） > 链接：[题目链接](https://leetcode-cn.com/problems/xor-operation-in-an-array) ## 解题思路 ### 暴力模拟 由于`0^0 = 0, 0^1 = 1`，即`0^x = x`，所以设答案初始值为0，然后每循环一次，就将`res`异或上`nums`数组的一个元素即可。 #### 代码 ```cpp class Solution { public: vector<int> decode(vector<int>& encoded, int first) { vector<int> res; res.emplace_back(first); for(int i = 0; i < encoded.size(); i++){ res.emplace_back(res[i]^encoded[i]); } return res; } }; ``` #### 用时和内存 > 执行用时：0 ms，在所有 C++提交中击败了100.00%的用户 > 内存消耗：5.7 MB，在所有 C++提交中击败了88.10%的用户 ### 数学 + 异或运算性质 异或运算具有如下性质： 1.$$x \oplus x = 0$$ 2.$$x \oplus y = y \oplus x$$（交换律） 3.$$(x \oplus y) \oplus z = x \oplus (y \oplus z)$$（结合律） 4.$$x \oplus y \oplus y = x$$ （自反性） 5.$$\forall i \in Z$$，有$$4i \oplus(4i+1)\oplus(4i+2)\oplus(4i+3) = 0$$ 在本题中，需要计算 $$S = start\oplus start+2\oplus start+4\oplus \cdots\oplus start+(2n-2)$$。 因为$$start + 2i, 0\leq i<n$$的奇偶性相同，因此$$S$$的最后一位二进制位为1当且仅当$$start$$为奇数且$$n$$为奇数。 因此，我们可以仅考虑$$S$$除了最后一个二进制位以外的其余二进制位，相当于将$$S$$中的每一项$$start+2i$$都右移一位，即$$\lfloor\frac{start}{2}\rfloor+i$$，记$$s = \lfloor\frac{start}{2}\rfloor$$，则 $$S = \left[ s\oplus (s+1) \oplus (s+2) \oplus (s+3) \oplus \cdots \oplus (s+n-1) \right]<<1 + e$$ 其中$$<<$$表示左移运算，$$e$$表示$$S$$的最后一位二进制位，即  接下来，因此，$$v$$的前半部分即为$$s$$到$$s+n-1$$的异或和。考虑从$$1$$到$$n$$的异或和函数$$sumXor(n) = 1\oplus 2\oplus3\oplus\cdots\oplus n$$，根据异或运算的**性质5**，将每四个数字合并成一组，因此有  进一步讨论$$n$$的最后2位二进制位，可以化简  而根据异或运算的**性质1**，我们有  因此，  因此，可以在$$O(1)$$时间内计算出$$S$$的值。 #### 代码 ```cpp class Solution { public: inline int sumXor(int n){ if(n % 4 == 0){ return n; }else if(n % 4 == 1){ return 1; }else if(n % 4 == 2){ return n+1; } return 0; } int xorOperation(int n, int start) { int s = start / 2; int e = (n % 2 == 1 && start % 2 == 1); return 2 * (sumXor(s + n - 1) ^ sumXor(s - 1)) + e; } }; ``` #### 用时和内存 > 执行用时：0 ms，在所有 C++提交中击败了100.00%的用户 > 内存消耗：5.7 MB，在所有 C++提交中击败了95.80%的用户
所有评论
暂无评论
新增评论
评论
邮箱
邮箱仅作验证使用
图形验证码
邮箱验证码
发送验证码
发表评论
所有评论
暂无评论