Python中查找小于limit和XOR最大值的元素列表的程序

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个数字nums列表和一个查询列表，其中每个查询都包含[x，limit]。我们必须找到一个列表，以便对每个查询[x，limit]，我们找到一个以数字表示的元素e，以使e≤limit且e XOR x最大化。如果没有这样的元素，则返回-1。

因此，如果输入类似于nums = [3，5，9]查询= [[4，6]，[2，0]]，那么对于第一个查询，输出将为[3，-1]，我们可以使用2或4。3 ^ 4 = 7，而5 ^ 4 = 3，所以我们选择3产生更大的XOR。在第二个查询中，没有这样的数字小于或等于0，因此我们将其设置为-1。

范例(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]

以上是 Python中查找小于limit和XOR最大值的元素列表的程序 的全部内容， 来源链接： utcz.com/z/321391.html