Сложность: medium
Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.
Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.
Верните максимальное возможное перекрытие.
Пример:
Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.
👨💻 Алгоритм:
1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.
2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).
3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.
😎 Решение:
class Solution:
def shiftAndCount(self, xShift, yShift, M, R):
leftShiftCount = 0
rightShiftCount = 0
rRow = 0
for mRow in range(yShift, len(M)):
rCol = 0
for mCol in range(xShift, len(M)):
if M[mRow][mCol] == 1 and M[mRow][mCol] == R[rRow][rCol]:
leftShiftCount += 1
if M[mRow][rCol] == 1 and M[mRow][rCol] == R[rRow][mCol]:
rightShiftCount += 1
rCol += 1
rRow += 1
return max(leftShiftCount, rightShiftCount)
def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
maxOverlaps = 0
for yShift in range(len(A)):
for xShift in range(len(A)):
maxOverlaps = max(maxOverlaps, self.shiftAndCount(xShift, yShift, A, B))
maxOverlaps = m
Ставь 👍 и забирай 📚 Базу знаний