Теория, подготовка к интервью и курсы для PHP разработчиков
YeaHub — это платформа для IT-специалистов, объединяющая обучение, карьерный рост, развитие и сообщество единомышленников.
Платформа: https://yeahub.ru
Для связи: @ruslan_kuyanets
Post #178
82
#ЛитКод
Задача: 711. Number of Distinct Islands II
Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов.
Пример:
👨💻 Алгоритм:
1⃣Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова.
2⃣Нормализуйте форму острова, применив все возможные повороты и отражения, чтобы найти каноническую форму.
3⃣Используйте множество для хранения всех уникальных канонических форм и верните размер этого множества.
😎 Решение:
👉Новости 👉База вопросов
Задача: 711. Number of Distinct Islands II
Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов.
Пример:
Input: grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]
Output: 1
👨💻 Алгоритм:
1⃣Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова.
2⃣Нормализуйте форму острова, применив все возможные повороты и отражения, чтобы найти каноническую форму.
3⃣Используйте множество для хранения всех уникальных канонических форм и верните размер этого множества.
😎 Решение:
function numDistinctIslands2($grid) {
$uniqueIslands = [];
for ($i = 0; $i < count($grid); $i++) {
for ($j = 0; $j < count($grid[0]); $j++) {
if ($grid[$i][$j] == 1) {
$shape = [];
dfs($grid, $i, $j, $i, $j, $shape);
$uniqueIslands[normalize($shape)] = true;
}
}
}
return count($uniqueIslands);
}
function dfs(&$grid, $i, $j, $baseI, $baseJ, &$shape) {
if ($i < 0 || $i >= count($grid) || $j < 0д Задача
:
711. Number of Di$grid[$i][$j]
== 0) {
return;
}
$grid[$i][$j] = 0;
$shape[] = [$i - $baseI, $j - $baseJ];
dfs($grid, $i + 1, $j, $baseI, $baseJ, $shape);
dfs($grid, $i - 1, $j, $baseI, $baseJ, $shape);
dfs($grid, $i, $j + 1, $baseI, $baseJ, $shape);
dfs($grid, $i, $j - 1, $baseI, $baseJ, $shape);
}
function normalize($shape) {
$shapes = array_fill(0, 8, []);
foreach ($shape as $p) {
$x = $p[0];
$y = $p[1];
$shapes[0][] = [$x, $y];
$shapes[1][] = [$x, -$y];
$shapes[2][] = [-$x, $y];
$shapes[3][] = [-$x, -$y];
$shapes[4][] = [$y, $x];
$shapes[5][] = [$y, -$x];
$shapes[6][] = [-$y, $x];
$shapes[7][] = [-$y, -$x];
}
foreach ($shapes as &$s) {
sort($s);
}
$minShape = implode(",", array_map(function($p) { return implode(",", $p); }, $shapes[0]));
foreach ($shapes as $s) {
$sStr = implode(";", array_map(function($p) { return implode(",", $p); }, $s));
$minShape = min($minShape, $sStr);
}
return $minShape;
}👉Новости 👉База вопросов
