Chương trình tìm XOR tối đa với một phần tử từ mảng trong Python

Giả sử chúng ta có một mảng được gọi là nums với các giá trị không âm. Chúng ta cũng có một mảng khác được gọi là truy vấn trong đó các truy vấn [i] có một cặp (xi, mi). Câu trả lời của truy vấn thứ i là giá trị XOR theo từng bit tối đa của xi và bất kỳ phần tử nào của nums nhỏ hơn hoặc bằng mi. Nếu tất cả các phần tử trong num lớn hơn mi, thì câu trả lời là -1. Vì vậy, chúng tôi phải tìm một câu trả lời mảng trong đó câu trả lời sizeof giống với kích thước của truy vấn và câu trả lời [i] là câu trả lời cho truy vấn thứ i.

Vì vậy, nếu đầu vào giống như nums =[0,1,2,3,4] queries =[[3,1], [1,3], [5,6]], thì đầu ra sẽ là [3, 3,7], bởi vì

• 0 và 1 không lớn hơn 1. 0 XOR 3 =3 và 1 XOR 3 =2, ở đây lớn hơn của hai giá trị này là 3.

• 1 XOR 2 =3.

• 5 XOR 2 =7.

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

• m:=kích thước của nums

• n:=kích thước của các truy vấn

• queries =tạo một bộ ba (i, x, giới hạn) cho mỗi chỉ mục i và ghép nối (x, giới hạn) trong các truy vấn

• sắp xếp các truy vấn dựa trên giới hạn

• nums:=sắp xếp danh sách nums

• res:=một mảng có kích thước n và điền bằng 0

• đối với k trong phạm vi 31 đến 0, giảm đi 1, thực hiện

  • prefixes:=a new set

  • j:=0

  • đối với mỗi chỉ mục i và giá trị (x, giới hạn) trong các truy vấn, hãy thực hiện

    • while j <=m - 1 and nums [j] <=limit, do

      • chuyển nums [j] sang k bit bên phải và chèn vào tiền tố

      • j:=j + 1

    • nếu tiền tố trống, thì

      • res [i]:=-1

    • nếu không,

      • res [i] =thương số của res [i] / 2

      • target:=res [i] XOR 1

      • if (x sau khi chuyển k bit sang phải) mục tiêu XOR ở tiền tố, thì

        • res [i]:=target

• trả lại res

Ví dụ

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

def solve(nums, queries):
   m, n = len(nums), len(queries)
   queries = sorted(((i, x, limit) for i, (x, limit) in
enumerate(queries)), key=lambda x: x[2])
   nums = sorted(nums)
   res = [0] * n
   for k in range(31, -1, -1):
      prefixes = set()
      j = 0
      for i, x, limit in queries:
         while j <= m - 1 and nums[j] <= limit:
            prefixes.add(nums[j] >> k)
            j += 1
         if not prefixes:
            res[i] = -1
         else:
            res[i] <<= 1
            target = res[i] ^ 1
            if (x >> k) ^ target in prefixes:
               res[i] = target
   return res

nums = [0,1,2,3,4]
queries = [[3,1],[1,3],[5,6]]
print(solve(nums, queries))

Đầu vào

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

Đầu ra

[3, 3, 7]