广州网站建设藤虎,合肥市住房和城乡建设局,手机app开发公司排行,惠州网站建设设计【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主#xff0c;题解使用C语言。#xff08;若有使用其他语言的同学也可了解题解思路#xff0c;本质上语法内容一致题解使用C语言。若有使用其他语言的同学也可了解题解思路本质上语法内容一致 【题目描述】
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。
【示例一】
输入nums [2,3,1,1,4]
输出true
解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
【示例二】
输入nums [3,2,1,0,4]
输出false
解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。
【提示及数据范围】
1 nums.length 10的4次方0 nums[i] 10的5次方
【代码】
// 方法一贪心// 我们依次遍历数组中的每一个位置并实时维护最远可以到达的位置。
// 对于当前遍历到的位置 x如果它在 最远可以到达的位置 的范围内
// 那么我们就可以从起点通过若干次跳跃到达该位置
// 因此我们可以用 xnums[x] 更新 最远可以到达的位置。
bool canJump(vectorint nums) {int n nums.size();int rightmost 0;for(int i 0;in;i){if(i rightmost){rightmost max(rightmost,inums[i]);if(rightmost n-1) return true;}else return false;}return false;
}// 方法二倒序// 从题目出发是否能到最后一个位置。用一个变量来表示步数如果能到达下一个位置则为1
// 若不能到达下一个位置则步数加一。当遍历到前面的步数满足条件时再次赋值为1.
// 最后判断该变量是否为一即可。bool canJump(vectorint nums) {int minNums 1,size nums.size();for(int i size - 2;i 0;i--) {if(nums[i] minNums) {minNums 1;} else {minNums;}}return minNums 1;
}
