程序计算最小操作数以翻转列以在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：=（ths * 2）+行中的最后一个元素，并删除行中的最后一个元素
：= 0
当行不为空时，执行
在nums1的末尾插入
对于目标中的每一行，执行
：= 0
当row非零时，执行
ths：=（ths * 2）+行中的最后一个元素，并删除行中的最后一个元素
在nums2的末尾插入
ret：=无穷大
对于nums1中的每个num，执行
需要：= my_xor XOR nums2 [i]
如果cts [needed]为零，则
除此以外，
ret：=最小最小值，以及my_xor的置位位数
如果ret与无穷大不同，则返回ret，否则返回-1
从循环中出来
cts [需要]：= cts [需要]-1
cts：=包含nums1中不同元素及其频率的映射
cts [num]：= cts [num]-1
my_xor：= num XOR nums2 [0]
对于范围1到nums2的i
让我们看下面的实现以更好地理解-
示例
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中成为目标 的全部内容， 来源链接： utcz.com/z/316700.html
