【Leetcode 每日一题 - 扩展】421. 数组中两个数的最大异或值

问题背景

给你一个整数数组 $nums$，返回 $nums[i]XORnums[j]$ 的最大运算结果，其中 $0\le i\le j<n$。

数据约束

• $1\le nums.length\le 2\times 10^5$
• $0\le nums[i]\le 2^{31}-1$

解题过程

终于出现每日一题抄都抄不明白的情况了，今天的题需要改进$0-1$背包之后将数组处理成前后缀，然后再解决两个数组中的最大异或值问题。
自己目前动态规划掌握地并不好，不强求。
不过其中涉及到的这个最大异或值是可以学着写写，积累一下的。

主要的思路是从高到低枚举数组中数字的每一位，依次判断这一位上有没有可能异或得到$1$，计算出所需的另一个因子，判断它在数组中是否存在即可。
这里的判断，有点像 两数之和，可以用哈希表来实现。

具体实现

class Solution {public int findMaximumXOR(int[] nums) {// 标准流程，计算数组中数字可能的最大有效长度int max = 0;for (int num : nums) {max = Math.max(max, num);}int n = 31 - Integer.numberOfLeadingZeros(max);// 定义一个掩码变量，方便在过程中处理某一位上的问题int res = 0, mask = 0;Set<Integer> set = new HashSet<>();// 这里下标 i 需要倒序变化，因为某一位上为 1 是需要通过左移来实现的for (int i = n; i >= 0; i--) {set.clear();mask |= 1 << i;// nextRes 表示下一个可能的较大的结果int nextRes = res | (1 << i);for (int num : nums) {// 这一位之后的所有位上置零num &= mask;// 如果对应的因子在集合中存在，就更新结果if (set.contains(nextRes ^ num)) {res = nextRes;break;}set.add(num);}}return res;}
}