我偷看你板今天一直讲union find
才想到可以用
我有罪== 好难欸
def removeStones(self, stones: List[List[int]]) -> int:
n = len(stones)
root = [i for i in range(n)]
ans = 0
def find_root(a):
while root[a] != a:
a = root[a]
return a
def union(a,b):
nonlocal ans
root_a, root_b = find_root(a), find_root(b)
if root_a != root_b:
root[root_a] = root_b
ans += 1
row_idx_map = defaultdict(list)
col_idx_map = defaultdict(list)
for i,pt in enumerate(stones):
row_idx_map[pt[0]].append(i)
col_idx_map[pt[1]].append(i)
for _, row_idx_list in row_idx_map.items():
a = row_idx_list[0]
for b in row_idx_list[1:]:
union(a,b)
for _, col_idx_list in col_idx_map.items():
a = col_idx_list[0]
for b in col_idx_list[1:]:
union(a,b)
return ans
补个昨天的
一开始没把图二走完就直接退DFS
结果出事
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) ->
int:
m, n = len(grid1), len(grid1[0])
traveled = [[0 for _ in range(n)] for _ in range(m)]
def dfs(i,j):
diff = [1, 0, -1, 0, 1]
traveled[i][j] = 1
flag = grid1[i][j] is not 0
for diff_i in range(4):
next_i, next_j = i+diff[diff_i], j+diff[diff_i+1]
if 0<=next_i<m and 0<=next_j<n and grid2[next_i][next_j]==1 and
traveled[next_i][next_j]==0:
flag_temp = dfs(next_i,next_j)
flag = flag and flag_temp
return flag
ans = 0
for i in range(m):
for j in range(n):
if traveled[i][j] == 0 and grid2[i][j] == 1:
if dfs(i,j):
ans += 1
return ans