[Leetcode] 0417. Flujo de agua del Atlántico Pacífico

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

hay un xn isla rectangular que bordea tanto el Océano Pacífico y Océano Atlántico.El Océano Pacífico toca los bordes izquierdo y superior de la isla, y el Océano Atlántico toca los bordes derecho e inferior de la isla.

La isla está dividida en una cuadrícula de celdas cuadradas. xn matriz entera alturas dónde alturas[r][c] representa el altura sobre el nivel del mar de la celda en la coordenada (r, c).

La isla recibe mucha lluvia y el agua de lluvia puede fluir a las celdas vecinas directamente al norte, sur, este y oeste si la altura de la celda vecina es menor o igual a La altura de la celda actual. El agua puede fluir desde cualquier celda adyacente a un océano hacia el océano.

Devolver a lista 2D de coordenadas de cuadrícula resultado dónde resultado[i] = [r _yo , c _yo ] denota que el agua de lluvia puede fluir desde la celda ( _ri , _ci ) a ambos los océanos pacífico y atlántico.

Ejemplo 1:

Aporte: alturas = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5] ,[5,1,1,2,4]]
Producción: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explicación: Las siguientes celdas pueden fluir hacia los océanos Pacífico y Atlántico, como se muestra a continuación: [0,4]: [0,4] -> Océano Pacífico [0,4] -> Océano Atlántico [1,3]: [1,3 ] -> [0,3] -> Océano Pacífico [1,3] -> [1,4] -> Océano Atlántico [1,4]: [1,4] -> [1,3] -> [0 ,3] -> Océano Pacífico [1,4] -> Océano Atlántico [2,2]: [2,2] -> [1,2] -> [0,2] -> Océano Pacífico [2,2] -> [2,3] -> [2,4] -> Océano Atlántico [3,0]: [3,0] -> Océano Pacífico [3,0] -> [4,0] -> Océano Atlántico [ 3,1]: [3,1] -> [3,0] -> Océano Pacífico [3,1] -> [4,1] -> Océano Atlántico [4,0]: [4,0] -> Océano Pacífico [4,0] -> Océano Atlántico Tenga en cuenta que existen otros caminos posibles para que estas células fluyan hacia los océanos Pacífico y Atlántico.

Ejemplo 2:

Aporte: alturas = [[1]]
Producción: [[0,0]]
Explicación: El agua puede fluir desde la única celda hacia los océanos Pacífico y Atlántico.

Restricciones:

m == alturas.longitud
n == alturas[r].longitud
1 <= m, n <= 200
0 <= alturas[r][c] <= 10 ⁵

Pitón

				
					Complejidad del tiempo de #: O(m*n) Complejidad del espacio de #: O(m*n) de colecciones importar deque de escribir importar Clase de lista Solución: def pacificAtlantic(self, heights: List[List[int]]) -> List[ Lista[int]]: FILA = len(alturas) COL = len(alturas[0]) si no es FILA o no COL: devuelve [] direcciones = [(1, 0), (-1, 0), (0, 1), (0, -1)] pacificQueue = deque() atlanticQueue = deque() para i en el rango(ROW): pacificQueue.append((i, 0)) atlanticQueue.append((i, COL - 1)) para i en rango(COL): pacificQueue.append((0, i)) atlanticQueue.append((ROW - 1, i)) def bfs(cola): alcanzable = set() mientras que cola: currX, currY = cola. popleft() alcanzable.add((currX, currY)) para (dX, dY) en direcciones: nextX = currX + dX nextY = currY + dY si nextX < 0 o nextX >= FILA o nextY < 0 o nextY >= COL : continuar si (nextX, nextY) es alcanzable: continuar si alturas[currX][currY] > alturas[nextX][nextY]: continuar queue.append((nextX, nextY)) devolver alcanzable pacificSet = bfs(pacificQueue) atlanticSet = bfs(atlanticQueue) return list(pacificSet.intersection(atlanticSet)) alturas = [[1, 1], [1, 1], [1, 1]] print(Solution().pacificAtlantic(alturas))

Medio

Pitón

Artículos relacionados