🔒Открыть пост
и посмотреть медиа
Задача: 305. Number of Islands II
Сложность: hard
Дан пустой двумерный бинарный массив grid размером m x n. Этот массив представляет собой карту, где 0 означает воду, а 1 — сушу. Изначально все ячейки массива — водные (т.е. все ячейки содержат 0).
Вы можете выполнить операцию "добавить землю", которая превращает воду в указанной позиции в сушу. Вам дан массив positions, где positions[i] = [ri, ci] — позиция (ri, ci), в которой следует выполнить i-ю операцию.
Верните массив целых чисел answer, где answer[i] — количество островов после превращения ячейки (ri, ci) в сушу.
Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Вы можете считать, что все четыре края сетки окружены водой.
Пример:
Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]
👨💻 Алгоритм:
1⃣Инициализация:
Создайте массивы x[] = { -1, 1, 0, 0 } и y[] = { 0, 0, -1, 1 }, которые будут использоваться для нахождения соседей ячейки.
Создайте экземпляр UnionFind, например, dsu(m * n). Инициализируйте всех родителей значением -1. Используйте объединение по рангу, инициализируйте все ранги значением 0. Наконец, инициализируйте count = 0.
Создайте список целых чисел answer, где answer[i] будет хранить количество островов, образованных после превращения ячейки positions[i] в сушу.
2⃣Обработка позиций:
Итерация по массиву positions. Для каждой позиции в positions:
Выполните линейное отображение, чтобы преобразовать двумерную позицию ячейки в landPosition = position[0] * n + position[1].
Используйте операцию addLand(landPosition), чтобы добавить landPosition как узел в граф. Эта функция также увеличит count.
Итерация по каждому соседу позиции. Соседа можно определить с помощью neighborX = position[0] + x[i] и neighborY = position[1] + y[i], где neighborX — координата X, а neighborY — координата Y соседней ячейки. Выполните линейное отображение соседней ячейки с помощью neighborPosition = neighborX * n + neighborY. Теперь, если на neighborPosition есть суша, т.е. isLand(neighborPosition) возвращает true, выполните объединение neighborPosition и landPosition. В объединении уменьшите count на 1.
3⃣Определение количества островов:
Выполните операцию numberOfIslands, которая возвращает количество островов, образованных после превращения позиции в сушу. Добавьте это значение в answer.
Верните answer.
😎 Решение
class UnionFind {
constructor(size) { this.parent = Array(size).fill(-1); this.rank = Array(size).fill(0); this.count = 0 }
addLand(x) { if (this.parent[x] < 0) { this.parent[x] = x; this.count++ } }
isLand(x) { return this.parent[x] >= 0 }
find(x) { if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]); return this.parent[x] }
unionSet(x, y) { let xset = this.find(x), yset = this.find(y)
if (xset !== yset) { if (this.rank[xset] < this.rank[yset]) this.parent[xset] = yset
else { this.parent[yset] = xset; if (this.rank[xset] === this.rank[yset]) this.rank[xset]++ }; this.count-- } }
}
var numIslands2 = function(m, n, positions) {
let dsu = new UnionFind(m * n), dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]], answer = []
for (let pos of positions) { let land = pos[0] * n + pos[1]; dsu.addLand(land)
for (let [dx, dy] of dirs) { let nx = pos[0] + dx, ny = pos[1] + dy, neighbor = nx * n + ny
if (nx >= 0 && nx < m && ny >= 0 && ny < n && dsu.isLand(neighbor)) dsu.unionSet(land, neighbor) }
answer.push(dsu.count) }
return answer
}
Ставь 👍 и забирай 📚 Базу знаний
