本文共 2419 字,大约阅读时间需要 8 分钟。
最近在leetcode发现两道异或相关的题目,觉得挺好的,拿出来分享一下。
公式还是要清楚的
1、归零率:a ^ a = 0(自己异或自己结果为0) 2、恒等率:a ^ 0 = a(与0异或结果不变) 3、交换律:a ^ b = b ^ a 4、结合律:a ^ b ^ c = a ^ (b ^ c )题目中给出的encoded[i] 公式如下:
encoded[i] = arr[i] XOR arr[i + 1]
我们可以利用归零律、恒等率、结合律,让等号两边同时异或arr[i + 1],即得到:
encoded[i] XOR arr[i + 1] = arr[i] XOR arr[i + 1] XOR arr[i + 1],
又因为:arr[i + 1] XOR arr[i + 1] 等于 0,arr[i] XOR 0 等于 arr[i]
所以最终公式变为:
arr[i] = encoded[i] XOR arr[i + 1]
题目中恰好又告诉了我们arr[0]的值,所以最终我们便能计算出arr数组中每个位置的值。
public class LC_1720 { public int[] decode(int[] encoded, int first) { int n = encoded.length + 1; int[] ans = new int[n]; ans[0] = first; for (int i = 1; i < n; i++) { ans[i] = encoded[i - 1] ^ ans[i - 1]; } return ans; }}
很显然本题从 encoded[i] = perm[i] XOR perm[i + 1] 这个公式开始分析,与第一题给出的公式一样,区别在与不知道perm数组第一个下标的元素值是多少了,那我们猜想假设我们能得到第一个下标的值,那么这题就解决了。
我们再分析题目,给出的条件中,指出perm 是前 n 个正整数的排列,且 n 是个 奇数 。
假设n等于5,那么perm中的数字就是由,1-5组成,假设就是【1,2,3,4,5】,顺序不一定,但是值一定是这5个数字的排列组合。
再回到encoded[i] = perm[i] XOR perm[i + 1] 公式中,我们可以看出:
encoded[0] = perm[0] XOR perm[1]
encoded[1] = perm[1] XOR perm[2] …
那么encoded数组中所有数的异或结果应该如下:
perm[0] XOR perm[1] XOR perm[1] XOR perm[2] XOR perm[2] XOR perm[3]。。。XOR perm[n-1] XOR perm[n]
如果这样一直下去最终encoded数组中所有数异或的结果实际上就等于
perm[0] XOR perm[n]
这看起来没什么用,那我们换一个方式,不妨我们每隔一位异或一下,也就是:
encoded[0] XOR encoded[2] XOR encoded[4]。。。
那么最终将会得到:
perm[0] XOR perm[1] XOR perm[2] XOR perm[3] XOR perm[4] XOR perm[5]
也就得到了perm数组每一位异或后的结果。
现在我们再回到,perm 是前 n 个正整数的排列,这个条件中,上面已经说过了,perm下标1-5实际上就是数字1-5,只不过不一定数字和下标不一定是按照顺序对应而已,但是这并对于结合律来说并没有影响,所以我们只要让1-5异或即可。
上半部分:perm[0] XOR perm[1] XOR perm[2] XOR perm[3] XOR perm[4] XOR perm[5]
XOR
下半部分:1 XOR 2 XOR 3 XOR 4 XOR 5
又因为 perm[1] XOR perm[2] XOR perm[3] XOR perm[4] XOR perm[5],就是对应这1到5的异或结果,所以最终上下异或后得到perm[0]。
好了,现在我们终于拿到了perm[0],接下来按照第一题的方法即可。
class Solution { public int[] decode(int[] encoded) { int[] ans = new int[encoded.length + 1]; int n = encoded.length + 1; int a = 0; for (int i = 1; i <= n; i++) { a ^= i; } int e = 0; for (int i = 1; i < encoded.length; i += 2) { e ^= encoded[i]; } ans[0] = a ^ e; for (int i = 0; i < encoded.length; i++) { ans[i + 1] = ans[i] ^ encoded[i]; } return ans; }}
转载地址:http://welrb.baihongyu.com/