← Static tasks

305. Number of Islands II

leetcode hard

#array#csharp#graph#hard#leetcode#matrix#search

Task

Дан пустой двумерный бинарный массив

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]

C# solution

matched/original
public class UnionFind {
    private int[] parent, rank;
    private int count;
    public UnionFind(int size) { parent = new int[size]; rank = new int[size]; Array.Fill(parent, -1); count = 0; }
    public void AddLand(int x) { if (parent[x] < 0) { parent[x] = x; count++; } }
    public bool IsLand(int x) { return parent[x] >= 0; }
    public int NumberOfIslands() { return count; }
    public int Find(int x) { return parent[x] != x ? parent[x] = Find(parent[x]) : x; }
    public void UnionSet(int x, int y) { int xset = Find(x), yset = Find(y); if (xset != yset) {
        if (rank[xset] < rank[yset]) parent[xset] = yset; else { parent[yset] = xset; if (rank[xset] == rank[yset]) rank[xset]++; } count--; } }
}
public class Solution {
    public IList<int> NumIslands2(int m, int n, int[][] positions) {
        var dsu = new UnionFind(m * n);
        int[] x = { -1, 1, 0, 0 }, y = { 0, 0, -1, 1 };
        var answer = new List<int>();
        foreach (var pos in positions) {
            int land = pos[0] * n + pos[1];
            dsu.AddLand(land);
            for (int i = 0; i < 4; ++i) {
                int nx = pos[0] + x[i], ny = pos[1] + y[i], neighbor = nx * n + ny;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && dsu.IsLand(neighbor)) dsu.UnionSet(land, neighbor);
            }
            answer.Add(dsu.NumberOfIslands());
        }
        return answer;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class UnionFind {
    private vector<int>& parent, rank;
    private int count;
    public UnionFind(int size) { parent = new int[size]; rank = new int[size]; Array.Fill(parent, -1); count = 0; }
    public void AddLand(int x) { if (parent[x] < 0) { parent[x] = x; count++; } }
    public bool IsLand(int x) { return parent[x] >= 0; }
    public int NumberOfIslands() { return count; }
    public int Find(int x) { return parent[x] != x ? parent[x] = Find(parent[x]) : x; }
    public void UnionSet(int x, int y) { int xset = Find(x), yset = Find(y); if (xset != yset) {
        if (rank[xset] < rank[yset]) parent[xset] = yset; else { parent[yset] = xset; if (rank[xset] == rank[yset]) rank[xset]++; } count--; } }
}
class Solution {
public:
    public vector<int> NumIslands2(int m, int n, int[][] positions) {
        var dsu = new UnionFind(m * n);
        vector<int>& x = { -1, 1, 0, 0 }, y = { 0, 0, -1, 1 };
        var answer = new List<int>();
        foreach (var pos in positions) {
            int land = pos[0] * n + pos[1];
            dsu.AddLand(land);
            for (int i = 0; i < 4; ++i) {
                int nx = pos[0] + x[i], ny = pos[1] + y[i], neighbor = nx * n + ny;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && dsu.IsLand(neighbor)) dsu.UnionSet(land, neighbor);
            }
            answer.push_back(dsu.NumberOfIslands());
        }
        return answer;
    }
}

Java solution

matched/original
class UnionFind {
    private int[] parent, rank;
    private int count;
    public UnionFind(int size) { parent = new int[size]; rank = new int[size]; Arrays.fill(parent, -1); count = 0; }
    public void addLand(int x) { if (parent[x] >= 0) return; parent[x] = x; count++; }
    public boolean isLand(int x) { return parent[x] >= 0; }
    public int numberOfIslands() { return count; }
    public int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; }
    public void unionSet(int x, int y) { int xset = find(x), yset = find(y); if (xset == yset) return;
        if (rank[xset] < rank[yset]) parent[xset] = yset; else { parent[yset] = xset; if (rank[xset] == rank[yset]) rank[xset]++; } count--; }
}

