Python中查找元素列表小于限制且XOR最大的程序

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))

输入

[3、5、9],[[4、6],[2、0]]

出口

[3、-1]

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程