难度: Hard
原题连接
内容描述
We have a grid of 1s and 0s; the 1s in a cell represent bricks. A brick will not drop if and only if it is directly connected to the top of the grid, or at least one of its (4-way) adjacent bricks will not drop.
We will do some erasures sequentially. Each time we want to do the erasure at the location (i, j), the brick (if it exists) on that location will disappear, and then some other bricks may drop because of that erasure.
Return an array representing the number of bricks that will drop after each erasure in sequence.
Example 1:
Input:
grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]
Output: [2]
Explanation:
If we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop. So we should return 2.
Example 2:
Input:
grid = [[1,0,0,0],[1,1,0,0]]
hits = [[1,1],[1,0]]
Output: [0,0]
Explanation:
When we erase the brick at (1, 0), the brick at (1, 1) has already disappeared due to the last move. So each erasure will cause no bricks dropping. Note that the erased brick (1, 0) will not be counted as a dropped brick.
Note:
The number of rows and columns in the grid will be in the range [1, 200].
The number of erasures will not exceed the area of the grid.
It is guaranteed that each erasure will be different from any other erasure, and located inside the grid.
An erasure may refer to a location with no brick - if it does, no bricks drop.
思路 1 - 时间复杂度: O(row * col * Alpha(rowcol) + len(hits))- 空间复杂度: O(row * col)*****
直接抄的qjhdtc001
时间复杂度中的Alpha(row*col)指的是find函数的amortized time complexity
beats 28.78%
class UnionFind(object):
def __init__(self, n): # 初始化uf数组和组数目
self.uf = [i for i in range(n)]
self.size = [1] * n # 每个联通分量的size
def find(self, x): # 判断节点所属于的组
while x != self.uf[x]:
self.uf[x] = self.uf[self.uf[x]]
x = self.uf[x]
return self.uf[x]
def union(self, x, y): # 连接两个节点
x_root = self.find(x)
y_root = self.find(y)
if x_root == y_root:
return
if self.size[x_root] < self.size[y_root]:
x_root, y_root = y_root, x_root
self.uf[y_root] = x_root
self.size[x_root] += self.size[y_root]
self.size[y_root] = 0
class Solution:
def hitBricks(self, grid, hits):
"""
:type grid: List[List[int]]
:type hits: List[List[int]]
:rtype: List[int]
"""
row = len(grid)
col = len(grid[0]) if row else 0
# 这里的 +1 主要是多一个 0 来表示顶，所有的第一排的砖在unionfind的时候都会直接与这个0相连。
uf = UnionFind(row * col + 1)
# 首先把所有要打的砖块标记为2.
for i, j in hits:
if grid[i][j] == 1:
grid[i][j] = 2
# 然后对打掉后的数组中的砖块进行四个方向的union
for i in range(row):
for j in range(col):
if grid[i][j] == 1:
self.dfs(i, j, grid, uf)
# 这个cnt就是打完后一定会剩下的砖块数量.
cnt = uf.size[uf.find(0)]
res = []
# 反向遍历hits数组，一个一个复原回board
for i, j in hits[::-1]:
if grid[i][j] == 2:
grid[i][j] = 1 # 复原这块砖
# 对于复原的这个砖块做四个方向union，主要是为了得到有多少砖必须通过这块砖才能连接到顶部。
self.dfs(i, j, grid, uf)
# new_cnt 就是复原这块砖之后，有多少与顶部相连的砖块
new_cnt = uf.size[uf.find(0)]
# 打掉当前砖块会掉的数量就是 复原后的数量- 开始时的数量 - 1 （本身）
# 但是要注意复原这块砖之后，与顶部相连的砖块可能不会变，比如复原的这块砖是一块孤立的砖
# 因此要测试一下 new_cnt - cnt 是否大于 0
res.append(new_cnt - cnt - 1 if new_cnt - cnt > 0 else 0)
# 由于是从后向前，所以下次循环时，这个砖还没掉，更新cnt。
cnt = new_cnt
return res[::-1] # 因为是从后往前，所以要反转结果
def dfs(self, i, j, grid, uf):
row = len(grid)
col = len(grid[0]) if row else 0
for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
if x < 0 or x >= row or y < 0 or y >= col:
continue
if grid[x][y] == 1:
uf.union(i * col + j + 1, x * col + y + 1)
if i == 0:
uf.union(i * col + j + 1, 0)