Cómo resolver el número de islas de las preguntas de Blind 75 LeetCode by@rakhmedovrs
85,953 lecturas

Cómo resolver el número de islas de las preguntas de Blind 75 LeetCode

2022/08/20
7 min
por @rakhmedovrs 85,953 lecturas
tldt arrow
ES
Read on Terminal Reader

Demasiado Largo; Para Leer

Dada una cuadrícula binaria 2D m x n que representa un mapa de '1's (tierra) y '0's (agua), devuelve el número de islas. Una isla está rodeada de agua y se forma al conectar tierras adyacentes horizontal o verticalmente. Puede suponer que los cuatro bordes de la cuadrícula están rodeados de agua.
featured image - Cómo resolver el número de islas de las preguntas de Blind 75 LeetCode
Ruslan Rakhmedov HackerNoon profile picture

@rakhmedovrs

Ruslan Rakhmedov

Senior Software Engineer. As a hobby I do competitive programming...

Aprender Mas
LEARN MORE ABOUT @RAKHMEDOVRS'S EXPERTISE AND PLACE ON THE INTERNET.
react to story with heart

Descripción de la tarea:

Dada una grid binaria mxn 2D que representa un mapa de '1' (tierra) y '0' (agua), devuelva el número de islas .

Una isla está rodeada 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:

 Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1

Ejemplo 2:

 Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3

Restricciones:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] es '0' o '1' .

Razonamiento:

Al principio, la tarea parece ser difícil, excepto que ya sabe qué hacer después de ver este problema antes. No consideramos ese escenario aquí, tratemos el problema como si lo viéramos por primera vez. Para que sea más fácil de entender, usemos una forma más completa de describir el problema. Voy a usar una tabla simple en la que las celdas azules representarán el agua y las celdas verdes representarán la tierra. 0 en la cuadrícula dada representa el agua y 1 representa la tierra. Vamos a visualizar los ejemplos que nos dan:

Visualización del primer ejemplo

Visualización del primer ejemplo

Visualización del segundo ejemplo

Visualización del segundo ejemplo

La respuesta para la primera cuadrícula es 1, mientras que la segunda es 3. La razón es que la tierra debe estar conectada vertical u horizontalmente. Visualicemos esto también.

La cuadrícula izquierda tiene 1 isla y la derecha tiene 5

La cuadrícula izquierda tiene 1 isla y la derecha tiene 5

Como siempre hago, le sugiero que comience con ejemplos extremadamente simples, tontos si se quiere.

Grilla vacía o grilla con 0 islas

Grilla vacía o grilla con 0 islas

El ejemplo anterior no tiene ninguna tierra, por lo que la respuesta es 0 isla.

Cuadrícula con 7 islas

Cuadrícula con 7 islas

El ejemplo anterior tiene 7 islas. ¿Cómo podemos decir eso programáticamente? Necesitamos iterar a través de toda la cuadrícula y contar cuántas veces vemos tierra. Eso es todo. Suena fácil, ¿verdad? Pero pongamos otro ejemplo:

Cuadrícula con 6 islas

Cuadrícula con 6 islas

Si usamos la misma lógica que usamos en los ejemplos anteriores, obtenemos la respuesta 8, pero es la incorrecta. La respuesta correcta es 6 islas. El principal inconveniente del enfoque anterior es que contamos cada pedazo de tierra, no las islas. Resulta que es el problema principal que debemos resolver para resolver el problema dado.


Solución:

El enfoque general consta de 2 pasos generales.

El primer paso es que necesitamos recorrer toda la cuadrícula celda por celda. No hay forma de que podamos responder la pregunta principal sin hacerlo.

 public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int islands = 0; for (int row = 0; row < grid.length; row++) { for (int column = 0; column < grid[row].length; column++) { if (grid[row][column] == '1') { islands += //some logic here } } } return islands; }

Comenzamos desde la esquina superior izquierda e iteramos a través de cada fila, cuando no podemos continuar, saltamos a la siguiente fila.

Es hora de discutir la lógica detrás de cómo calculamos cuántas islas tenemos. A estas alturas debería ser obvio que comenzamos explorando la primera pieza de cualquier isla. Lo agregamos a la respuesta como 1 isla que acabamos de explorar. Lo siguiente que debemos hacer es evitar que se cuenten los terrenos adjuntos, ya que incrementamos el contador general. ¿Como lo podemos hacer?

La respuesta es simple. BORRÉMOSLO. Si, lo tienes bien. Una vez que descubrimos el primer pedazo de tierra, comenzamos el procedimiento de borrado.

 private int eraseLand(char[][] grid, int row, int column) { if (row < 0 || column < 0 || row >= grid.length || column >= grid[row].length || grid[row][column] == '0') { return 0; } grid[row][column] = '0'; // going up eraseLand(grid, row - 1, column); // going down eraseLand(grid, row + 1, column); // going left eraseLand(grid, row, column - 1); // going right eraseLand(grid, row, column + 1); return 1; }

Para cada celda, borramos su tierra estableciendo el valor de la celda en 0, y desde esa celda, continuamos explorando la cuadrícula yendo hacia la izquierda, derecha, arriba y abajo. Eventualmente, exploraremos todos los terrenos adjuntos.

Aquí está el código fuente completo de la solución:

 public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int islands = 0; for (int row = 0; row < grid.length; row++) { for (int column = 0; column < grid[row].length; column++) { if (grid[row][column] == '1') { islands += eraseLand(grid, row, column); } } } return islands; } private int eraseLand(char[][] grid, int row, int column) { if (row < 0 || column < 0 || row >= grid.length || column >= grid[row].length || grid[row][column] == '0') { return 0; } grid[row][column] = '0'; // going up eraseLand(grid, row - 1, column); // going down eraseLand(grid, row + 1, column); // going left eraseLand(grid, row, column - 1); // going right eraseLand(grid, row, column + 1); return 1; }

Como mencioné anteriormente, debemos explorar toda la cuadrícula, cuesta O (filas * columnas) + si consideramos el peor de los casos como este:

Peor de los casos

Peor de los casos

Exploraremos la cuadrícula completa una vez más con la misma complejidad de tiempo de O (filas * columnas). Entonces, la complejidad del tiempo general es O (filas * columnas) + O (filas * columnas). Por reglas de notación O grande, podemos omitir una parte y la complejidad de tiempo resultante es O (filas * columnas).

Rendimiento de la solución

Rendimiento de la solución

Espero que este artículo lo ayude a comprender la lógica detrás de este problema y lo use para resolver otras tareas.

¡Te veo pronto!


También publicado aquí .

HISTORIAS RELACIONADAS

L O A D I N G
. . . comments & more!
Hackernoon hq - po box 2206, edwards, colorado 81632, usa