행과 열의 수가 같은 행렬 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) + 행의 마지막 요소, 행의 마지막 요소 삭제
-
-
nums1의 끝에 th를 삽입
-
-
대상의 각 행에 대해 수행
-
ths :=0
-
행이 0이 아닌 동안 수행
-
ths :=(ths*2) + 행의 마지막 요소, 행의 마지막 요소 삭제
-
nums2의 끝에 삽입
-
-
ret:=무한대
-
nums1의 각 숫자에 대해 수행
-
cts :=nums1 및 해당 빈도에 고유한 요소가 있는 맵
-
cts[숫자] :=cts[숫자] - 1
-
my_xor :=num XOR nums2[0]
-
범위 1에서 nums2의 크기에 있는 i에 대해
-
필요 :=my_xor XOR nums2[i]
-
cts[needed]가 0이면
-
루프에서 나오다
-
cts[필요] :=cts[필요] - 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