68 lines
1.0 KiB
Go
68 lines
1.0 KiB
Go
package main
|
|
|
|
import "fmt"
|
|
|
|
func main() {
|
|
fmt.Println(jump([]int{2, 3, 1, 1, 4}))
|
|
}
|
|
|
|
func jump(nums []int) int {
|
|
res := 0
|
|
right := 2
|
|
maxstep := 0
|
|
|
|
for i := 0; i < len(nums); i++ {
|
|
if (i+1)+nums[i] > right {
|
|
maxstep = (i + 1) + nums[i]
|
|
}
|
|
if (i + 1) == right {
|
|
res++
|
|
right = maxstep
|
|
}
|
|
if maxstep >= len(nums) {
|
|
break
|
|
}
|
|
|
|
}
|
|
return res
|
|
}
|
|
|
|
//func jump(nums []int) int {
|
|
// step := make([]int, len(nums))
|
|
// res := 0
|
|
// for i := 0; i < len(nums); i++ {
|
|
// maxstep := 0
|
|
// maxi := 0
|
|
// for j := i + 1; j < i+nums[i]; j++ {
|
|
// if j >= len(nums) {
|
|
// break
|
|
// }
|
|
// if j == i+1 {
|
|
// maxstep = nums[j]
|
|
// maxi = j
|
|
// continue
|
|
// }
|
|
// if nums[j] >= maxstep {
|
|
// maxstep = nums[j]
|
|
// maxi = j
|
|
// }
|
|
// }
|
|
// step[i] = maxi
|
|
// }
|
|
// tmp := make([]int, len(nums))
|
|
// copy(tmp, step)
|
|
// for len(tmp) > 1 {
|
|
// res++
|
|
// num := tmp[0]
|
|
// i := 0
|
|
// for i < num {
|
|
// tmp = tmp[1:]
|
|
// i++
|
|
// }
|
|
// //fmt.Println("---", tmp)
|
|
// }
|
|
// //fmt.Println(step)
|
|
// //fmt.Println(res)
|
|
// return res
|
|
//}
|