โปรแกรมนับจำนวนการดำเนินการขั้นต่ำเพื่อพลิกคอลัมน์เพื่อสร้างเป้าหมายใน Python

สมมติว่าเรามีเมทริกซ์ M และเมทริกซ์เป้าหมาย T ที่มีจำนวนแถวและคอลัมน์เท่ากัน สมมติว่าการดำเนินการที่เราพลิกคอลัมน์เฉพาะในเมทริกซ์เพื่อให้ 1s ทั้งหมดถูกแปลงเป็น 0 และ 0 ทั้งหมดจะถูกแปลงเป็น 1s ดังนั้น หากเราสามารถจัดลำดับแถวเมทริกซ์ใหม่ได้ฟรี ให้หาจำนวนการดำเนินการขั้นต่ำที่จำเป็นในการเปลี่ยน M เป็น T หากไม่มีวิธีแก้ปัญหา ให้คืนค่า -1

ดังนั้นหากอินพุตเป็น M =

T =

จากนั้นผลลัพธ์จะเป็น 1 อันดับแรกให้เรียงลำดับแถวใหม่เป็น−

แล้วพลิกคอลัมน์ 1 ไปที่−

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-

• nums1 :=รายการใหม่ nums2 :=รายการใหม่

• สำหรับแต่ละแถวในเมทริกซ์ ทำ

  • ths :=0

  • ขณะที่แถวไม่ว่างให้ทำ

    • ths :=(ths*2) + องค์ประกอบสุดท้ายจากแถว และลบองค์ประกอบสุดท้ายของแถว

  • ใส่ ths ที่ท้าย nums1

• สำหรับแต่ละแถวในเป้าหมาย ทำ

  • ths :=0

  • ในขณะที่แถวไม่เป็นศูนย์ให้ทำ

  • ths :=(ths*2) + องค์ประกอบสุดท้ายจากแถว และลบองค์ประกอบสุดท้ายของแถว

  • ใส่ ths ที่ท้าย nums2

• ret:=อินฟินิตี้

• สำหรับแต่ละ num ใน nums1 ให้ทำ

  • cts :=แผนที่ที่มีองค์ประกอบต่างกันใน nums1 และความถี่

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

  • my_xor :=num XOR nums2[0]

  • สำหรับฉันอยู่ในช่วง 1 ถึงขนาด nums2 ทำ

    • ต้องการ :=my_xor XOR nums2[i]

    • ถ้า cts[จำเป็น] เป็นศูนย์ แล้ว

      • ออกจากวง

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

    • มิฉะนั้น

    • ret:=ขั้นต่ำของ ret และจำนวน set bit ของ my_xor

    • return ret หาก ret ไม่เหมือนกับอินฟินิตี้มิฉะนั้น -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