200. 岛屿数量 - 力扣（LeetCode）
dfs找到所有的岛屿，遍历所有的点，如果当前节点是岛屿并且未被访问的话，说明这个点是新的岛屿，答案加一
func numIslands(grid [][]byte) int {
var ans int
n,m := len(grid),len(grid[0])
vis := make([][]bool,n+1)
for i := 0; i < n + 1; i ++ {
vis[i] = make([]bool,m+1)
}
var dfs func(int,int)
nx := []int{1,-1,0,0}
ny := []int{0,0,1,-1}
dfs = func(x,y int) {
vis[x][y] = true
for i := 0; i < 4; i ++ {
xx,yy := x + nx[i], y + ny[i]
if xx >= 0 && xx < n && yy >= 0 && yy < m &&
grid[xx][yy] == '1' && vis[xx][yy] == false {
dfs(xx,yy)
}
}
}
for i := 0; i < n; i ++ {
for j := 0; j < m; j ++ {
if !vis[i][j] && grid[i][j] == '1' {
ans ++
dfs(i,j)
}
}
}
return ans
}130. 被围绕的区域 - 力扣（LeetCode）
反向思考，找到所有与边缘o相连的区域，将该区域标记为*
再遍历一次区域，将*改为O，将O改为X
func solve(board [][]byte) {
//
n,m := len(board),len(board[0])
var dfs func(int,int)
nx := []int{0,0,1,-1}
ny := []int{1,-1,0,0}
dfs = func(x,y int) {
board[x][y] = '*'
for i := 0; i < 4; i ++ {
xx,yy := x + nx[i], y + ny[i]
if xx >= 0 && xx < n && yy >= 0 && yy < m {
if board[xx][yy] == 'O' {
dfs(xx,yy)
}
}
}
}
for i := 0; i < n; i ++ {
if board[i][0] == 'O' {
dfs(i,0)
}
if board[i][m-1] == 'O' {
dfs(i,m-1)
}
}
for i := 0; i < m; i ++ {
if board[0][i] == 'O' {
dfs(0,i)
}
if board[n-1][i] == 'O' {
dfs(n-1,i)
}
}
for i := 0 ; i < n ; i ++ {
for j := 0; j < m; j ++ {
if board[i][j] == '*' {
board[i][j] = 'O'
}else if board[i][j] =='O'{
board[i][j] = 'X'
}
}
}
}133. 克隆图 - 力扣（LeetCode）
本质上就是图的遍历，可以用dfs，也可以用bfs
不管用哪种，都需要用哈希表来记录某个节点是否被遍历过
/**
* Definition for a Node.
* type Node struct {
* Val int
* Neighbors []*Node
* }
*/
func cloneGraph(node *Node) *Node {
vis := make(map[*Node]*Node)
var dfs func(*Node) *Node
dfs = func(node *Node) *Node {
if node == nil {
return nil
}
if val,ok := vis[node]; ok {
return val
}
nowNode := &Node{node.Val,[]*Node{}}
vis[node] = nowNode
for _,ne := range node.Neighbors {
nowNode.Neighbors = append(nowNode.Neighbors,dfs(ne))
}
return nowNode
}
return dfs(node)
}207. 课程表 - 力扣（LeetCode）
要学课程a必须要先学课程b，那么就建立一条b到a的有向边
拓扑排序判断是否有环
func canFinish(numCourses int, prerequisites [][]int) bool {
//b->a建边
graph := make([][]int,numCourses+1)
for i := 0; i < numCourses + 1; i ++ {
graph[i] = []int{}
}
in := make([]int,numCourses+1) //入度
for _,pre := range prerequisites {
graph[pre[1]] = append(graph[pre[1]],pre[0])
in[pre[0]]++
}
var queue []int
for i := 0; i < numCourses; i ++ {
if in[i] == 0 {
queue = append(queue,i)
}
}
ans := 0
for len(queue) > 0 {
ans ++
now := queue[0]
queue = queue[1:]
for _,ne := range graph[now] {
in[ne] --
if in[ne] == 0 {
queue = append(queue,ne)
}
}
}
return ans == numCourses
}210. 课程表 II - 力扣（LeetCode）
额外用数组维护入队顺序
func findOrder(numCourses int, prerequisites [][]int) []int {
//b->a建边
graph := make([][]int,numCourses+1)
for i := 0; i < numCourses + 1; i ++ {
graph[i] = []int{}
}
in := make([]int,numCourses+1) //入度
for _,pre := range prerequisites {
graph[pre[1]] = append(graph[pre[1]],pre[0])
in[pre[0]]++
}
var queue []int
for i := 0; i < numCourses; i ++ {
if in[i] == 0 {
queue = append(queue,i)
}
}
cnt := 0
ans := []int{}
for len(queue) > 0 {
cnt ++
now := queue[0]
queue = queue[1:]
ans = append(ans,now)
for _,ne := range graph[now] {
in[ne] --
if in[ne] == 0 {
queue = append(queue,ne)
}
}
}
if cnt != numCourses {
return []int{}
}
return ans
}994. 腐烂的橘子 - 力扣（LeetCode）
每次从腐烂的橘子出发进行bfs
注意一开始要记录下新鲜橘子的数量，当新鲜橘子数量大于0时才进行循环
func orangesRotting(grid [][]int) int {
ans := 0
queue := [][]int{}
n,m := len(grid),len(grid[0])
cnt := 0
for i := 0; i < n; i ++ {
for j := 0; j < m; j ++ {
if grid[i][j] == 2 {
queue = append(queue,[]int{i,j})
}else if grid[i][j] == 1 {
cnt ++
}
}
}
nx := []int{0,0,1,-1}
ny := []int{1,-1,0,0}
for len(queue) > 0 && cnt > 0 {
ans ++
now := len(queue)
for i := 0; i < now; i ++ {
nowx,nowy := queue[0][0],queue[0][1]
queue = queue[1:]
for j := 0; j < 4; j ++ {
xx,yy := nowx + nx[j], nowy + ny[j]
if xx >= 0 && xx < n && yy >= 0 && yy < m && grid[xx][yy] == 1 {
grid[xx][yy] = 2
queue = append(queue,[]int{xx,yy})
cnt --
}
}
}
}
if cnt > 0 {
return -1
}
return ans
}评论 (0)
