描述
给定一个非负整数数组nums,假定最开始处于下标为0的位置,数组里面的每个元素代表下一跳能够跳跃的最大长度。如果能够跳到数组最后一个位置,则返回true,否则返回false。
输入:
[2,1,3,3,0,0,100]
返回值:
true
说明:
首先位于nums[0]=2,然后可以跳2步,到nums[2]=3的位置,再跳到nums[3]=3的位置,再直接跳到nums[6]=100,可以跳到最后,返回true
题目链接
package main
// import "fmt"
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return bool布尔型
*/
func canJump1( nums []int ) bool {
// write code here
var dp = make([]bool, len(nums))
dp[0] = true
for i:=1;i<len(nums);i++ {
for j:=0;j<i;j++ {
if dp[j] && j+ nums[j] >= i {
dp[i] = true
break
}
}
}
return dp[len(nums)-1]
}
func max(a ...int) int {
var u = a[0]
for _,v := range a {
if u<v {
u = v
}
}
return u
}
func canJump2(nums []int) bool {
if len(nums) <=1 { return true }
var sum int
for i:=0;i<len(nums);i++{
if i>sum { return false }
if i+nums[i] > sum {
sum = i+nums[i]
}
}
return true
}
func canJump( nums []int ) bool {
return canJump2(nums)
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)