Chương trình tìm danh sách các phần tử nhỏ hơn giới hạn và XOR là tối đa trong Python

Giả sử chúng ta có một danh sách các số num và một danh sách các truy vấn trong đó mỗi truy vấn chứa [x, giới hạn]. Chúng ta phải tìm một danh sách sao cho mỗi truy vấn [x, limit], chúng ta tìm thấy một phần tử e trong nums sao cho e ≤ giới hạn và e XOR x là cực đại. Nếu không có phần tử như vậy, hãy trả về -1.

Vì vậy, nếu đầu vào giống như nums =[3, 5, 9] queries =[[4, 6], [2, 0]], thì đầu ra sẽ là [3, -1], như đối với truy vấn đầu tiên, chúng ta có thể sử dụng 2 hoặc 4 trong nums. 3 ^ 4 =7 trong khi 5 ^ 4 =3 vì vậy chúng tôi chọn 3 sẽ mang lại XOR lớn hơn. Trong truy vấn thứ hai, không có số nào nhỏ hơn hoặc bằng 0, vì vậy chúng tôi đặt nó thành -1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• trie:=a new map

• Định nghĩa một hàm bit (). Điều này sẽ mất tôi

• trả về biểu diễn nhị phân 32 bit của i

• Xác định một chèn chức năng. Điều này sẽ mất tôi

• nút:=trie

• đối với mỗi c tính bằng bit (i), thực hiện

  • node:=nếu c không có trong node, hãy chèn một bản đồ trống vào bên trong nó

• nút [2]:=i

• Xác định một truy vấn hàm (). Điều này sẽ mất tôi

• nút:=trie

• đối với mỗi c tính bằng bit (i), thực hiện

  • rc:=c XOR 1

  • node:=node [rc] nếu tồn tại, nếu không, node [c]

• nút trả về [2]

• Từ phương thức chính, hãy làm như sau -

• sắp xếp danh sách A

• B:=danh sách các phần tử ở dạng (i, x, giới hạn) cho mỗi chỉ mục truy vấn i và các giá trị truy vấn x và giới hạn. Sau đó, sắp xếp nó dựa trên giới hạn

• (j, n, ans):=(0, kích thước của A, danh sách có kích thước giống như truy vấn, điền bằng -1)

• đối với mỗi chỉ số i và giá trị x và giới hạn trong B, thực hiện

  • while j

    • chèn (A [j])

    • j:=j + 1

  • nếu j khác 0 thì

    • ans [i]:=query (x)

• trả lại ans

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

[3, -1]