[Leetcode] 0305. Número de islas II

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Duro

Se le proporciona una cuadrícula binaria 2D vacía red de tamaño xn.La cuadrícula representa un mapa donde 0Los representan agua y 1Los representan tierra. Inicialmente, todas las celdas de red son células de agua (es decir, todas las células son 0's).

Podemos realizar una operación de adición de tierra que convierte el agua en una posición en una tierra. Se le proporciona una matriz. posiciones dónde posiciones[i] = [r _i , c _i ] es la posición ( _ri , _ci ) en el que debemos operar el ^yo operación.

Devolver una serie de números enteros respuesta dónde respuesta[yo] es el número de islas después de girar la celda ( _ri , _ci ) en una tierra.

Un isla está rodeado de agua y se forma conectando tierras adyacentes horizontal o verticalmente. Puede suponer que los cuatro bordes de la cuadrícula están rodeados de agua.

Ejemplo 1:

Aporte: m = 3, n = 3, posiciones = [[0,0],[0,1],[1,2],[2,1]]
Producción: [1,1,2,3]
Explicación:
Inicialmente, la 2d cuadrícula se llena de agua - Operación #1: addLand(0, 0) convierte el agua en grid[0][0] en una isla. - Operación #2: addLand(0, 1). convierte el agua en la cuadrícula [0] [1] en una tierra. Todavía tenemos 1 isla - Operación #3: addLand(1, 2) convierte el agua en la cuadrícula [1] [2] en una tierra. - Operación #4: addLand(2, 1) convierte el agua en grid[2][1] en una tierra.

Ejemplo 2:

Aporte: m = 1, n = 1, posiciones = [[0,0]]
Producción: [1]

Restricciones:

1 <= m, n, posiciones.longitud <= 10 ⁴
1 <= metro * norte <= 10 ⁴
posiciones[i].longitud == 2
0 <= r _yo < m
0 <= c _yo < norte

Hacer un seguimiento: ¿Podrías resolverlo en complejidad temporal? O(k registro(mn)), dónde k == posiciones.longitud?

Pitón

				
					Complejidad de tiempo de #: O(m*n) Complejidad de espacio de #: O(m*n) al escribir import List clase Solución: clase UnionFind: def __init__(self, tamaño): self.rep = [i for i in range(size) )] self.rank = [0] * tamaño self.count = 0 def buscar(self, nodo): if node != self.rep[nodo]: self.rep[nodo] = self.find(self.rep[ nodo]) return self.rep[nodo] def unión(self, nodo1, nodo2): rep1 = self.find(nodo1) rep2 = self.find(nodo2) if rep1 != rep2: if self.rank[rep1] > self.rank[rep2]: self.rep[rep2] = rep1 elif self.rank[rep2] < self.rank[rep1]: self.rep[rep1] = rep2 else: self.rep[rep2] = rep1 self. rango[rep1] += 1 self.count -= 1 def numIslands2(self, m: int, n: int, posiciones: Lista[List[int]]) -> Lista[int]: uf = self.UnionFind(m * n) res = [] land_map = set() para fila, col en posiciones: if (fila, col) en land_map: res.append(uf.count) continuar land_map.add((fila, col)) uf.count += 1 para i, j en [(-1, 0), (1, 0), (0, 1), (0, -1)]: r, c = fila + i, col + j si r < 0 o c < 0 o r >= m o c >= n: continuar si (r, c) en land_map: uf.union(row * n + col, r * n + c) res.append(uf.count) return res m = 3 n = 3 posiciones = [[0, 0], [0, 1], [1, 2], [2, 1]] print(Solución().numIslands2(m, n, posiciones))

Duro

Pitón

Artículos relacionados