题目

2317. 操作后的最大异或和 - 力扣（LeetCode）

给你一个下标从 0 开始的整数数组 nums 。一次操作中，选择 任意 非负整数 x 和一个下标 i ，更新 nums[i] 为 nums[i] AND (nums[i] XOR x) 。

注意，AND 是逐位与运算，XOR 是逐位异或运算。

请你执行 任意次 更新操作，并返回 nums 中所有元素 最大 逐位异或和。

示例 1：

1
2
3
4
5
6
输入：nums = [3,2,4,6]
输出：7
解释：选择 x = 4 和 i = 3 进行操作，num[3] = 6 AND (6 XOR 4) = 6 AND 2 = 2 。
现在，nums = [3, 2, 4, 2] 且所有元素逐位异或得到 3 XOR 2 XOR 4 XOR 2 = 7 。
可知 7 是能得到的最大逐位异或和。
注意，其他操作可能也能得到逐位异或和 7 。

示例 2：

1
2
3
4
5
输入：nums = [1,2,3,9,2]
输出：11
解释：执行 0 次操作。
所有元素的逐位异或和为 1 XOR 2 XOR 3 XOR 9 XOR 2 = 11 。
可知 11 是能得到的最大逐位异或和。

提示：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^8

解题

这道题有点脑筋急转弯的感觉。

要想获得最大逐位异或和（我们设为ans），就必须尽可能的保留更多异或后的1的个数。

我们再来看这个运算操作：nums[i] AND (nums[i] XOR x)

实际上：

  • nums[i] XOR x等同于将nums[i]修改为任意非负整数。
  • num[i] AND ??? 等同于修改nums[i]的某些比特位（由1修改为0）

由于我们想要尽可能的保留更多异或后的1的个数。因此必须使得二进制位上1的个数要是奇数。因此nums[i] AND (nums[i] XOR x)操作就是将某些比特位上的1修改为0，从而使得该位上的1是奇数个，最终异或结果里该位上才是1。

因此我们发现，这道题目要求的最大逐位异或和，实际上等价于对数组中每个元素的所有二进制位，只要某一位在数组中出现过 1，那么答案里这一位也是 1，得到的结果才达到最大。

因此我们可以用逐位或运算来尽最大努力保留每一位上的1。

代码很简单：

1
2
3
4
5
6
7
8
9
class Solution {
    public int maximumXOR(int[] nums) {
        int ans = 0;
        for(int i : nums) {
            ans = i | ans;
        }
        return ans;
    }
}