外贸网站 栏目,中国互联网公司排名,宿迁房价最新价格表,网站开发项目管理文档模板题目描述
给你一个非负整数数组 nums #xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标#xff0c;如果可以#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
示例 1…题目描述
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。
示例 1
输入 nums [2,3,1,1,4] 输出 true 解释 可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2
输入 nums [3,2,1,0,4] 输出 false 解释 无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。
提示
1 nums.length 1040 nums[i] 105
代码及注释
func canJump(nums []int) bool {// 初始化覆盖范围为0cover : 0// 获取数组的长度length : len(nums) - 1// 遍历数组for i : 0; i cover; i {// 更新覆盖范围cover max(i nums[i], cover)// 检查是否可以到达最后一个位置if cover length {return true}}// 如果遍历完整个数组都没有找到一个位置可以达到最后一个位置则返回falsereturn false
}// 辅助函数返回两个数中的最大值
func max(x, y int) int {if x y {return x}return y
}代码解释 初始化覆盖范围为0 cover : 0我们使用cover变量来表示当前位置可以到达的最远距离。初始时从第一个位置出发我们可以覆盖的范围是0。 获取数组的长度 length : len(nums) - 1获取数组的长度这样我们可以检查是否可以覆盖到数组的最后一个位置。 遍历数组 for i : 0; i cover; i {我们从第一个位置开始遍历直到cover位置这是因为在当前位置之前的每个位置都可以从前面的位置跳到。 更新覆盖范围 cover max(i nums[i], cover)对于每一个位置i我们计算从当前位置可以跳跃的最远距离然后与当前的cover比较取其中更大的值。这确保我们选择了最远的距离作为下一步可以达到的最远距离。 检查是否可以到达最后一个位置 if cover length {return true
}在每次更新cover后我们检查是否可以覆盖到数组的最后一个位置如果可以则返回true。 返回结果 return false如果遍历完整个数组都没有找到一个位置可以达到最后一个位置则返回false。
这道题使用了贪心算法的思想。我们从第一个位置开始持续更新能够跳跃到的最远位置并检查这个最远位置是否能达到数组的最后一个位置。如果可以跳跃到最后一个位置那么整个数组就可以被跳跃到。
