Leetcode 421. Maximum XOR of Two Numbers in an Array

[Woodyiiiiiii]

421. Maximum XOR of Two Numbers in an Array

421. Maximum XOR of Two Numbers in an Array

这道题我没想到解法。用贪心的话不行，遍历数组的话只能两次遍历。

那么，这时候就要观察题目特性了，我们其实只需要关注数的二进制情况，而且数值之间有共用特性。

这就是字典树Trie数据结构。我们也不用标志位，直接用this和判空来验证数是否存在。

class Solution {
    public int findMaximumXOR(int[] nums) {
        int ans = 0;
        Trie trie = new Trie();
        for (int num : nums) {
            trie.insert(num);
        }
        for (int num : nums) {
            ans = Math.max(ans, trie.check(num));
        }
        return ans;
    }

    class Trie {
       
        Trie[] next;
        
        public Trie() {
            next = new Trie[2];
        }

        public void insert(int num) {
            Trie cur = this;
            for (int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (cur.next[bit] == null) {
                    cur.next[bit] = new Trie();
                }
                cur = cur.next[bit];
            }
        }

        public int check(int num) {
            int max = 0;
            Trie cur = this;
            for (int i = 31; i >= 0; i--) {
                int bit = (num >> i) & 1;
                if (cur.next[bit ^ 1] != null) {
                    cur = cur.next[bit ^ 1];
                    max |= (1 << i);
                } else {
                    cur = cur.next[bit];
                }
            }
            return max;
        }
    }
}