Trie 与位运算：最大异或值

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

思路：将每个数的 32 位二进制表示插入 Trie，查询时贪心地走与当前位相反的分支（使异或值最大）。

class MaxXOR {
    private int[][] trie = new int[32 * 100005][2];
    private int cnt = 1;

    private void insert(int x) {
        int node = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (x >> i) & 1;
            if (trie[node][bit] == 0) trie[node][bit] = cnt++;
            node = trie[node][bit];
        }
    }

    private int query(int x) {
        int node = 0, xorVal = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (x >> i) & 1;
            int want = 1 - bit;    // 贪心：选与当前位相反的分支
            if (trie[node][want] != 0) {
                xorVal |= (1 << i);
                node = trie[node][want];
            } else {
                node = trie[node][bit];
            }
        }
        return xorVal;
    }

    public int findMaximumXOR(int[] nums) {
        for (int x : nums) insert(x);
        int max = 0;
        for (int x : nums) max = Math.max(max, query(x));
        return max;
    }
}

时间复杂度：O(32n)，比 O(n²) 暴力好很多。

最大异或值（带上限约束，LeetCode 2935）

// 查询：在 nums 中找一个数 x，使 x XOR num 最大，且 x XOR num <= maximumBit
// 等价于找 num XOR target，其中 target = (1<<k)-1
public int[] getMaximumXor(int[] nums, int maximumBit) {
    int mask = (1 << maximumBit) - 1;  // 全1掩码
    int xorAll = 0;
    for (int x : nums) xorAll ^= x;
    int n = nums.length;
    int[] ans = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        // 与xorAll异或后，选使结果最大的k位
        ans[n - 1 - i] = xorAll ^ mask;
        xorAll ^= nums[i];
    }
    return ans;
}

数组中最长的按位与（连续子数组最大AND）

线段树变体，Trie 也可解决区间按位 AND 问题。

字典序最小的回文字符串（LeetCode 2697）

位 Trie 的技巧总结

数组形式 vs 链表形式

// 数组形式（高效，优先使用）
int[][] trie = new int[MAXN][26];

// 链表形式（代码清晰，底层框架常用）
static class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd;
}