[Leetcode] 0200. Número de islas

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

Medio

dado un xn Cuadrícula binaria 2D red que representa un mapa de '1's (tierra) y '0's (agua), regresar el número de islas.

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: cuadrícula = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1 ","1","0","0","0"], ["0","0","0","0","0"] ]
Producción: 1

Ejemplo 2:

Aporte: cuadrícula = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0 ","0","1","0","0"], ["0","0","0","1","1"] ]
Producción: 3

Restricciones:

m==longitud.cuadrícula
n == cuadrícula[i].longitud
1 <= m, n <= 300
cuadrícula[i][j] es '0' o '1'.

Pitón

				
					Complejidad de tiempo de #: O(m*n) Complejidad de espacio de #: O(m*n) al escribir import List class Solución: def dfs(self, grid: List[List[str]], r: int, c: int) -> Ninguno: nR = len(grid) nC = len(grid[0]) grid[r][c] = '0' si r - 1 >= 0 y grid[r - 1][c] == " 1": self.dfs(grid, r - 1, c) si r + 1 < nR y grid[r + 1][c] == "1": self.dfs(grid, r + 1, c) si c - 1 >= 0 y grid[r][c - 1] == "1": self.dfs(grid, r, c - 1) if c + 1 < nC and grid[r][c + 1] == "1": self.dfs(grid, r, c + 1) def numIslands(self, grid: Lista[List[str]]) -> int: si no grid: devuelve 0 numIslands = 0 para r en el rango (len(grid)): para c en rango(len(grid[0])): si grid[r][c] == '1': numIslands += 1 self.dfs(grid, r, c) return numIslands grid = [ ["1", "1", "0", "0", "0"], ["1", "1", "0", "0", "0"], [" 0", "0", "1", "0", "0"], ["0", "0", "0", "1", "1"] ] print(Solución().numIslas( red))

Medio

Pitón

Artículos relacionados