数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：查找小于限制且异或结果最大的元素列表
假设我们有一个数字列表 nums 和一个查询列表，其中每个查询包含 [x, limit]。我们必须找到一个列表，对于每个查询 [x, limit]，我们找到 nums 中的一个元素 e，使得 e ≤ limit 且 e XOR x 最大化。如果没有这样的元素，则返回 -1。
因此，如果输入类似于 nums = [3, 5, 9] queries = [[4, 6],[2, 0]]，则输出将为 [3, -1]，因为对于第一个查询，我们可以在 nums 中使用 2 或 4。3 ^ 4 = 7 而 5 ^ 4 = 3，所以我们选择 3，它产生更大的 XOR。在第二个查询中，没有小于或等于 0 的数字，所以我们将其设置为 -1。
要解决这个问题，我们将遵循以下步骤：
trie := 一个新的映射
定义一个函数 bits()。它将接收 i
返回 i 的 32 位二进制表示
定义一个函数 insert。它将接收 i
node := trie
对于 bits(i) 中的每个 c，执行以下操作：
node := 如果 c 不在 node 中，则在其中插入一个空映射
node[2] := i
定义一个函数 query()。它将接收 i
node := trie
对于 bits(i) 中的每个 c，执行以下操作：
rc := c XOR 1
node := 如果存在则 node[rc]，否则 node[c]
返回 node[2]
从主方法执行以下操作：
对列表 A 进行排序
B := 一个元素形式为 (i, x, limit) 的列表，对于每个查询索引 i 和查询值 x 和 limit。然后根据 limit 对其进行排序
(j, n, ans) := (0, A 的大小, 一个与查询大小相同的列表, 用 -1 填充)
对于 B 中的每个索引 i 和值 x 和 limit，执行以下操作：
当 j < n 且 A[j] <= limit 时，执行以下操作：
insert(A[j])
j := j + 1
如果 j 不为零，则
ans[i] := query(x)
返回 ans
示例（Python）
让我们看看以下实现，以便更好地理解：
class Solution:
def solve(self, A, queries):
trie = {}
def bits(i):
return map(int, bin(i)[2:].zfill(32))
def insert(i):
node = trie
for c in bits(i):
node = node.setdefault(c, {})
node[2] = i
def query(i):
node = trie
for c in bits(i):
rc = c ^ 1
node = node.get(rc, node.get(c))
return node[2]
A.sort()
B = sorted([(i, x, limit) for i, (x, limit) in enumerate(queries)], key=lambda x: x[2])
j, n, ans = 0, len(A), [-1] * len(queries)
for i, x, limit in B:
while j < n and A[j] <= limit:
insert(A[j])
j += 1
if j:
ans[i] = query(x)
return ans
ob = Solution()
nums = [3, 5, 9]
queries = [
[4, 6],
[2, 0]
]
print(ob.solve(nums, queries))输入
[3, 5, 9], [[4, 6],[2, 0]]
输出
[3, -1]
138 次浏览
