LeetCode 数组中两个数的最大异或值-蒲公英云

LeetCode 数组中两个数的最大异或值

迷南。 2023-06-04 14:56 163阅读 0赞

题目链接：https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/

题目大意：

　　略。

分析：

　　字典树 + 贪心.

代码如下：

1 class Trie {
 2 public:
 3     int passed; // 记录经过这个节点的字符串数量
 4     int ends;   // 记录有多少个字符串以这个节点结尾
 5     Trie* nxt[2];
 6     
 7     /** Initialize your data structure here. */
 8     Trie() {
 9         passed = 0;
10         ends = 0;
11         nxt[0] = nxt[1] = NULL;
12     }
13     
14     /** Inserts a word into the trie. */
15     void insert(string word) {
16         Trie* p = this;
17         for(int i = 0; i < word.size(); ++i) {
18             int key = word[i] - '0';
19             
20             if(p->nxt[key] == NULL) {
21                 p->nxt[key] = new Trie();
22             }
23             ++p->passed;
24             p = p->nxt[key];
25         }
26         ++p->ends;
27     }
28     
29     int solve(string word) {
30         int ret = 0;
31         int mask = (1 << 30);
32         
33         Trie* p = this;
34         for(int i = 0; i < word.size(); ++i) {
35             int key = word[i] - '0';
36             
37             if(p->nxt[!key] != NULL) {
38                 ret |= mask;
39                 key = !key;
40             }
41             mask >>= 1;
42             p = p->nxt[key];
43         }
44         return ret;
45     }
46 };
47 
48 
49 class Solution {
50 public:
51     int findMaximumXOR(vector<int>& nums) {
52         Trie trie = Trie();
53         vector< string > bits;
54         int ans = -1;
55         int N = nums.size();
56         
57         for(int i = 0; i < N; ++i) {
58             bits.push_back(bitset< 31 >(nums[i]).to_string());
59             trie.insert(bits[i]);
60         }
61         
62         for(int i = 0; i < N; ++i) {
63             ans = max(ans, trie.solve(bits[i]));
64         }
65         
66         return ans;
67     }
68 };