UnionFind 库的惯用/正确 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
}
}
我想要的硬性要求是：1.我想将unionfind保留为库 2.我需要访问主程序中的Point结构
我试图遵循的设计要求是：我试图避免使用UnionFind父映射的接口，因为我只能预见Point结构被传递到库中。
我的要求可能是错误的。我对重构代码并使其看起来更优雅的建议持开放态度。
波斯汪1回答
-
米脂
执行此操作时：type point u.Point那么不仅仅是一个可以互换使用的别名名称 - 它是一种全新的类型，并且您的软件包对此一无所知，因此不会接受。pointu.Pointuniontype因此，请不要这样做，而是直接使用包为您提供的类型。例如，更改：uniontypedirections := []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{}等等。
随时随地看视频慕课网APP
相关分类
Go