力扣第 827 题
题目
给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后，grid 中最大的岛屿面积是多少？
岛屿 由一组上、下、左、右四个方向相连的 1 形成。
示例 1:
输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
示例 2:
输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。
示例 3:
输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。
提示：
n == grid.lengthn == grid[i].length1 <= n <= 500grid[i][j] 为 0 或 1
分析
- 先统计所有岛屿面积
- 遍历格子 0，将相邻的岛屿面积相加即可，注意去重
- 需要统计岛屿面积，并维护每个格子所属岛屿，可以用并查集
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
def find(x):
if f[x]!=x:
f[x] = find(f[x])
return f[x]
def union(x,y):
f[find(x)] = find(y)
n = len(grid)
f = list(range(n*n))
for i,j in product(range(n), range(n)):
if grid[i][j]:
if i and grid[i-1][j]:
union(i*n+j,i*n-n+j)
if j and grid[i][j-1]:
union(i*n+j,i*n+j-1)
ct = Counter(find(i*n+j) for i in range(n) for j in range(n) if grid[i][j])
res = max(ct.values(),default=0)
for i,j in product(range(n), range(n)):
if not grid[i][j]:
vis = set()
for x,y in [(i,j-1),(i,j+1),(i-1,j),(i+1,j)]:
if 0<=x<n and 0<=y<n and grid[x][y]:
vis.add(find(x*n+y))
res = max(res, 1+sum(ct[p] for p in vis))
return res
|
1360 ms