class Solution {
    public List<Integer> numIslands2(int m, int n, List<int[]> positions) {
        UnionFind dsu = new UnionFind(m * n);
        int[] x = {-1, 1, 0, 0}, y = {0, 0, -1, 1};
        List<Integer> answer = new ArrayList<>();
        for (int[] pos : positions) {
            int land = pos[0] * n + pos[1];
            dsu.addLand(land);
            for (int i = 0; i < 4; i++) {
                int nx = pos[0] + x[i], ny = pos[1] + y[i], neighbor = nx * n + ny;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && dsu.isLand(neighbor)) { dsu.unionSet(land, neighbor); }
            }
            answer.add(dsu.numberOfIslands());
        }
        return answer;
    }
}

JavaScript solution

matched/original
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
}

Python solution

matched/original
class UnionFind:
    def __init__(self, size): self.parent = [-1] * size; self.rank = [0] * size; self.count = 0
    def addLand(self, x): if self.parent[x] < 0: self.parent[x] = x; self.count += 1
    def isLand(self, x): return self.parent[x] >= 0
    def numberOfIslands(self): return self.count
    def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]); return self.parent[x]
    def unionSet(self, x, y): xset, yset = self.find(x), self.find(y); if xset == yset: return
        if self.rank[xset] < self.rank[yset]: self.parent[xset] = yset
        else: self.parent[yset] = xset; if self.rank[xset] == self.rank[yset]: self.rank[xset] += 1
        self.count -= 1

class Solution:
    def numIslands2(self, m, n, positions):
        dsu, answer, dirs, dirc = UnionFind(m * n), [], [-1, 1, 0, 0], [0, 0, -1, 1]
        for pos in positions:
            land = pos[0] * n + pos[1]
            dsu.addLand(land)
            for i in range(4):
                x, y = pos[0] + dirs[i], pos[1] + dirc[i]
                neighbor = x * n + y
                if 0 <= x < m and 0 <= y < n and dsu.isLand(neighbor):
                    dsu.unionSet(land, neighbor)
            answer.append(dsu.numberOfIslands())
        return answer

Go solution

matched/original
type UnionFind struct {
    parent []int
    rank   []int
    count  int
}

func NewUnionFind(size int) *UnionFind {
    uf := &UnionFind{parent: make([]int, size), rank: make([]int, size)}
    for i := range uf.parent { uf.parent[i] = -1 }
    return uf
}

func (uf *UnionFind) AddLand(x int) { if uf.parent[x] < 0 { uf.parent[x] = x; uf.count++ } }
func (uf *UnionFind) IsLand(x int) bool { return uf.parent[x] >= 0 }
func (uf *UnionFind) Find(x int) int { if uf.parent[x] != x { uf.parent[x] = uf.Find(uf.parent[x]) }; return uf.parent[x] }
func (uf *UnionFind) UnionSet(x, y int) { xset, yset := uf.Find(x), uf.Find(y)
    if xset != yset { if uf.rank[xset] < uf.rank[yset] { uf.parent[xset] = yset } else { uf.parent[yset] = xset
    if uf.rank[xset] == uf.rank[yset] { uf.rank[xset]++ } }; uf.count-- } }

func numIslands2(m int, n int, positions [][]int) []int {
    dsu, dirs, answer := NewUnionFind(m * n), [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}, []int{}
    for _, pos := range positions { land := pos[0]*n + pos[1]; dsu.AddLand(land)
        for _, d := range dirs { nx, ny, neighbor := pos[0]+d[0], pos[1]+d[1], (pos[0]+d[0])*n+(pos[1]+d[1])
            if nx >= 0 && nx < m && ny >= 0 && ny < n && dsu.IsLand(neighbor) { dsu.UnionSet(land, neighbor) } }
        answer = append(answer, dsu.count) }
    return answer
}

Explanation

Algorithm

Инициализация:

Создайте массивы x[] = { -1, 1, 0, 0 } и y[] = { 0, 0, -1, 1 }, которые будут использоваться для нахождения соседей ячейки.

Создайте экземпляр UnionFind, например, dsu(m * n). Инициализируйте всех родителей значением -1. Используйте объединение по рангу, инициализируйте все ранги значением 0. Наконец, инициализируйте count = 0.

Создайте список целых чисел answer, где answer[i] будет хранить количество островов, образованных после превращения ячейки positions[i] в сушу.

Обработка позиций:

Итерация по массиву 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.

Определение количества островов:

Выполните операцию numberOfIslands, которая возвращает количество островов, образованных после превращения позиции в сушу. Добавьте это значение в answer.

Верните answer.

😎