Chương trình đếm số lượng thao tác tối thiểu để lật các cột để tạo mục tiêu trong Python

Giả sử chúng ta có một ma trận M và một ma trận mục tiêu T có cùng số hàng và số cột. Bây giờ, giả sử một phép toán trong đó chúng ta lật một cột cụ thể trong ma trận để tất cả các số 1 sẽ được chuyển thành 0 và tất cả các số 0 sẽ được chuyển thành 1s. Vì vậy, nếu chúng ta có thể sắp xếp lại các hàng ma trận miễn phí, hãy tìm số phép toán tối thiểu cần thiết để biến M thành T. Nếu không có lời giải, hãy trả về -1.

Vì vậy, nếu đầu vào là M =

T =

thì đầu ra sẽ là 1, vì lần đầu tiên sắp xếp lại các hàng thành−

Và sau đó lật cột 1 thành−

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

• nums1:=một danh sách mới, nums2:=một danh sách mới

• đối với mỗi hàng trong ma trận, thực hiện

  • ths:=0

  • trong khi hàng không trống, thực hiện

    • ths:=(ths * 2) + phần tử cuối cùng từ hàng và xóa phần tử cuối cùng của hàng

  • chèn ths vào cuối nums1

• đối với mỗi hàng trong mục tiêu, hãy thực hiện

  • ths:=0

  • trong khi hàng khác 0, thực hiện

  • ths:=(ths * 2) + phần tử cuối cùng từ hàng và xóa phần tử cuối cùng của hàng

  • chèn ths vào cuối nums2

• ret:=infinity

• đối với mỗi số trong nums1, hãy thực hiện

  • cts:=một bản đồ với các phần tử riêng biệt trong nums1 và tần số của chúng

  • cts [num]:=cts [num] - 1

  • my_xor:=num XOR nums2 [0]

  • đối với tôi trong phạm vi từ 1 đến kích thước của nums2, hãy thực hiện

    • cần thiết:=my_xor XOR nums2 [i]

    • nếu cts [cần] bằng 0 thì

      • đi ra từ vòng lặp

      • cts [cần]:=cts [cần] - 1

    • nếu không,

    • ret:=tối thiểu ret và số bit đã đặt của my_xor

    • trả về ret nếu ret không giống với vô cùng, nếu không thì -1

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

Ví dụ

class Solution:
   def solve(self, matrix, target):
      nums1 = []
      nums2 = []
      for row in matrix:
         ths = 0
         while row:
            ths = (ths<<1) + row.pop()
         nums1.append(ths)
      for row in target:
         ths = 0
         while row:
            ths = (ths<<1) + row.pop()
         nums2.append(ths)
      ret=float('inf')
      from collections import Counter
      for num in nums1:
         cts = Counter(nums1)
         cts[num] -= 1
         my_xor = num^nums2[0]
         for i in range(1,len(nums2)):
            needed = my_xor^nums2[i]
            if not cts[needed]:
               break
            cts[needed]-=1
         else:
            ret=min(ret,bin(my_xor).count('1'))
      return ret if ret!=float('inf') else -1
ob = Solution()
M = [
   [0, 0],
   [1, 0],
   [1, 1]
]
T = [
   [0, 1],
   [1, 0],
   [1, 1]
]
print(ob.solve(M,T))

Đầu vào

M = [[0, 0],[1, 0],[1, 1]] T = [[0, 1],[1, 0],[1, 1]]

Đầu ra

1