LeetCode经典题目

130. 被围绕的区域
200. 岛屿数量
547. 省份数量
684. 冗余连接

模板

class UnionFind {
    func find(_ x:Int,_ parent:[Int]) -> Int {
        var x1 = x
        while parent[x1] != x1 {
            x1 = parent[x1]
        }
        return x1
    }
    
    func union(_ i:Int,_ j:Int,_ parent:inout [Int]) -> Bool{
        let x1 = find(i, parent)
        let y1 = find(j, parent)
        if x1 != y1 {//合并
            parent[x1] = y1
            return true
        }
        return false
    }
    
    //路径优化
    func unionPath(_ x:Int,_ y:Int,_ parent:inout [Int],_ rank:inout [Int]) -> Bool{
        let rootx = find(x,parent)
        let rooty = find(y,parent)
        
        if rootx != rooty {
            if rank[rootx] > rank[rooty] {
                parent[rooty] = rootx
            }else if rank[rootx] < rank[rooty]{
                parent[rootx] = rooty
            }else{
                parent[rooty] = rootx
                rank[rootx] += 1
            }
            return true
        }
        return false
    }
    
    func isConected(_ x:Int,_ y:Int,_ parent:[Int]) -> Bool {
        if find(x,parent) == find(y,parent){
            return true
        }
        return false
    }
}

200. 岛屿数量

这道题有多种解法:深搜、广搜、并查集都可以解。本文主要讲究并查集.
题意是求岛屿的个数。
思路:把1相连的合并成一个块,有多少个块就有多少个岛屿个数。

1. 先统计1的个数，代表总的岛屿数.
2. 遍历二维数组,从当前位置与周围位置是1的岛屿进行合并,合并一个总的岛屿数减1.
3. 最后返回合并后的岛屿数.

func numIslands(_ grid: [[Character]]) -> Int {
        let row = grid.count
        let col = grid[0].count
        
        var count = 0
        var parent:[Int] = Array.init(repeating: 0, count: row*col)

        for i in 0..<row {
            for j in 0..<col {
                if grid[i][j] == "1" {//假设岛屿数量都是独立的,有多少1就有多少陆地
                    count += 1
                }
                parent[i*col+j] = i*col+j
            }
        }
        
        let directions = [[-1,0],[1,0],[0,1],[0,-1]]
        var grid = grid
        
        let unionFind = UnionFind()
        
        for i in 0..<row {
            for j in 0..<col {
                if grid[i][j] == "1" {//如果当前是陆地,则与周围岛屿进行合并
                    grid[i][j] = "0"
                    for dir in directions {
                        let newX = i+dir[0]
                        let newY = j+dir[1]
                        if newX>=0 && newX<row && newY>=0 && newY<col && grid[newX][newY] == "1"{
                            let isUnion = unionFind.union(i*col+j, newX*col+newY, &parent)
                            if isUnion {
                                count -= 1
                            }
                        }
                    }
                }
            }
        }
        return count
    }

130. 被围绕的区域

这道题是上一道题的升华，需要处理边界。需要找到O并用X填充，边界的O不能被填充。如果X是0，O是1，与上一题比较类似。相当于找到陆地1，填充成0.
思路:

1. 边界上的O与maxBorder=row*col进行连通
2. 除边界外，内部连通的O进行连通
3. 遍历数组，找到与maxBorder不连通的O的字符，用X进行填充

func solve(_ board: inout [[Character]]) {
        if board.count == 0 || board[0].count == 0{
            return
        }
        let unionFind = UnionFind()
        
        let row = board.count
        let col = board[0].count
        let maxBorder = row*col
        
        var parent = Array.init(repeating: -1, count: maxBorder+1)
        var rank = Array.init(repeating: -1, count: maxBorder+1)

        for i in 0..<parent.count {
            parent[i] = i
            rank[i] = 0
        }
        
        let dirs = [[-1,0],[1,0],[0,1],[0,-1]]
        
        for i in 0..<board.count {
            for j in 0..<board[0].count {
                if board[i][j] == "X" {
                    continue
                }
                if i == 0 || i == row-1 || j == 0 || j == col-1 {
                    unionFind.unionPath(maxBorder, i*col+j,&parent,&rank)//与maxBorder连接
                }else{
                    for dir in dirs {
                        let newx = i+dir[0]
                        let newy = j+dir[1]
                        
                        if newx>=0 && newx<board.count && newy>=0 && newy<board[0].count && board[newx][newy] == "O" {
                            unionFind.unionPath(i*col+j, newx*col+newy,&parent,&rank)
                        }
                    }
                }
            }
        }
        
        for i in 0..<row {
            for j in 0..<col {
                if board[i][j] == "O"{
                    if !unionFind.isConected(i*col+j, maxBorder,parent) {
                        board[i][j] = "X"
                    }
                }
            }
        }
    }

本题用了unionPath,与union的区别多了rank，记录连通点的高度。

547. 省份数量

与200解法一样,我记得原来是叫朋友圈。

1. i == j代表相同城市
2. i != j且M[i][j] == 1代表i与j的城市相连，则总数-1

func findCircleNum(_ M: [[Int]]) -> Int {
        var parent:[Int] = Array.init(repeating: 0, count: M.count)
        var count = M.count

        for i in 0..<M.count {
            parent[i] = i
        }
        
        let union = UnionFind()
        
        for i in 0..<M.count {
            for j in 0..<M[0].count {
                if M[i][j] == 1 && i != j {
                    let isUnion = union.union(i, j, &parent)
                    if isUnion {
                        count -= 1
                    }
                }
            }
        }

        return count
    }

684. 冗余连接

这是一个典型的无向有环图的。
思路:

1. 把每个顶点看做独立的点，与其他顶点进行合并
2. 遍历每条边，对其顶点进行合并,如果发现合并失败,则证明两个顶点已经连通

func findRedundantConnection(_ edges: [[Int]]) -> [Int] {
        var parent = Array.init(repeating: 0, count: 1001)
        for i in 0..<parent.count {
            parent[i] = i
        }
        let union = UnionFind()
        
        var ans = Array.init(repeating: 0, count: 2)
        for i in 0..<edges.count {
            let from = edges[i][0]
            let to = edges[i][1]
            if !union.union(from,to,&parent) {
                ans[0] = from
                ans[1] = to
            }
        }
        return ans
    }

总结

1. 总的思路就是查找点，然后合并。多练习几遍，孰能生巧。
2. 我理解为每个点都有唯一的标识，然后把相同的合并在一起。无论是二维矩阵，还是图。