Python中查找元素列表小于限制且XOR最大的程序
假设我们有一个数字列表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,因此我们选择产生更大XOR的3。在第二个查询中,没有小于或等于0的数字,因此我们将其设置为-1。
要解决这个问题,我们将按照以下步骤进行−
- trie:一个新的映射
-
定义一个函数bits()。这将取i
-
返回i的32位二进制表示
-
定义一个函数insert。这将取i
-
节点:= trie
-
对于每个位i中的c,执行以下操作
- 如果在节点c中不存在,则在其中插入一个空映射
- node [2]:= i
-
定义一个函数query()。这将取i
-
节点:= trie
-
对于每个位i中的字符,执行以下操作
- rc:= c XOR 1
-
node:=如果存在,否则为node [c] node
-
返回节点[2]
-
从主方法执行以下操作−
-
排序列表A
-
B:形式为(i,x,limit)的元素列表,每个查询索引i和查询值x和limit。然后根据限制进行排序
-
(j,n,ans):=(0,A的大小,与查询大小相同的列表,用-1填充)
-
对于B中的每个索引i和值x和限制,执行以下操作
- 当j
- insert(A [j])
-
j:= j + 1
-
如果j为非零,则
- ans [i]:= query(x)
- 当j
- 返回ans
更多Python相关文章,请阅读:Python 教程
示例(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 inbits(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]