Python程序：计算翻转列以匹配目标矩阵所需的最少操作次数

假设我们有两个矩阵 M 和 T，它们具有相同数量的行和列。现在假设有一种操作可以翻转矩阵中的特定列，使得所有 1 都转换为 0，所有 0 都转换为 1。如果我们可以免费重新排序矩阵的行，请找到将 M 转换为 T 所需的最少操作次数。如果没有解决方案，则返回 -1。

因此，如果输入类似于 M =

0
0
1
0
1
1

T =

0
1
1
0
1
1

则输出将为 1，因为首先重新排序行：

0
0
1
1
1
0

然后翻转第 1 列：

0
1
1
0
1
1

为了解决这个问题，我们将遵循以下步骤：

  • nums1 := 新列表，nums2 := 新列表

  • 对于矩阵中的每一行，执行：

    • ths := 0

    • 当行不为空时，执行：

      • ths := (ths * 2) + 行的最后一个元素，并删除行的最后一个元素

    • 将 ths 插入 nums1 的末尾

  • 对于目标矩阵中的每一行，执行：

    • ths := 0

    • 当行不为零时，执行：

    • ths := (ths * 2) + 行的最后一个元素，并删除行的最后一个元素

    • 将 ths 插入 nums2 的末尾

  • ret := 无穷大

  • 对于 nums1 中的每个数字，执行：

    • cts := 一个映射，包含 nums1 中的唯一元素及其频率

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

    • my_xor := num XOR nums2[0]

    • 对于 i 从 1 到 nums2 的大小，执行：

      • needed := my_xor XOR nums2[i]

      • 如果 cts[needed] 为零，则

        • 退出循环

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

      • 否则，

      • ret := ret 和 my_xor 的设置位数的最小值

      • 如果 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

更新于：2020年10月5日

浏览量：168

开启你的职业生涯

通过完成课程获得认证

开始学习
广告