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）
返回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))