免备案网站建设,整网站代码 带数据 免费 下载,公众号开发的可行性,Wordpress和drupal开发【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主#xff0c;题解使用C语言。#xff08;若有使用其他语言的同学也可了解题解思路#xff0c;本质上语法内容一致题解使用C语言。若有使用其他语言的同学也可了解题解思路本质上语法内容一致 【题目描述】
给定一个长度为 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步到达数组的最后一个位置。
【示例二】
输入: nums [2,3,0,1,4]
输出: 2
【提示及数据范围】
1 nums.length 10的4次方0 nums[i] 1000题目保证可以到达 nums[n-1]
【代码】
// 贪心// 维护当前能够到达的最大下标位置记为边界。
// 我们从左到右遍历数组到达边界时更新边界并将跳跃次数增加 1。
// 由于题目中一定可以到达最后一个元素所以不用再枚举最后一个元素int jump(vectorint nums) {int maxpos 0,n nums.size(),end 0,step 0;for(int i 0;in-1;i){maxpos max(maxpos,i nums[i]);if(i end){end maxpos;step;}}return step;
}
