算法-数据结构-并查集

算法

并查集

  1. 优化一（将高的tree作为root,降低树的高度）
  2. 优化二 (递归路径压缩)
  3. 解题思路
    1
    2
    3
    4
    1. find union 代码不变
    2. self.count 代表需要合并的节点（岛屿，朋友）对角矩阵问题节点只有一般
    3. self.parent 代表初始化节点树，若是二维数组非对角矩阵问题需降纬
    4. 寻找需要合并的条件

岛屿数量

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class UnionSet():
    
    def __init__(self,grid):
        m, n = len(grid), len(grid[0])
        # 代表需要合并的节点（岛屿，朋友）
        self.count=0
        self.parent=[]
        # 将二维数组降纬
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='1':
                    self.count+=1
                self.parent.append(i*n+j)
        # 树的秩，也就是高度。初始化数量与节点树相同
        self.rank=[0 for i in range(m*n)]
    
    def find(self,x):
        if self.parent[x]!=x:
            self.parent[x]=self.find(self.parent[x])
        return self.parent[x]
    
    def union(self,x,y):
        rootx=self.find(x)
        rooty=self.find(y)
        
        if rootx!=rooty:
            if self.rank[rootx]<self.rank[rooty]:
                self.parent[rootx]=rooty
                self.rank[rootx]+=1
            elif self.rank[rootx]>self.rank[rooty]:
                self.parent[rooty]=rootx
                self.rank[rooty]+=1
            else:
                self.parent[rooty]=rootx
                self.rank[rooty]+=1
            self.count-=1

class Solution():
    def numIslands(self,grid):
        if not grid or not grid[0]:
            return 0
        m, n = len(grid), len(grid[0])
        direction=[(1,0),(-1,0),(0,1),(0,-1)]
        us=UnionSet(grid)
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='0':
                    continue
                for d in direction:
                    nc,nr=i+d[0],j+d[1]
                    if nc>=0 and nr>=0 and nc <m and nr <n and grid[nc][nr]=="1":
                        us.union(i*n+j,nc*n+nr)                    
        return us.count

朋友圈个数

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class UnionSet():
    
    def __init__(self,grid):
        m, n = len(grid), len(grid[0])
        self.count=m
        self.parent=[]
        for i in range(m):
            self.parent.append(i)
        self.rank=[0 for i in range(m)]
    
    def find(self,x):
        if self.parent[x]!=x:
            self.parent[x]=self.find(self.parent[x])
        return self.parent[x]
    
    def union(self,x,y):
        rootx=self.find(x)
        rooty=self.find(y)
        
        if rootx!=rooty:
            if self.rank[rootx]<self.rank[rooty]:
                self.parent[rootx]=rooty
                self.rank[rootx]+=1
            elif self.rank[rootx]>self.rank[rooty]:
                self.parent[rooty]=rootx
                self.rank[rooty]+=1
            else:
                self.parent[rooty]=rootx
                self.rank[rooty]+=1
            self.count-=1

class Solution():
    def findCircleNum(self,grid):
        if not grid or not grid[0]:
            return 0
        m, n = len(grid), len(grid[0])
        us=UnionSet(grid)
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1:
                    us.union(i,j)                    
        return us.count