思路:從最高位向低位構造,對每一位利用哈希表尋找是否存在可使此位為1的數
第一輪找1:清空哈希表,1,2存1,到3發現1^0=1,res|=1<<3
第二輪找11:清空哈希表,1存10,2存10,3發現11^01=10,res|=1<<3
第三輪找111:清空哈希表,1存101,2存101,3存011…找不到能構造出111的
第四輪找1101:清空哈希表,1存1010,2存1011,到3發現1101^0111=1010,res|=(1<<0)
class Solution {
public:int findMaximumXOR(vector<int>& nums) {int res=0,mask=0;unordered_set<int>set;for(int i=31;i>=0;i--){set.clear();mask|=1<<i;int tmp=res|(1<<i);for(int num:nums){int x=num&mask;if(set.contains(tmp^x)){res=tmp;break;}set.insert(x);}}return res;}
};
在前邊基礎上加上限制條件即可,對任意強數對滿足|x-y|<=min(x,y),假設x比y大那么2*y>=x即可,那么只需要排序后利用unordered_map記錄之前的值比較一下即可
class Solution {
public:int maximumStrongPairXor(vector<int>& nums) {sort(nums.begin(),nums.end());int res=0,mask=0;unordered_map<int,int>map;for(int i=31;i>=0;i--){map.clear();mask|=1<<i;int tmp=res|(1<<i);for(int j:nums){int x=mask&j;if(map.count(tmp^x)&&map[tmp^x]*2>=j){res=tmp;break;}map[x]=j;}}return res;}
};