LeetCode/2020_September/14.cpp at master · zzz0906/LeetCode · GitHub

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    TreeNode{
        TreeNode* leftb, righto;
    }
    int findMaximumXOR(vector<int>& nums) {
        TreeNode* root = new TreeNode();
        for （auto num:nums){
            int bin[32];
            for(int i = 0; i <= 31; i++){
                if(num & (1<<i))
                    bin[i]=1;
                else
                    bin[i]=0;
            }
            TreeNode* current = root;
            for (int i = 31; i >= 0; i--){
                if (bin[i] == 1){
                    if (current->righto != NULL) {current->righto;continue;}
                    else {current->righto = new TreeNode(); current = current->righto;}
                }else{
                    if (current->leftb != NULL) {current = current->leftb;continue;}
                    else {current->leftb = new TreeNode(); current = current->leftb;}
                }
            }
        }
        int ans = 0;
        for (auto num : nums){
            int bin[32];
            for(int i = 0; i <= 31; i++){
                if(num & (1<<i))
                    bin[i]=1;
                else
                    bin[i]=0;
            }
            TreeNode* current = root;
            int current_res[31];
            for (int = 31; i >= 0; i--){
                if (bin[i] == 1){
                    if (current->leftb != NULL) {current = current->leftb; current_res[i] = 1;}
                    else {current = current->righto; current_res[i] =0;}
                }else{
                    if (current->righto!= NULL) {current = current->righto; current_res[i] = 1;}
                    else {current = current->leftb; current_res[i] =0;}
                }
            }
            multi = 1;
            int current_dec = 0;
            for (int i = 0; i <= 31; i++){
                current_dec += current_res[i]*multi;
                multi *= 2;
            }
            ans = max(ans,current_dec)
        }
        return ans;
    }
};