Это популярный вопрос о кодировании, который задают многие компании.
Описание:
Учитывая двумерную сетку с 1 (суша) и 0 (вода), подсчитайте количество островов. Остров окружен водой и образован путем соединения соседних земель по горизонтали или вертикали. Вы можете предположить, что все четыре края сетки окружены водой.
Пример:
В этом примере у нас есть три отдельных острова, как показано ниже.
На первый взгляд, мы можем просто перебирать матрицу, пока не встретим остров, и использовать DFS на этом острове, чтобы найти его соседей.
Давайте посмотрим, как это выглядит:
- Установите переменную (total), в которой будет храниться количество островов, с которыми мы столкнулись изначально.
- Повторите матрицу, и как только мы встретим остров, мы обновим нашу общую переменную и применим нашу вспомогательную функцию DFS.
- Верните нашу итоговую переменную.
Как выглядит наша функция DFS?
- Поскольку наша функция DFS будет использоваться рекурсивно, нам сначала нужно проверить, что мы все еще находимся в границах сетки и что текущая точка, в которой мы находимся, все еще является частью острова.
- Затем нам нужно будет отметить каждый остров, который мы посетили, чтобы предотвратить дублирование подсчета.
- Затем мы можем рекурсивно применить нашу функцию DFS к соседним островам, которые находятся выше, ниже, слева и справа от нашего текущего положения.
Вот реализация Javascript:
const visited = (i, j, grid) => { let height = grid.length; let width = grid[0].length; if (i < 0 || i === height || j < 0 || j === width || grid[i][j] !== '1') return; grid[i][j] = 'X'; visited(i + 1, j, grid); visited(i — 1, j, grid); visited(i, j + 1, grid); visited(i, j — 1, grid); }; const numIslands = (grid) => { let total = 0; for (let i = 0; i < grid.length; i++) { for (let j = 0; j < grid[i].length; j++) { if (grid[i][j] === “1”) { total += 1; visited(i, j, grid); } } } return total; };