本文共 1483 字，大约阅读时间需要 4 分钟。
今天leetcode每日一题是解码异或后的排列，我个人认为这道题非常巧妙，也能帮助我们更好地理解异或这个符号，同时也会发现它的神奇之处。
题目链接：
这道题的意思是，有从1到n的数存到数组中(n是奇数)，不过被重新排列了，用nums表示，但是我们不知道这个数组是什么，要求我们求出。题目给了我们一个数组encoded，满足encoded[i]=nums[i]^nums[i+1]。所以encoded数组的长度是nums-1。
这里要说的是异或是满足交换率的，即a^b=c 等价于 a ^c=b。所以要求出nums[i]，就是nums[i]=nums[i-1] ^encoded[i-1]。因此只要我们得出nums[0]的值就可以毫不费力地推出nums中的所有值了。题目转换成求nums[0]就行了。
那么nums[0]怎么求，可以想到nums[0]=nums[0]^ nums[1]^nums[2] ^…… ^nums[n-1] ^ nums[1] ^nums[2] ^…… ^nums[n-1] ，这是因为异或的定义为相同为0，nums[0] ^nums[0]=0，0异或任何数都是它本身，那么我们可以把 nums[1] ^ nums[2] ^…… ^nums[n-1] 全部约掉，就只剩下了nums[0]。
题目就再次转换成求nums[0]^ nums[1]^nums[2] ^…… ^nums[n-1] 和 nums[1] ^nums[2] ^…… ^nums[n-1]了。
首先说前面的怎么求，题目已经说明，数字是从1到n，只是重新排列了，但是由于异或符合交换律。比如1 ^ 2 ^ 3=2 ^ 3^ 1，所以nums[0]^ nums[1]^nums[2] ^…… ^nums[n-1]其实就是1 ^2 ^3…… ^n，他们是等价的，无论nums如何排列，交换一下顺序永远都是这样的。
那么nums[1] ^nums[2] ^…… ^nums[n-1]怎么求，我们可以发现：
encoded[1]=nums[1] ^nums[2] encoded[3]=nums[3] ^nums[4] 那么(nums[1]^ nums[2]) ^(nums[3] ^nums[4])=nums[1] ^nums[2] ^nums[3] ^nums[4]。 由于n是奇数，所以我们的encoded是一定不会少掉一个数字的。因此我们的 i 从1开始，i 每次加2，这样就可以得出nums[1] ^nums[2] ^…… ^nums[n-1]的结果。
代码如下：
class Solution { public: vector decode(vector & encoded) { int n=encoded.size(); int a=0,b=0; for(int i=1;i<=n+1;i++) a^=i; for(int i=1;i 代码中a是nums[0]^ nums[1]^nums[2] ^…… ^nums[n-1]的异或和。
b是nums[1] ^nums[2] ^…… ^nums[n-1]的异或和。这样的话我们a^b就是nums[0]了。
至此，这道题就讲完啦，继续加油：)
发表评论
最新留言
关于作者
