我正在練習(xí)一個經(jīng)典的算法問題去“島數(shù)”。我想使用unionfind解決它。雖然我可以調(diào)整并使其工作,但我想知道構(gòu)建代碼的最佳方法。這是主程序。package mainimport ( "fmt" u "practice/leetcode/library/unionfind")type point u.Pointfunc 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 unionfindtype 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結(jié)構(gòu)我試圖遵循的設(shè)計要求是:我試圖避免使用UnionFind父映射的接口,因為我只能預(yù)見Point結(jié)構(gòu)被傳遞到庫中。我的要求可能是錯誤的。我對重構(gòu)代碼并使其看起來更優(yōu)雅的建議持開放態(tài)度。
1 回答

米脂
TA貢獻1836條經(jīng)驗 獲得超3個贊
執(zhí)行此操作時:
type point u.Point
那么不僅僅是一個可以互換使用的別名名稱 - 它是一種全新的類型,并且您的軟件包對此一無所知,因此不會接受。pointu.Pointuniontype
因此,請不要這樣做,而是直接使用包為您提供的類型。例如,更改: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{}
等等。
- 1 回答
- 0 關(guān)注
- 123 瀏覽
添加回答
舉報
0/150
提交
取消