异或解码（氵）

发表于 | 更新于: | 分类于 |
字数统计: 673 字 | 阅读时长 ≈ 2 分钟

cover老久没有来氵过题解了所以今天写一下（从五一连休中缓过来了），这道异或解码的题中考察了比较重要的异或计算。

一、题目

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：

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

示例 2：

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

提示：

  • 3 <= n < 105
  • n 是奇数。
  • encoded.length == n - 1

二、思路

一开始其实我是想看看位运算是不是可以拿来解答，开局走的就很偏了，笑死，根本做不起。

点开提示上面写着“想想为什么n是奇数”，我一下就悟了

解题需要用到以下这些等式：

  1. a^b=b^a;
  2. if a^b=c,then a^c=b;
  3. a^0=a;

其实示例一这种特殊情况（前n个整数未打乱）已经十分亲切了，我们把数字1，2，3……正好看作第一个、第二个、第三个数……，那么就可以得到一张关于perm和encoded数组关系的表：

encoded index 1 2 3 …… i
对perm的关系 perm[1]XORperm[2] perm[2]XORperm[3] perm[3]XORperm[4] …… perm[i]XORperm[i+1]

仔细观察发现，encoded数组中所有偶数序号对应的值为：

perm[2]XORperm[3]，perm[4]XORperm[5]，……

而这恰好就包含了原来perm数组中除了perm【1】以外所有的元素

之前做过一道弱化版的异或解码，其实这里知道perm【1】其余的就都可以推出了

因此encoded[2]^encoded[4]^…=perm[2]^perm[3]^perm[4]^perm[5]^…

我们可以求出正整数1~n的异或值，有1^2^3^…^n=perm[1]^perm[2]^perm[3]^…perm[n]

由公式**if a^b=c,then a^c=b;**得：

perm[1]=1^2^3^…^n^perm[2]^perm[3]^…perm[n]

后面就轻松了。

三、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int* decode(int* encoded, int encodedSize, int* returnSize){
  int con=0,en=0;//这里等于0不影响后续异或计算：因为a^0=a;
  *returnSize=encodedSize+1;
  for(int i=1;i<encodedSize+2;i++){
​    con^=i;
  }
  for(int i=1;i<encodedSize;i+=2){
​    en^=encoded[i];
  }
  int* perm=malloc(sizeof(int)*(*returnSize));
  perm[0]=con^en;
  for(int i=1;i<(*returnSize);i++){
​    perm[i]=perm[i-1]^encoded[i-1];
  }
  return perm;
}

晚安

有些梦，虚幻却也美好