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

刺骨的言语ヽ痛彻心扉 2022-10-29 14:26 130阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[官方][Link 1]

class TrieNode {
        
      HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
      public TrieNode() {
        }
    }
    
    class Solution {
        
      public int findMaximumXOR(int[] nums) {
        
        // Compute length L of max number in a binary representation
        int maxNum = nums[0];
        for(int num : nums) maxNum = Math.max(maxNum, num);
        int L = (Integer.toBinaryString(maxNum)).length();
    
        // zero left-padding to ensure L bits for each number
        int n = nums.length, bitmask = 1 << L;
        String [] strNums = new String[n];
        for(int i = 0; i < n; ++i) {
        
          strNums[i] = Integer.toBinaryString(bitmask | nums[i]).substring(1);
        }
    
        TrieNode trie = new TrieNode();
        int maxXor = 0;
        for (String num : strNums) {
        
          TrieNode node = trie, xorNode = trie;
          int currXor = 0;
          for (Character bit : num.toCharArray()) {
        
            // insert new number in trie  
            if (node.children.containsKey(bit)) {
        
              node = node.children.get(bit);
            } else {
        
              TrieNode newNode = new TrieNode();
              node.children.put(bit, newNode);
              node = newNode;
            }
    
            // compute max xor of that new number 
            // with all previously inserted
            Character toggledBit = bit == '1' ? '0' : '1';
            if (xorNode.children.containsKey(toggledBit)) {
        
              currXor = (currXor << 1) | 1;
              xorNode = xorNode.children.get(toggledBit);
            } else {
        
              currXor = currXor << 1;
              xorNode = xorNode.children.get(bit);
            }
          }
          maxXor = Math.max(maxXor, currXor);
        }
    
        return maxXor;
      }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/0e073ea1ad954f44998dafbd930be8db.png
[Link 1]: https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/solution/shu-zu-zhong-liang-ge-shu-de-zui-da-yi-huo-zhi-by-/