Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm phòng gần nhất từ ​​các truy vấn bằng Python

Giả sử có một mảng được gọi là phòng. trong đó các phòng [i] chứa một cặp [roomId_i, size_i] biểu thị một phòng có id là roomId_i và kích thước là size_i. Tất cả các số phòng đều khác nhau. Chúng ta cũng có một truy vấn mảng khác, trong đó các truy vấn [j] chứa một cặp [favourite_j, minSize_j]. Câu trả lời cho truy vấn thứ j là id số phòng của một phòng như vậy -

  • Phòng có kích thước ít nhất là minSize_j và

  • | id - favourite_j | được thu nhỏ.

Bây giờ, nếu có sự ràng buộc về sự khác biệt tuyệt đối, thì hãy sử dụng phòng có id nhỏ nhất. Nếu không có phòng như vậy, trả về -1. Vì vậy, chúng ta phải tìm một mảng được gọi là câu trả lời có độ dài bằng với các truy vấn, chứa câu trả lời cho truy vấn thứ j.

Vì vậy, nếu đầu vào giống như phòng =[[2,2], [1,2], [3,2]] truy vấn =[[3,1], [3,3], [5,2]], thì đầu ra sẽ là [3, -1, 3] vì

  • Đối với truy vấn [3,1]:Phòng 3 là gần nhất vì | 3 - 3 | =0 và kích thước của nó là 2 ít nhất là 1, vì vậy câu trả lời là 3.

  • Đối với truy vấn [3,3]:Không có phòng nào có kích thước ít nhất là 3, vì vậy câu trả lời là -1.

  • Đối với truy vấn [5,2]:Phòng 3 là gần nhất vì | 3 - 5 | =2, và kích thước của nó là 2 ít nhất là 2, vì vậy câu trả lời là 3.

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

  • phân loại phòng dựa trên kích thước, khi kích thước giống nhau thì dựa trên id phòng

  • queries =danh sách các cặp (qid, size, i) cho chỉ mục i và cặp (qid, size) trong các truy vấn

  • sắp xếp các truy vấn theo thứ tự ngược lại dựa trên kích thước, nếu kích thước giống nhau thì dựa trên ưu tiên, khi cả hai đều giống nhau thì dựa trên chỉ mục

  • ans:=một mảng có kích thước bằng với kích thước của các truy vấn và điền bằng -1

  • X:=một danh sách mới

  • đối với mỗi (qid, size, i) trong các truy vấn, hãy thực hiện

    • trong khi phòng và kích thước của mục cuối cùng của phòng> =kích thước, làm

      • (idr, p):=đã xóa phần tử cuối cùng khỏi phòng

      • sắp xếp X sau khi chèn idr

    • nếu X không trống thì

      • j:=index nơi chèn qid để X được sắp xếp lại

      • nếu j giống với kích thước của X thì

        • ans [i]:=phần tử cuối cùng của X

      • ngược lại khi j giống 0 thì

        • ans [i]:=X [0]

      • nếu không,

        • nếu X [j] - qid

          • ans [i]:=X [j]

        • nếu không,

          • ans [i]:=X [j-1]

  • trả lại ans

Ví dụ

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

import bisect
def solve(rooms, queries):
   rooms.sort(key = lambda x: (x[1], x[0]))
   queries = [(qid,size,i) for i, (qid, size) in enumerate(queries)]
   queries.sort(key = lambda x: (x[1], x[0], x[2]), reverse = True)
   ans = [-1] * len(queries)
   X = []
   for qid, size, i in queries:
      while rooms and rooms[-1][1] >= size:
         idr, _ = rooms.pop()
         bisect.insort(X, idr)
      if X:
         j = bisect.bisect(X, qid)
         if j == len(X):
            ans[i] = X[-1]
         elif j == 0:
            ans[i] = X[0]
         else:
            if X[j] - qid < qid - X[j-1]:
               ans[i] = X[j]
            else:
               ans[i] = X[j-1]
   return ans

rooms = [[2,2],[1,2],[3,2]]
queries = [[3,1],[3,3],[5,2]]
print(solve(rooms, queries))

Đầu vào 

[[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]]

Đầu ra 

[3, -1, 3]