- 1345.跳跃游戏IV
- 题解
- 代码
1345.跳跃游戏IV
题解i + 1 满足：i + 1 < arr.length
i - 1 满足：i - 1 >= 0
j 满足：arr[i] == arr[j] 且 i != j
问从第一个出发到达最后一个需要几步，其实就是一个无向图，那么对于需要最短路径的问题，直接BFS就能做出来，每个元素连着
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])
}
}
