网站怎么伪静态网站,淄博网站优化服务,建设一个类似于京东的网站,重庆装修公司10强3妹#xff1a;“太阳当空照#xff0c;花儿对我笑#xff0c;小鸟说早早早#xff0c;你为什么背上炸药包” 2哥 :3妹#xff0c;什么事呀这么开心呀。 3妹#xff1a;2哥你看今天的天气多好啊#xff0c;阳光明媚、万里无云、秋高气爽#xff0c;适合秋游。 2哥…
3妹“太阳当空照花儿对我笑小鸟说早早早你为什么背上炸药包” 2哥 :3妹什么事呀这么开心呀。 3妹2哥你看今天的天气多好啊阳光明媚、万里无云、秋高气爽适合秋游。 2哥是啊都快立冬了天气还是这么热。今年的冬天比以往来的要晚一些。 3妹晚来也是要来的看天气预报 下周要降温估计没几天这种暖的天气了。 2哥注意保暖啊3妹看你们女生还穿着裙子不能只要美丽就冻人啊。 3妹我才不天冷了我就穿秋裤卷死她们。 2哥说到卷她们不如做一道题在技术上卷死她们。 内外兼修~
题目
给你一个整数数组 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
思路 假设我们已经确定了 x 最高的若干个二进制位当前正在确定第 k 个二进制位。根据题意我们希望第 k 个二进制位能够取到 1。 解题思路如代码中注释
java代码
class Solution {// 最高位的二进制位编号为 30static final int HIGH_BIT 30;public int findMaximumXOR(int[] nums) {int x 0;for (int k HIGH_BIT; k 0; --k) {SetInteger seen new HashSetInteger();// 将所有的 pre^k(a_j) 放入哈希表中for (int num : nums) {// 如果只想保留从最高位开始到第 k 个二进制位为止的部分// 只需将其右移 k 位seen.add(num k);}// 目前 x 包含从最高位开始到第 k1 个二进制位为止的部分// 我们将 x 的第 k 个二进制位置为 1即为 x x*21int xNext x * 2 1;boolean found false;// 枚举 ifor (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*2x xNext - 1;}}return x;}
}
