Алгоритмы и структуры данных88Количество островов

Прогресс0/166

01Массивы и слайсы

02Основы Go: типы, строки, структуры, generics

03Ошибки, defer, panic/recover

04Map

05Каналы и select

06Синхронизация: sync, atomic, data race

07Context

08Алгоритмы и структуры данных

09Паттерны конкурентности и лайвкодинг

10NoSQL и кеширование

11Архитектура, ООП, SOLID, паттерны

12Брокеры сообщений: Kafka, RabbitMQ, NATS

13Сеть и API: HTTP, gRPC, REST

Тренажёр166 задач⌘↵

Перейти к редактору ↓

Количество островов

Дана прямоугольная карта grid размера m × n: 1 — суша, 0 — вода. Остров — максимальная группа клеток суши, связанных по горизонтали или вертикали (по диагонали клетки не связаны). Посчитайте количество островов.

// NumIslands возвращает число островов на карте.
func NumIslands(grid [][]int) int

Примеры

NumIslands([][]int{
	{1, 1, 1, 1, 0},
	{1, 1, 0, 1, 0},
	{1, 1, 0, 0, 0},
	{0, 0, 0, 0, 0},
}) // 1
 
NumIslands([][]int{
	{1, 1, 0, 0, 0},
	{1, 1, 0, 0, 0},
	{0, 0, 1, 0, 0},
	{0, 0, 0, 1, 1},
}) // 3
 
NumIslands([][]int{{1, 0}, {0, 1}}) // 2 — диагональ не связывает

Ограничения: 0 <= m, n <= 1000, все строки одной длины. Время O(m·n). Карту можно изменять (на собесе лучше сказать об этом вслух). Учтите, что остров может состоять из миллиона клеток.

Устно: DFS рекурсией или BFS очередью — что выбрать и почему? Как решить, если карту менять нельзя?

Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.

Подсказки0/3

Сначала попробуй сам — подсказки не дают готовый ответ.

go test -race

solution.go

Загрузка редактора…

go test -race ./...Готов к запуску

Запусти тесты, чтобы увидеть вывод

Запусти тесты, чтобы увидеть вывод · ⌘↵

График