สมมติว่ามีเมทริกซ์ M และเมทริกซ์เป้าหมาย T ที่มีจำนวนแถวและคอลัมน์เท่ากัน การดำเนินการคือพลิกคอลัมน์หนึ่งในเมทริกซ์ ทำให้ 1 กลายเป็น 0 และ 0 กลายเป็น 1 หากเราสามารถเรียงลำดับแถวได้อย่างอิสระ หาจำนวนการดำเนินการน้อยสุดเพื่อทำให้ M กลายเป็น T หากไม่มีวิธีคืนค่า -1
เช่น ถ้าอินพุต M = [[0,0],[1,0],[1,1]] T = [[0,1],[1,0],[1,1]] ผลลัพธ์จะเป็น 1
ขั้นตอนการแก้ปัญหา
- nums1, nums2 := รายการใหม่
- สำหรับแต่ละแถวใน matrix แปลงแถวเป็นตัวเลขฐานสอง (pop จากท้าย) ใส่เข้า nums1
- สำหรับแต่ละแถวใน target แปลงเป็นตัวเลขฐานสอง ใส่เข้า nums2
- ret := infinity
- สำหรับแต่ละ num ใน nums1
- cts := Counter(nums1), cts[num] -= 1
- my_xor := num XOR nums2[0]
- for i ใน 1 ถึง len(nums2)-1
- needed := my_xor XOR nums2[i]
- ถ้า cts[needed] == 0 break
- cts[needed] -= 1
- มิฉะนั้น ret := min(ret, จำนวนบิต 1 ใน my_xor)
- คืนค่า ret ถ้า ret != infinity มิฉะนั้น -1
ตัวอย่างโค้ด
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))
อินพุต
M = [[0, 0],[1, 0],[1, 1]] T = [[0, 1],[1, 0],[1, 1]]
เอาต์พุต
1
