[リートコード] 0417. 太平洋大西洋の水の流れ

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

中くらい

があります xn 両方に接する長方形の島。 太平洋 そして 大西洋.ザ 太平洋 島の左端と上端に触れ、 大西洋 島の右端と下端に触れます。

島は正方形のセルのグリッドに分割されています。 xn 整数行列 ハイツ どこ 高さ[r][c] を表します 海抜の高さ 座標のセルの (r,c).

島にはたくさんの雨が降り、隣接するセルの高さが高ければ、雨水は真北、南、東、西の隣接するセルに流れることができます。以下現在のセルの高さ。水は海に隣接するどのセルからでも海に流れ込むことができます。

戻る ある 2Dリスト グリッド座標の 結果 どこ 結果[i] = [ _ri , c _i ] 雨水がセルから流れる可能性があることを示します (r _i , c _i ) に両方太平洋と大西洋.

例 1:

入力： 高さ = [[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]]
出力： [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
説明： 以下に示すように、次のセルは太平洋と大西洋に流れることができます: [0,4]: [0,4] -> 太平洋 [0,4] -> 大西洋 [1,3]: [1,3] ] -> [0,3] -> 太平洋 [1,3] -> [1,4] -> 大西洋 [1,4]: [1,4] -> [1,3] -> [0 ,3] -> 太平洋 [1,4] -> 大西洋 [2,2]: [2,2] -> [1,2] -> [0,2] -> 太平洋 [2,2] -> [2,3] -> [2,4] -> 大西洋 [3,0]: [3,0] -> 太平洋 [3,0] -> [4,0] -> 大西洋 [ 3,1]: [3,1] -> [3,0] -> 太平洋 [3,1] -> [4,1] -> 大西洋 [4,0]: [4,0] ->太平洋 [4,0] -> 大西洋 これらのセルが太平洋および大西洋に流れる可能性のある経路は他にもあることに注意してください。

例 2:

入力： 高さ = [[1]]
出力： [[0,0]]
説明： 水は唯一のセルから太平洋と大西洋に流れることができます。

制約:

m == 高さ.長さ
n == 高さ[r].length
1 <= m、n <= 200
0 <= 高さ[r][c] <= 10 ⁵

パイソン

				
					# 時間計算量: O(m*n) # 空間計算量: O(m*n) コレクションから import deque 入力からインポート リスト クラス 解決策: def pacificAtlantic(self, heights: List[List[int]]) -> List[ List[int]]: ROW = len(heights) COL = len(heights[0]) ROW または COL でない場合: return [] 方向 = [(1, 0), (-1, 0), (0, 1), (0, -1)] pacificQueue = deque() atlanticQueue = deque() for i in range(ROW): pacificQueue.append((i, 0)) atlanticQueue.append((i, COL - 1)) for i in range(COL): pacificQueue.append((0, i)) atlanticQueue.append((ROW - 1, i)) def bfs(queue):到達可能 = set() while キュー: currX、currY = queue。 Popleft() reverseable.add((currX, currY)) for (dX, dY) の方向: nextX = currX + dX nextY = currY + dY if nextX < 0 または nextX >= ROW または nextY < 0 または nextY >= COL : (nextX, nextY) が到達可能な場合は続行します: heights[currX][currY] > heights[nextX][nextY] の場合は続行します: 続行 queue.append((nextX, nextY)) return rereable pacificSet = bfs(pacificQueue) atlanticSet = bfs(atlanticQueue) return list(pacificSet.intersection(atlanticSet)) height = [[1, 1], [1, 1], [1, 1]] print(Solution().pacificAtlantic(heights))

中くらい

パイソン

関連記事