-
Notifications
You must be signed in to change notification settings - Fork 1
/
min_jumps.go
49 lines (47 loc) · 1.02 KB
/
min_jumps.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package _345_jump_game_IV
func minJumps(arr []int) int {
ht := make(map[int][]int)
for i := range arr {
if ht[arr[i]] == nil {
ht[arr[i]] = make([]int, 0)
}
ht[arr[i]] = append(ht[arr[i]], i)
}
numVisited := make(map[int]bool)
queue := make([]int, 1)
queue[0] = 0
step := 0
visited := make([]bool, len(arr))
visited[0] = true
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
cur := queue[i]
if cur == len(arr)-1 {
return step
}
/* if the current number has been visited, then all the same number are already in queue */
if !numVisited[arr[cur]] {
numVisited[arr[cur]] = true
for _, j := range ht[arr[cur]] {
if j == cur {
continue
}
queue = append(queue, j)
visited[j] = true
}
}
if cur-1 >= 0 && !visited[cur-1] {
queue = append(queue, cur-1)
visited[cur-1] = true
}
if cur+1 < len(arr) && !visited[cur+1] {
queue = append(queue, cur+1)
visited[cur+1] = true
}
}
queue = queue[size:]
step++
}
return -1
}