1734. 解码异或后的排列

布满荆棘的人生 2023-01-20 08:08 2阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjUxOTA0_size_16_color_FFFFFF_t_70]

[异或的相关属性和基础参考之前的博客][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjUxOTA0_size_16_color_FFFFFF_t_70 1]

这一题是 1720 的简单升级版本  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjUxOTA0_size_16_color_FFFFFF_t_70 2]

不同之处很明显，就是没有给出一个 ans\[n \]的值让我们通过推导出来的公式  
`encoded[i] XOR perm[i + 1] = perm[i]`进行计算  
所以我们的目的很明确，需要计算出一个perm\[i\],然后后面的计算就和之前那道简单题一样了

如果计算出一个perm\[i\]呢，这里我们可以通过题意计算出`ans[n - 1]`

计算推导过程如下

首先我们将所有的奇数位encoded\[i\] 进行异或，

encoded[1] = perm[1] XOR perm[2]
    encoded[3] = perm[3] XOR perm[4]

得到的结果 1就是

perm[1] ^ perm[2] ^  perm[3]  ^ perm[n - 2]

缺少`^perm[n - 1]`

而encoded是 n 个正整数的排列  
则 n的全量异或结果2为

1^2^n

然后由结果1和结果2异或，由性质1得结果为`perm[n - 1]`，得到结果perm\[n - 1\]后后面的代码就和之前这道题的简单版本一样计算了。具体代码实现如下

public int[] decode(int[] encoded) { 
            int n = encoded.length + 1;
            int[] res = new int[n];
            int a = 0;
            int b = 0;
            // 求得 perm[i - 1]
            for (int i = 0; i < n - 1; i += 2) { 
                a ^= encoded[i];
            }
            // 注意下标是1开始
            for (int i = 1; i <= n; i ++) { 
                b ^= i;
            }
    
            // perm[i - 1]
            res[n - 1] = a ^ b;
            for (int i = n - 2; i >= 0; i--) { 
                res[i] = res[i + 1] ^ encoded[i];
            }
            return res;
    
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjUxOTA0_size_16_color_FFFFFF_t_70]: /images/20221021/8f3afc779f764b3aa3836b7858d3d6da.png
[Link 1]: https://weihubeats.blog.csdn.net/article/details/116462840
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjUxOTA0_size_16_color_FFFFFF_t_70 1]: /images/20221021/b79239d77d9a44548e8eb586576eda23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjUxOTA0_size_16_color_FFFFFF_t_70 2]: /images/20221021/86af113167fd4154bf5910dcf6cb33ae.png