3妹:“太阳当空照,花儿对我笑,小鸟说早早早,你为什么背上炸药包”
2哥 :3妹,什么事呀这么开心呀。
3妹:2哥你看今天的天气多好啊,阳光明媚、万里无云、秋高气爽,适合秋游。
2哥:是啊,都快立冬了,天气还是这么热。今年的冬天比以往来的要晚一些。
3妹:晚来也是要来的,看天气预报 下周要降温,估计没几天这种暖的天气了。
2哥:注意保暖啊3妹,看你们女生还穿着裙子,不能只要美丽,就冻人啊。
3妹:我才不,天冷了我就穿秋裤,卷死她们。
2哥:说到卷她们,不如做一道题,在技术上卷死她们。 内外兼修~
1题目:
给你一个整数数组 nums ,返回 nums[i] XOR nums[j] 的最大运算结果,其中 0 ≤ i ≤ j < n 。
示例 1:
输入:nums = [3,10,5,25,2,8]
输出:28
解释:最大运算结果是 5 XOR 25 = 28.
示例 2:
输入:nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出:127
提示:
1 <= nums.length <= 2 * 10^5
0 <= nums[i] <= 2^31 - 1
2思路:
假设我们已经确定了 x 最高的若干个二进制位,当前正在确定第 k 个二进制位。根据题意,我们希望第 k 个二进制位能够取到 1。
解题思路如代码中注释:
3java代码:
class Solution {
// 最高位的二进制位编号为 30
static final int HIGH_BIT = 30;
public int findMaximumXOR(int[] nums) {
int x = 0;
for (int k = HIGH_BIT; k >= 0; --k) {
Set<Integer> seen = new HashSet<Integer>();
// 将所有的 pre^k(a_j) 放入哈希表中
for (int num : nums) {
// 如果只想保留从最高位开始到第 k 个二进制位为止的部分
// 只需将其右移 k 位
seen.add(num >> k);
}
// 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分
// 我们将 x 的第 k 个二进制位置为 1,即为 x = x*2+1
int xNext = x * 2 + 1;
boolean found = false;
// 枚举 i
for (int num : nums) {
if (seen.contains(xNext ^ (num >> k))) {
found = true;
break;
}
}
if (found) {
x = xNext;
} else {
// 如果没有找到满足等式的 a_i 和 a_j,那么 x 的第 k 个二进制位只能为 0
// 即为 x = x*2
x = xNext - 1;
}
}
return x;
}
}
标签:xNext,nums,二进制位,编程,妹学,int,异或,num,found
From: https://blog.51cto.com/u_6813689/8179632