力扣第 221 场周赛第 4 题
题目
给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。
第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。
返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。
示例 1：
输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
输出：[3,3,7]
解释：
1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.
示例 2：
输入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
输出：[15,-1,5]
提示：
1 <= nums.length, queries.length <= 105queries[i].length == 20 <= nums[j], xi, mi <= 109
相似问题：
分析
- 0421 升级版，区别是只查询 <=m 的元素
- 一种常用的方法是将查询和元素都排序，保证整个查询过程中元素只加不减
- 在这个过程中，动态构建哈希表或字典树，即转为 0421
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
L = max(nums+[x for x,_ in queries]).bit_length()
T = [set() for _ in range(L)]
nums.sort()
j = 0
res = [-1]*len(queries)
for i,(x,m) in sorted(enumerate(queries),key=lambda p:p[1][1]):
while j<len(nums) and nums[j]<=m:
for k in range(L):
T[k].add(nums[j]>>k)
j += 1
if j:
y = 0
for k in range(L-1,-1,-1):
y <<= 1
y += (y+1)^(x>>k) in T[k]
res[i] = y
return res
|
1565 ms
*附加
字典树写法。
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
class BitTrie:
def __init__(self,n,L): # 插入总长度 n-1、最长 L 的二进制串
self.t = [[0]*n for _ in range(2)] # 模拟树节点
self.i = 0
self.L = L
def add(self, x):
p = 0
for j in range(self.L-1, -1, -1):
bit = (x>>j)&1
if not self.t[bit][p]:
self.i += 1
self.t[bit][p] = self.i
p = self.t[bit][p]
def maxxor(self,x):
p = 0
res = 0
for j in range(self.L-1, -1, -1):
bit = (x>>j)&1
if self.t[bit^1][p]:
res |= 1 << j
bit ^= 1
p = self.t[bit][p]
return res
class Solution:
def maximizeXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
L = max(nums+[x for x,_ in queries]).bit_length()
trie = BitTrie(len(nums)*L+1,L)
nums.sort()
j = 0
res = [-1]*len(queries)
for i,(x,m) in sorted(enumerate(queries),key=lambda p:p[1][1]):
while j<len(nums) and nums[j]<=m:
trie.add(nums[j])
j += 1
if j:
res[i] = trie.maxxor(x)
return res
|
1753 ms