UnionFind 库的惯用/正确 Go 代码重构

Question

我正在练习“岛屿数量”中的经典算法问题。我想使用 unionfind 解决它。虽然我可以调整并使其工作，但我想知道构建我的代码的最佳方式。

这是主程序。

package main

import (

  "fmt"

  u "practice/leetcode/library/unionfind"

)

type point u.Point

func numIslands(grid [][]byte) int {

  res := 0

  if grid == nil || grid[0] == nil {

    return res

  }

  m := len(grid)

  n := len(grid[0])

  num := 0

  uf := u.NewUnionFind()

  directions := []point{

    point{1, 0}, 

    point{-1, 0},

    point{0, 1},

    point{0, -1},

  }

  emptyPoint := point{}

  for i := 0; i < m; i++ {

    for j := 0; j < n; j++ {

      if grid[i][j] == 1 {

        p := point{i, j}

        uf.Add(p)

        num++

        for _, v := range directions {

          newx := i + v.X 

          newy := j + v.Y

          if 0 <= newx && newx < m && 0 <= newy && newy < n && grid[newx][newy] == 1 {

            newp := point{newx, newy}

            if uf.Find(newp) == emptyPoint {

              continue

            }

            uf.Union(p, newp)

            num--

          }

        }

      }

    }

  }

  return num

}

func main() {

  // expect 1

  grid := [][]byte {

    {1,1,1,1,0},

    {1,1,0,1,0},

    {1,1,0,0,0},

    {0,0,0,0,0},

  }

  fmt.Println(numIslands(grid))

  

  // expect 2

  grid = [][]byte {

    {1,0},

    {0,1},

  }

  fmt.Println(numIslands(grid))

}

这是我写的 unionfind 库

package unionfind

type Point struct {

  X int

  Y int

}

type UnionFind struct {

  parent map[Point]Point

}

func NewUnionFind() *UnionFind {

  parent := make(map[Point]Point)

  return &UnionFind{parent}

}

func (uf *UnionFind) Add(c Point) {

  if _, ok := uf.parent[c]; ok {

    return

  }

  uf.parent[c] = c

}

func (uf *UnionFind) Find(c Point) Point {

  if p, ok := uf.parent[c]; ok {

    if p != c {

      uf.parent[c] = uf.Find(p)

    }

    return uf.parent[c]

  }

  return Point{}

}

func (uf *UnionFind) Union(c1 Point, c2 Point) {

  p1 := uf.Find(c1)

  p2 := uf.Find(c2)

  if p1 != p2 {

    uf.parent[p1] = p2

  }

}

我试图遵循的设计要求是：我试图避免使用 UnionFind 父映射的接口，因为我可以预见只有 Point 结构会传入库。

我的要求可能是错误的。我愿意接受重构代码并使其看起来更优雅的建议。

Answer 1

当你这样做时：type point u.Pointthenpoint不仅仅是一个u.Point可以互换使用的别名——它是一种全新的类型，你的uniontype包对它一无所知，因此不会接受。所以不要那样做，而是直接使用uniontype包为你提供的类型。例如，更改：directions := []point{&nbsp; &nbsp; point{1, 0},&nbsp;&nbsp; &nbsp; point{-1, 0},&nbsp; &nbsp; point{0, 1},&nbsp; &nbsp; point{0, -1},}emptyPoint := point{}至：directions := []u.Point{&nbsp; &nbsp; u.Point{1, 0},&nbsp;&nbsp; &nbsp; u.Point{-1, 0},&nbsp; &nbsp; u.Point{0, 1},&nbsp; &nbsp; u.Point{0, -1},}emptyPoint := u.Point{}等等。