如何网站建设网页,北京招聘网站开发,seo综合查询是啥意思,北京网站搭建服务商题目
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说#xff0c;如果你在 nums[i] 处#xff0c;你可以跳转到任意 nums[i j] 处: 0 j nums[i] i j n 返回到达 nums[n - 1]…题目
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处: 0 j nums[i] i j n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例
输入: nums [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。
解析
这道题和『跳跃游戏I』不同的就是上道题求能不能跳到终点这道题求最小几步能跳到终点。 在遍历数组的时候不必要访问数组的最后一个元素因为题目保证了一定能跳到最后一个位置那我们在访问最后一个元素的时候我们的边界一定是大于等于最后一个元素。如果访问最后一个元素在边界恰好为最后一个位置的情况下会增加一次次数解释的是下面代码中i n-1的逻辑。 举个例子23114 这个数组开始的时候2可以跳到3或1的位置假如跳到3则又可以直接跳到终点只需要两步即可如果是i n-1的话在n-1的位置又要算一下然后命中step结果就不对了
func jump(nums []int) int {n : len(nums)maxPosition : 0 // 最大可跳步数end : 0 // 边界step : 0for i : 0; i n-1; i { // 这里要小于n-1maxPosition max(maxPosition, inums[i])if i end { // 每次到边界就将边界更新成最大可跳步数并将步数1end maxPositionstep}}return step
}
