[リートコード] 0305. 島の数 II

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

難しい

空の 2D バイナリグリッドが与えられます。 グリッド サイズの xnグリッドはマップを表します。 0は水を表し、 1は、最初はすべてのセルを表します。 グリッド 水のセルです（つまり、すべてのセルは 0さん）。

与えられた配列の位置にある水を土地に変える土地の追加操作を実行する場合があります。 ポジション どこ 位置[i] = [ _ri , c _i ] 位置です (r _i , c _i ) どの時点で操作すべきか ^私は 手術。

戻る 整数の配列 答え どこ 答え[i] セルを回転させた後の島の数です (r _i , c _i ) 土地に入る.

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

例 1:

入力： m = 3、n = 3、位置 = [[0,0],[0,1],[1,2],[2,1]]
出力： [1,1,2,3]
説明：
最初は、2D グリッドが水で満たされています。 - オペレーション #1: addLand(0, 0) は、grid[0][0] の水を土地に変えます。 - オペレーション #2: addLand(0, 1)。グリッド[0][1]の水を陸地に変えます。まだ 1 つの島があります。 - オペレーション #3: addLand(1, 2) は、グリッド[1][2]の水を陸地に変えます。 - 操作 #4: addLand(2, 1) は、grid[2][1] の水を陸地に変えます。

例 2:

入力： m = 1、n = 1、位置 = [[0,0]]
出力： [1]

制約:

1 <= m、n、positions.length <= 10 ⁴
1 <= m * n <= 10 ⁴
位置[i].length == 2
0 <= r _i < m
0 <= c _i < n

フォローアップ： 時間の複雑さで解決できますか O(k log(mn))、どこ k == 位置.長さ?

パイソン

				
					# 時間計算量: O(m*n) # 空間計算量: インポート リスト クラスの入力による O(m*n) 解決策: class UnionFind: def __init__(self, size): self.rep = [i for i in range(size) )] self.rank = [0] * サイズ self.count = 0 def find(self, node): if node != self.rep[node]: self.rep[node] = self.find(self.rep[ノード]) return self.rep[ノード] def Union(self, ノード1, ノード2): rep1 = self.find(node1) rep2 = self.find(node2) if rep1 != rep2: if self.rank[rep1] > self.rank[rep2]: self.rep[rep2] = rep1 elif self.rank[rep2] < self.rank[rep1]: self.rep[rep1] = rep2 else: self.rep[rep2] = rep1 self。 Rank[rep1] += 1 self.count -= 1 def numIslands2(self, m: int, n: int, Positions: List[List[int]]) -> List[int]: uf = self.UnionFind(m) * n) res = [] land_map = set() の位置の行、列: land_map の (行、列) の場合: res.append(uf.count) 続行 land_map.add((行、列)) uf.count += 1 for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]: r, c = row + i,col + j if r < 0 または c < 0 または r >= m または c >= n: land_map 内の (r, c) の場合は続行: uf.union(row * n +col, r * n + c) res.append(uf.count) return res m = 3 n = 3 位置 = [[0, 0], [0, 1], [1, 2], [2, 1]] print(Solution().numIslands2(m, n, Positions))

難しい

パイソン

関連記事