重构 Go 代码以符合 UnionFind 库的最佳实践

在重构 Go 代码以符合 UnionFind 库的最佳实践时，遇到了类型不匹配的错误。UnionFind 库中的 point 类型与主程序中的 point 类型不兼容，导致了 Add、Find 和 Union 函数的参数类型错误。为了解决这个问题，需要使用 UnionFind 库提供的 point 类型，而不是使用自定义的 point 类型。这将确保代码兼容性并消除错误。

我正在练习go“岛屿数量”中的一个经典算法问题。我想用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
  }
}

问题是当我运行主程序时，出现以下错误：

# command-line-arguments
./200_number_of_islands_uf.go:31:15: cannot use p (type point) as type unionfind.Point in argument to uf.Add
./200_number_of_islands_uf.go:38:23: cannot use newp (type point) as type unionfind.Point in argument to uf.Find
./200_number_of_islands_uf.go:38:30: invalid operation: uf.Find(newp) == emptyPoint (mismatched types unionfind.Point and point)
./200_number_of_islands_uf.go:41:21: cannot use p (type point) as type unionfind.Point in argument to uf.Union
./200_number_of_islands_uf.go:41:21: cannot use newp (type point) as type unionfind.Point in argument to uf.Union

我想要的硬性要求是： 1.我想将unionfind保留为图书馆 2.我需要在主程序中访问point结构

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

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

解决方案

当你这样做时：

type point u.point

那么 point 不仅仅是 u.point 的别名，可以互换使用 - 它是一种全新的类型，并且您的 uniontype 包对此一无所知，因此不会接受。

所以不要这样做，而是直接使用 uniontype 包为您提供的类型。例如，更改：

directions := []point{
    point{1, 0}, 
    point{-1, 0},
    point{0, 1},
    point{0, -1},
}
emptypoint := point{}

至：

directions := []u.Point{
    u.Point{1, 0}, 
    u.Point{-1, 0},
    u.Point{0, 1},
    u.Point{0, -1},
}
emptyPoint := u.Point{}

等等。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《重构 Go 代码以符合 UnionFind 库的最佳实践》文章吧，也可关注golang学习网公众号了解相关技术文章。