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

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:

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.

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

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

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:

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:

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).

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í .