hackerrank-Maximum Xor

发表于 更新于 分类于 阅读次数：

描述

原题在这: https://www.hackerrank.com/challenges/maximum-xor/problem
给一个数组, 和一系列query, 对每个query求出数组元素和它xor的最大值. 数组长度和query长度都是最大100000.

思路

brute force是O(n**2)肯定不行. 不过最优解并不难想到, 模拟手算就行. 每来一个query, (从高位到低位)我们优先找和它这一位值相反的数, 这样xor才最大. 用trie实现.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def maxXor(arr, queries):
    # arr: [1, 3, 5, 7]
    # queries: [17, 6, ...]
    trie = {}
    for num in arr:
        cur = trie
        for i in range(31, -1, -1):
            b = (num >> i) & 1 # 这一位是不是1
            if b not in cur:
                cur[b] = {}
            cur = cur[b]
        cur["#"] = 1
    res = []
    for q in queries:
        p = 0  # p是arr中的最佳候选, 来和q生成xor最大值
        cur = trie
        for i in range(31, -1, -1):
            b = 1 ^ ((q >> i) & 1)
            if b not in cur:
                cur = cur[1 ^ b]
                p |= ((1 ^ b) << i)
            else:
                cur = cur[b]
                p |= (b << i)
        res.append(q ^ p)
    return res