[リートコード] 0200. 島の数

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

中くらい

与えられた xn 2D バイナリグリッド グリッド の地図を表します '1's（土地）と '0's（水）、戻る 島の数.

アン島は水に囲まれており、隣接する土地を水平または垂直に接続することによって形成されます。グリッドの 4 つの端すべてが水に囲まれていると考えることができます。

例 1:

入力： グリッド = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1 ","1","0","0","0"], ["0","0","0","0","0"] ]
出力： 1

例 2:

入力： グリッド = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0 ","0","1","0","0"], ["0","0","0","1","1"] ]
出力： 3

制約:

m==グリッドの長さ
n == グリッド[i].length
1 <= m、n <= 300
グリッド[i][j] は '0' または '1'.

パイソン

				
					# 時間計算量: O(m*n) # 空間計算量: import List クラスの入力による O(m*n) 解決策: def dfs(self, Grid: List[List[str]], r: int, c: int) -> なし: nR = len(grid) nC = len(grid[0]) Grid[r][c] = '0' if r - 1 >= 0かつgrid[r - 1][c] == " 1": self.dfs(grid, r - 1, c) if r + 1 < nR および Grid[r + 1][c] == "1": self.dfs(grid, r + 1, c) if c - 1 >= 0 および Grid[r][c - 1] == "1": self.dfs(grid, r, c - 1) if c + 1 < nC および Grid[r][c + 1] == "1": self.dfs(grid, r, c + 1) def numIslands(self, Grid: List[List[str]]) -> int: グリッドでない場合: 範囲内の r に対して 0 を返す numIslands = 0 (len(grid)): for c in range(len(grid[0])): Grid[r][c] == '1' の場合: numIslands += 1 self.dfs(grid, r, c) return numIslands グリッド = [ ["1", "1", "0", "0", "0"], ["1", "1", "0", "0", "0"], [" 0", "0", "1", "0", "0"], ["0", "0", "0", "1", "1"] ] print(Solution().numIslands(グリッド））

中くらい

パイソン

関連記事