資料結構
網路
關係資料庫管理系統 (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
廣告