Hợp nhất tế bào bằng Python

Giả sử chúng ta có một danh sách các số được gọi là ô; danh sách này đại diện cho kích thước của các ô khác nhau. Bây giờ, trong mỗi lần lặp, hai ô lớn nhất a và b tương tác theo các quy tắc sau:Vì vậy, Nếu a =b, chúng đều chết. Nếu không, hai ô hợp nhất và kích thước của chúng trở thành tầng của ((a + b) / 3). Chúng ta phải tìm kích thước của ô cuối cùng hoặc trả về -1 nếu không còn ô nào.

Vì vậy, nếu đầu vào là [20,40,40,30], thì đầu ra sẽ là 16, trong lần lặp đầu tiên, 40 và 40 sẽ chết, sau đó 20 và 30 trở thành tầng của ((20 + 30) / 3) =tầng 50/3 =16

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

• cells:=chuyển đổi từng giá trị của mảng ô thành âm

• tạo một đống với các ô

• trong khi các ô không trống, hãy làm -

  • xóa hai phần tử khỏi ô và chuyển đổi chúng thành phủ định một lần nữa, đồng thời gán chúng là phần tử đầu tiên và thứ hai liên tiếp

• nếu đầu tiên không bằng thứ hai, thì -

  • chèn phủ định của tầng (thứ nhất + thứ hai) / 3) vào heap

• trả về âm của ô [0] nếu ô có một số phần tử khác - 1

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

Ví dụ

from heapq import heapify, heappop, heappush
class Solution:
   def solve(self, cells):
      cells=[-x for x in cells]
      heapify(cells)
      while len(cells)>1:
         first,second = -heappop(cells), -heappop(cells)
         if first!=second:
            heappush(cells, -((first+second)//3))
      return -cells[0] if cells else -1
ob = Solution()
cells = [20,40,40,30]
print(ob.solve(cells))

Đầu vào

[20,40,40,30]

Đầu ra

16