数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学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
广告