互联网技术培训,深圳网站seo推广,个人搭建网站教程,毕设做网站 方面的论文1. 题意
求数组中两个数的最大异或值
数组中两个数的最大异或值
2. 题解
2.1 哈希表 a i ⊕ a j x a_i \oplus a_j x ai⊕ajx 所以 a i x ⊕ a j a_i x \oplus a_j aix⊕aj
考虑 a i 、 a j a_i、a_j ai、aj的每一位的所有情况 b i t ( a i , k ) bit(a_i…1. 题意
求数组中两个数的最大异或值
数组中两个数的最大异或值
2. 题解
2.1 哈希表 a i ⊕ a j x a_i \oplus a_j x ai⊕ajx 所以 a i x ⊕ a j a_i x \oplus a_j aix⊕aj
考虑 a i 、 a j a_i、a_j ai、aj的每一位的所有情况 b i t ( a i , k ) bit(a_i,k) bit(ai,k) b i t ( a j , k ) bit(a_j,k) bit(aj,k) b i t ( x , k ) bit(x,k) bit(x,k)000011101110
我们可以从最高位开始尝试是否能使第 k k k位为1。
即对 p r e ( k , a j ) pre(k,a_j) pre(k,aj) p r e S e t ( k ) preSet(k) preSet(k)中是否有 x ⊕ p r e ( k , a j ) x \oplus pre(k,a_j) x⊕pre(k,aj)使得枚举的最大前缀 x x x成立。
代码
class Solution {
public:int findMaximumXOR(vectorint nums) {int ans 0;for ( int i 30; i -1; --i ) {unordered_setint preSet;for ( int num: nums) {preSet.insert( num i);}ans ans 1 | 1;bool find false;for (int num: nums) {if ( preSet.count( (num i) ^ ans )) {find true;break;}}if ( !find)ans--;} return ans;}
};2.2 前缀树
可以将所有值插入到一颗0-1前缀树中然后再遍历每个值对于每一位尽量选择它的翻转值如果 树中有该路径的话。最后再取最大值。
class Solution {
public:class Trie {public:Trie():isEnd(false),left(nullptr),right(nullptr){}void insert(int v) {Trie *cur this;for ( int bit 30; bit -1; --bit) {int c (1 bit) v;if (!c) {if (cur-left nullptr) {cur-left new Trie();}cur cur-left;}else {if ( cur-right nullptr)cur-right new Trie();cur cur-right;}}cur-isEnd true;}int getMaxXor(int v) {int ans 0;Trie *cur this;for ( int bit 30; bit -1; --bit) {int c (1 bit) v;if (c) {if ( cur-left) {cur cur-left;ans | (1 bit);}else {cur cur-right;}}else {if ( cur-right ) {cur cur-right;ans | (1 bit);}else {cur cur-left;}}}return ans; }private:Trie *left;Trie *right;bool isEnd;};int findMaximumXOR(vectorint nums) {Trie trie;for (int num: nums)trie.insert(num);int ans 0;for (int num:nums) {ans max(ans, trie.getMaxXor(num) );}return ans;}
};
