题目链接:https://leetcode-cn.com/problems/jump-game/
这道题有两种解题思路,一种是官方给出的解答方案 通过整个数组能够跳跃的最大距离进行判断,另一种是我个人的解答方案 根据下一步能够跳跃的最大距离。
方案一:
按照官方解题思路,只需要在最后一个数之前找到大于等于整个数组长度的数即可。
代码:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canJump(vector<int>& nums) {
int len = nums.size();
if(len == 1){
return true;
}
if(nums[0] == 0 && len > 1){
return false;
}
//step为可以走的最远距离
int step = nums[0];
for(int i=1; i<len-1; i++){
if(step>=i){
step = max(step, nums[i]+i);
}
}
// cout<<step<<endl;
if(step >= len-1){
return true;
}
return false;
}
};
方案二:只以当前可以走的步数为基准,当最后一步可以走的步数>=1时即为成功。
此方法需要注意:如果在走的过程中某一步可以走的步数为0时,说明无法到达下一步,此时即可判断为false
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canJump(vector<int>& nums) {
int len = nums.size();
if(len == 1){
return true;
}
if(nums[0] == 0 && len > 1){
return false;
}
//step为可以走的最大步数
int step = nums[0];
for(int i=1; i<len-1; i++){
if((step-1)>nums[i]){
step = step-1;
}else{
step = nums[i];
}
if(step == 0){
return false;
}
}
// cout<<step<<endl;
if(step >= 1){
return true;
}
return false;
}
};