1345.跳跃游戏IV
1345.跳跃游戏IV
题解
i + 1 满足：i + 1 < arr.length
i - 1 满足：i - 1 >= 0
j 满足：arr[i] == arr[j] 且 i != j
问从第一个出发到达最后一个需要几步，其实就是一个无向图，那么对于需要最短路径的问题，直接BFS就能做出来，每个元素连着 <i -1> <i+1><value相同>的这些边，那么对于这个图来说，可能出现无限循环的情况，用一个visited的map来处理
代码
package main type P struct { idx, step int } func minJumps(arr []int) int { queue := make([]P, 0) visited := make(map[int]bool) repeat := make(map[int][]int) for k, v := range arr { repeat[v] = append(repeat[v], k) //把值相同的下标存起来 } queue = append(queue, P{0, 0}) visited[0] = true for { top := queue[0] queue = queue[1:] idx, step := top.idx, top.step if idx == len(arr)-1 { return step } //值相同 for _, v := range repeat[arr[idx]] { if !visited[v] { queue = append(queue, P{ idx: v, step: step + 1, }) } visited[v] = true } //i-1 if idx-1 >= 0 { if !visited[idx-1] { queue = append(queue, P{ idx: idx - 1, step: step + 1, }) } visited[idx-1] = true } //i+1 if idx+1 <= len(arr)-1 { if !visited[idx+1] { queue = append(queue, P{ idx: idx + 1, step: step + 1, }) } visited[idx+1] = true } //BFS三种情况遍历完了，把当前这个值删除 delete(repeat, arr[idx]) } }
