【Leetcode 每日一题 - 扩展】421. 数组中两个数的最大异或值
问题背景
给你一个整数数组 n u m s nums nums，返回 n u m s [ i ] X O R n u m s [ j ] nums[i]\ XOR\ nums[j] nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 0 ≤ i ≤ j < n 0≤i≤j<n。
数据约束
- 1 ≤ n u m s . l e n g t h ≤ 2 × 1 0 5 1 \le nums.length \le 2 \times 10 ^ 5 1≤nums.length≤2×105
- 0 ≤ n u m s [ i ] ≤ 2 31 − 1 0 \le nums[i] \le 2 ^ {31} - 1 0≤nums[i]≤231−1
解题过程
终于出现每日一题抄都抄不明白的情况了，今天的题需要改进 0 − 1 0 - 1 0−1背包之后将数组处理成前后缀，然后再解决两个数组中的最大异或值问题。
自己目前动态规划掌握地并不好，不强求。
不过其中涉及到的这个最大异或值是可以学着写写，积累一下的。
主要的思路是从高到低枚举数组中数字的每一位，依次判断这一位上有没有可能异或得到 1 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;}
}