LC:https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
public int findMaximumXOR(int[] nums) {
int max = 0, mask = 0;
for (int i = 31; i >= 0; i--){
mask = mask | (1 << i);
Set<Integer> set = new HashSet<>();
for(int num : nums){
int left = num & mask
set.add(left);
}
int greed = max | (1 << i);
for (int prefix : set){
if (set.contains(greed ^ prefix)) {
max = greed;
break;
}
}
}
return max;
}
有人能解释一下当我们用一个看起来越来越小的掩码(从2^31,2^30开始…(在nums[i]上应用AND运算符时发生了什么吗?
int left = num & mask
我从评论中知道,它应该保留左边的比特,而忽略右边的比特,但我仍然不确定这段代码背后发生了什么。
给定输入[3,10,5,25,2,8]
,输出为28
(由5
^25
给定(:
Num Binary
5 00101
^ 25 11001
------------
= 28 11100
注意,当两个比特不同时,xor
运算给出1
,否则给出0
。因此,考虑到这一点,我们从左边开始(最高有效位,由代码中的i=31
给出(。
带
mask = mask | (1 << i);
我们在每次迭代中计算CCD_ 9。在第一次迭代中,掩码是100...000
,然后是下一次迭代中的1100...000
,依此类推。如果您不确定如何操作,请参考此答案。
请注意,我们使用的是贪婪方法——当您处理i
位时,您只关心该位置的位;左边的已经在前面处理过了,右边的将在后面的迭代中处理。考虑到这一点,在下一步中,我们创建一个哈希集set
,并将所有num & mask
值放在其中。例如,当i=30时,我们的掩码是110...000
,因此在这一点上,我们只关注5
和25
中的i=30
位(左侧的MSB,即i=31
,已经得到了处理,由于我们使用了&
,右侧的MSB将被忽略,因为我们的掩码中有所有的0
(。
下一篇:
int greed = max | (1 << i);
我们为当前迭代设定了"期望值"。理想情况下,我们希望1
位于i
的位置,因为我们希望找到最大xor。通过这个集合,我们查看set
中的所有元素,看看是否有任何元素符合我们的期望。如果我们找到一个,那么我们相应地更新max
,否则我们的max
保持不变。
我发现将其视为递归算法最简单。
基本情况是当所有数字都为零时。那么最大XOR显然为零。
递归地,我们修剪掉每个数字的最低有效位并求解子问题。现在,假设我们知道这个子问题的最大值,称之为submax
,答案是submax<<1
或(submax<<1)|1
,因为数字的最低有效位只影响最大XOR的最低有效位数。我们可以通过测试任何两个数字是否有这个XOR来检查答案是否是(submax<<1)|1
。
此代码倾向于屏蔽低阶位,而不是移位。循环开启mask
的每个连续位,从最高有效位到最低有效位,对应于当前递归调用中数字长度的增加。CCD_ 32将当前被忽略的低位置零。