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]

Arnab Chakraborty

更新于: 2020-12-22

138 次浏览

开启你的 职业生涯

完成课程获得认证

开始学习