我偷看你板今天一直講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 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724946811.A.E10.html