421. 数组中两个数的最大异或值 (opens new window)

1.位掩码+异或运算

本题利用异或运算一个重要性质：假设a^b=c，那么这个三个数的顺序任意交换依然成立，a^c=b。

根据题意，我们需要确定一个31位二进制数上，每个位置是否可以等于1，最理想情况都为1肯定是最大的。常规做法下两两异或运算，再判断该位是否为1，复杂度n方超时。而利用上述性质，可以将判断“数组存在两个数的异或运算结果使该位为1”这件事的复杂度降为O(n)。

• 使用哈希表存储每个前缀掩码，假设当前这个数的前缀掩码与"期望最大结果"的异或运算结果在哈希表中，那么说明数组存在两个数可以保证第i位上的二进制编码为1，否则为0。

1. 假设i=3，res=1100，数组二进制表示分别为1100，0001，0110
2. 进行掩码运算获取对应的前缀。因为在第三位上11^11=00，而00是存在的，因此1100可以组合得到。
3. 当i=2时，因为不存在和111异或结果也在哈希表的数，因此第二位只能为0，即使res=1100

class Solution {
    public int findMaximumXOR(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int max = Integer.MAX_VALUE-(Integer.MAX_VALUE>>1);
        int mask = 0;
        int res=0;
        for (int i = 31; i >= 0; i--) {
            mask += max;
            res += max;
            for (int num : nums) {
                int a = mask & num;
                map.put(a, map.getOrDefault(a, 0) + 1);
            }
            boolean check = false;
            for (int num : nums) {
                int numMask = mask & num;
                int ans = numMask ^ res;
                if (map.containsKey(ans)) {
                    check = true;
                    break;
                }
            }
            if(!check) res -= max;
            map.clear();
            max = max >> 1;
        }
        return res;
    }
}

2935. 找出强数对的最大异或值 II (opens new window)

相同思路。枚举每个二进制比特位判断是否可以等于1时，还需要加一层判断，是否满足不等式关系。