【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;
    }
}

原文地址：https://blog.csdn.net/2401_88859777/article/details/145227860

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！