Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
AC代码
class Solution {
public:
bool canJump(vector<int>& nums) {
if (nums.size() == 1 && nums[0] == 0) return true;
bool flag = true;
for (int i = 0; i < nums.size() - 1; ++i) {
if (nums[i] != 0) continue;
flag = false;
for (int j = 0; j < i; ++j) {
if (nums[j] > i - j) {
flag = true;
break;
}
}
if (!flag) return false;
}
return flag;
}
};
AC代码（动态规划）
class Solution {
public:
bool canJump(vector<int>& nums) {
if(nums[0]==0 && nums.size()!=1) return false;
vector<int> dp(nums.size());
dp[0]=nums[0];
for (int i = 1; i < nums.size()-1; ++i) {
dp[i] = max(dp[i - 1]-1, nums[i]);
if (dp[i] == 0) return false;
}
return true;
}
};
AC代码（贪心）
class Solution {
public:
bool canJump(vector<int>& nums) {
int reach = 0;
for (int i = 0; i < nums.size(); ++i) {
if (i > reach || reach >= nums.size() - 1) break;
reach = max(reach, nums[i] + i);
}
return reach >= nums.size() - 1;
}
};
总结
1、自己的思路：先找0，找到0再从头遍历，如果当前位置能"越过"0，则该0不成为障碍，break后寻找下一个0，如果这个0之前的元素都无法越过这个0，那么返回false，如此往复直到遍历完毕倒数第二个元素。
2、动态规划与贪心解法学习自：https://www.cnblogs.com/grandyang/p/4371526.html
3、动态规划数组dp考虑并存放每个元素最远能跳几个位置，如果最远只能跳0个位置，那么返回false，对每个元素来说，它能跳的最远位置是它前一个元素所能跳的最远位置减一 与 当前数值大小两者之间的最大值。
4、贪心定义一个初始为0的reach，代表已知能到达的最大位置，若当前位置大于可到达的最大位置或者可到达最大位置大于等于实际最大位置，退出遍历，判断Ture/False，否则，取已知可达最大位置与当前位置与当前可跳跃最大距离之和的最大值，作为新的reach。
