郑州的电子商城网站建设,电商网站可以用dw做,wordpress 破解后台,湛江小程序设计公司题目描述
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说#xff0c;如果你在 nums[i] 处#xff0c;你可以跳转到任意 nums[i j] 处:
0 j nums[i]i j n
返回到达 nums[n …题目描述
给定一个长度为 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]。
题目分析
在分析此题之前可以先回顾下LeetCode 刷题 [C] 第55题.跳跃游戏 再结合本体题意本题依然是使用贪心算法的思想来分析
依然是先构造一个表示能跳跃到的最大位置max_jump_pos初始值为0遍历数组若当前值的下标小于等于max_jump_pos表示能够从前面的某个元素跳跃到当前位置接下来比较当前元素值当前元素位置是否大于max_jump_pos若大于则更新max_jump_pos否则不更新max_jump_pos另外我们再维护一个当前能够到达的最大下标位置记为边界。更新该值时机从左至右遍历数组过程中访问到边界元素时更新边界并将跳跃次数增加1。即在边界区间内包括边界自身一定发生了一次跳跃且只有一次。不要访问最后一个元素因为在这之前我们的边界一定大于等于最后一个位置否则就无法跳跃到最后一个位置。如果访问最后一个元素可能会多增加一次不必要的跳跃次数。
Code
class Solution {
public:int jump(vectorint nums) {int max_jump_pos 0, size nums.size(), win_end 0, step 0;for (int i 0; i size - 1; i) {if (max_jump_pos i) {max_jump_pos max(max_jump_pos, i nums[i]);if (win_end i) {win_end max_jump_pos;step;}}}return step;}
};
