114просмотров
7.9%от подписчиков
18 марта 2026 г.
statsScore: 125
Задача: 835. Image Overlap
Сложность: 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 { function shiftAndCount($xShift, $yShift, $M, $R) { $leftShiftCount = 0; $rightShiftCount = 0; $rRow = 0; for ($mRow = $yShift; $mRow < count($M); ++$mRow) { $rCol = 0; for ($mCol = $xShift; $mCol < count($M); ++$mCol) { if ($M[$mRow][$mCol] == 1 && $M[$mRow][$mCol] == $R[$rRow][$rCol]) { $leftShiftCount++; } if ($M[$mRow][$rCol] == 1 && $M[$mRow][$rCol] == $R[$rRow][$mCol]) { $rightShiftCount++; } $rCol++; } $rRow++; } return max($leftShiftCount, $rightShiftCount); } function largestOverlap($A, $B) { $maxOverlaps = 0; for ($yShift = 0; $yShift < count($A); ++$yShift) { for ($xShift = 0; $xShift < count($A); ++$xShift) { $maxOverlaps = max($maxOverlaps, $this->shiftAndCount($xShift, $yShift, $A, $B)); $maxOverlaps = max($maxOverlaps, $this->shiftAndCount($xShift, $yShift, $B, $A)); } } return $maxOverlaps; }
} Ставь 👍 и забирай 📚 Базу знаний