字典树/前缀树

• 概述

字典树/前缀树是一种利用字符串的公共前缀来减少查询时间的树形结构，查询效率高，但存储空间消耗比较大。

• 经典应用
  • 异或问题
• 例题1：异或问题

给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 。
第 i 个查询的答案是 和任何 nums 数组中不超过 的元素按位异或（XOR）得到的最大值。换句话说，答案是 ，其中所有 j 均满足 。如果 nums 中的所有元素都大于 ，最终答案就是 -1 。
返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。

题目来源：Leetcode1707题
题目链接：https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array
分析：
本题数据量较大，需要进行离线查询。将nums数据从小到大排序后再将queries中的数据从小到大排序。每次只插入比当前查询的小的数。查询的时候尽可能使得高位不相同。
参考解答：

class Solution:
    def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        nums.sort()
        q = [(m, x, idx) for idx, (x, m) in enumerate(queries)]
        q.sort()
        i = 0
        ret = [0] * len(q)
        trie = Trie()
        for m, x, idx in q:
            while i < len(nums) and nums[i] <= m:
                trie.insert(nums[i])
                i += 1
            ret[idx] = trie.getXor(x)
        return ret
class TrieNode:
    def __init__(self) -> None:
        self.val = -1
        self.next = {}
def binaryStr(val):
    s = bin(val)[2:]  # 转化为2进制后前面两个字符为0b，故去掉
    n = len(s)
    return '0' * (32-n) + s
class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()
    def insert(self, num):
        binary = binaryStr(num)
        cur = self.root
        for c in binary:
            if c not in cur.next:
                cur.next[c] = TrieNode()
            cur = cur.next[c]
        cur.val = num
    def getXor(self, num):
        cur = self.root
        if not cur.next:
            return -1
        binary = binaryStr(num)
        for c in binary:
            if c == '0':
                cur = cur.next['1'] if '1' in cur.next else cur.next['0']
            elif c == '1':
                cur = cur.next['0'] if '0' in cur.next else cur.next['1']
        return cur.val ^ num

• 练习题
  • 数组中两个数的最大异或值

题目来源：Leetcode421题
题目链接：https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/
参考解答：

class TrieNode:
    def __init__(self):
        self.next = {}
        self.val = -1
def buildBinary(num):
    s = bin(num)[2:]
    n = len(s)
    binary = '0' * (32 - n) + s
    return binary
class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        root = TrieNode()
        for num in nums:
            cur = root
            binary = buildBinary(num)
            for c in binary:
                if c not in cur.next:
                    cur.next[c] = TrieNode()
                cur = cur.next[c]
            cur.val = num
        ans = 0
        for num in nums:
            cur = root
            binary = buildBinary(num)
            for c in binary:
                if c == '0':
                    cur = cur.next['1'] if '1' in cur.next else cur.next['0']
                elif c == '1':
                    cur = cur.next['0'] if '0' in cur.next else cur.next['1']
            ans = max(ans, cur.val ^ num)
        return ans