題目:
https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #define MAXN 3000001
int tree[MAXN][2] = {};
int cnt = 1;
class Solution {
public:
void reset(){
for(int i=1; i<=cnt; ++i)
tree[i][0] = tree[i][1] = 0;
cnt = 1;
}
void insert(int num){
int curr = 1;
for(int i=30, path; i>=0; --i){
path = (num >> i) & 1;
if(tree[curr][path] == 0) tree[curr][path] = ++cnt;
curr = tree[curr][path];
}
}
int maxXOR(int num){
int ans = 0;
int curr = 1;
for(int i=30, status, want; i>=0; --i){
status = (num >> i) & 1;
want = status^1;
if(tree[curr][want] == 0) want ^= 1;
ans |= (status^want) << i;
curr = tree[curr][want];
}
return ans;
}
int findMaximumXOR(vector<int>& nums) {
for(int n : nums) insert(n);
int ans = 0;
for(int n : nums) ans = max(ans, maxXOR(n));
reset();
return ans;
}
};
|
