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

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

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

### 题目大意： ###

略。

### 分析： ###

字典树 + 贪心.

### 代码如下： ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 };

转载于:https://www.cnblogs.com/zaq19970105/p/11458824.html

[https_leetcode-cn.com_problems_maximum-xor-of-two-numbers-in-an-array]: https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/9e12358393d84bfb99b20db4cad6b1a0.png