个人如何做微商城网站设计,网页策划方案模板范文,定制app系统开发,南宁怎么做网站421. 数组中两个数的最大异或值
给你一个整数数组 nums #xff0c;返回 nums[i] XOR nums[j] 的最大运算结果#xff0c;其中 0 ≤ i ≤ j n 。
示例 1#xff1a; 输入#xff1a;nums [3,10,5,25,2,8] 输出#xff1a;28 解释#xff1a;最大运算结果是 5 XOR…421. 数组中两个数的最大异或值
给你一个整数数组 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 * 105 0 nums[i] 2的31次方 - 1
字典树
思路可以将每个数变成最高31位的二进制数建立字典树为使异或值最大应该尽可能找不一样的如果该位为0先找1该位为1先找0
class Solution {
public://记录某个id下下个数为0或者1的idint a[200005*31][2];//记录某个id代表的十进制数 是唯一的int cnt[200005*31];//按顺序赋予id代表树的一个节点int id0;int findMaximumXOR(vectorint nums) {for(int i0;inums.size();i){insert(nums[i]);}int res0;for(int i0;inums.size();i){res max(res,find(nums[i]));}return res;}//建树void insert(int b){int p0;for(int i30;i0;i--){int x(bi)1;//获得第i位的值if(a[p][x]0) a[p][x]id;//新建节点pa[p][x];}cnt[p]b;//记录该节点的十进制数}//找树中和b异或的最大值int find(int b){int p0;int big0;for(int i30;i0;i--){int x(bi)1;if(x1){if(a[p][0]!0) pa[p][0];else if(a[p][1]!0) pa[p][1];}if(x0){if(a[p][1]!0) pa[p][1];else if(a[p][0]!0) pa[p][0];}}bigmax(big,b^cnt[p]);return big;}
};
