用 Python 编写程序，计算翻转列以达到目标所需的最少操作数
假设我们有一个矩阵 M 和一个目标矩阵 T，它们的行数和列数相同。现在假设一个操作，我们翻转矩阵中的特定列，这样所有的 1 都会转换为 0，所有的 0 都会转换为 1。因此，如果我们可以免费重新排序矩阵行，请找到将 M 变成 T 所需的最少操作数。如果没有解决方案，则返回 -1。
因此，如果输入如下 M =
| 0 | 0 |
| 1 | 0 |
| 1 | 1 |
T =
| 0 | 1 |
| 1 | 0 |
| 1 |
然后输出将为 1，因为首先将行重新排序为−
| 0 | 0 |
| 1 | 1 |
| 1 | 0 |
然后将第 1 列翻转为−
| 0 | 1 |
| 1 | 0 |
| 1 |
为了解决这个问题，我们将遵循以下步骤−
nums1 := 一个新列表，nums2 := 一个新列表
对于矩阵中的每一行，执行
ths := 0
当行不为空时，执行
ths :=(ths*2) + 行中的最后一个元素，并删除行的最后一个元素
在 nums1 的末尾插入 ths
对于目标中的每一行，执行
ths := 0
当行非零时，执行
ths :=(ths*2) + 行中的最后一个元素，并删除行中的最后一个元素
在 nums2 的末尾插入 ths
ret:= infinity
对于 nums1 中的每个数字，执行
cts := 包含 nums1 中不同元素及其频率的映射
cts[num] := cts[num] - 1
my_xor := num XOR nums2[0]
对于范围从 1 到 nums2 的大小的 i，执行
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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
