Re: [閒聊] 每日leetcode
今年最後一題leetcode
1970. Last Day Where You Can Still Cross
只要淹水的地方可以從第1行到最後1行連成一條線
直線可以從8個方向
右,右上、右下,左,左上,左下,上,下連起來
就可以保證沒辦法從top到bottom
所以用union find
在左右兩邊設一個牆
如果這兩個牆能連起來那就能保證上下無法通行
c=0就要跟左牆連在一起
c=col-1要跟右牆連在一起
每一天都要去union 8個方向
最後檢查左右牆是否連通
如果連通那就是這一天
golang code :
type unionFind struct{ parent []int }
func (this *unionFind) find(i int) int {
if (*this).parent[i] == i {
return i
}
(*this).parent[i] = this.find((*this).parent[i])
return (*this).parent[i]
}
func (this *unionFind) union(i, j int) {
p1, p2 := this.find(i), this.find(j)
if p1 != p2 {
this.parent[p1] = p2
}
}
func latestDayToCross(row int, col int, cells [][]int) int {
n := row * col
uf := unionFind{make([]int, n+2)}
for i := 0; i < n+2; i++ {
uf.parent[i] = i
}
grid := make([][]bool, row)
for i := 0; i < row; i++ {
grid[i] = make([]bool, col)
}
leftWall, rightWall := n, n+1
for time, cell := range cells {
r, c := cell[0]-1, cell[1]-1
cur := r*col + c
grid[r][c] = true
if c == 0 {
uf.union(cur, leftWall)
}
if c == col-1 {
uf.union(cur, rightWall)
}
for i := -1; i <= 1; i++ {
for j := -1; j <= 1; j++ {
nextR, nextC := r+i, c+j
if nextR < row && nextC < col && nextR > -1 && nextC > -1 && grid[nextR][
nextC] {
uf.union(cur, nextR*col+nextC)
}
}
}
if uf.find(leftWall) == uf.find(rightWall) {
return time
}
}
return 0
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1767180465.A.D2B.html
→
12/31 19:28,
14小時前
, 1F
12/31 19:28, 1F
推
12/31 19:33,
14小時前
, 2F
12/31 19:33, 2F
推
12/31 19:35,
14小時前
, 3F
12/31 19:35, 3F
推
12/31 19:35,
14小時前
, 4F
12/31 19:35, 4F
→
12/31 19:36,
14小時前
, 5F
12/31 19:36, 5F
討論串 (同標題文章)
完整討論串 (本文為第 1557 之 1558 篇)：