博文中会简要介绍Leetcode P0055题目分析及解题思路。
“Jump Game”是一道比较典型的贪心问题，它的变形题是p0045，这道题可以正向贪心，也可以反向遍历。
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.
正向贪心遍历不再赘述，思路和p0045一致。反向贪心遍历则是首先将起点start设置为数组的最后一位下标，然后向前遍历，若发现i为下标的位置为起点可以跳过start则更新start，直到遍历所有位置，若最后start为0说明最终的位置可达。
以下是Java的题解代码实现。
class Solution {
public boolean canJump(int[] nums) {
if (nums == null || nums.length <= 1)
return true;
int left = 0, right = nums[0];
while (left <= right && right < nums.length-1) {
int maxRight = right;
while (left <= right) {
maxRight = Math.max(maxRight, left+nums[left]);
++left;
}
right = maxRight;
}
return (right >= nums.length-1);
}
}
以下是C++的题解代码实现。
class Solution {
public:
bool canJump(vector<int>& nums) {
if (nums.size() <= 1)
return true;
int start = nums.size()-1;
for (int idx=nums.size()-2; idx>=0; --idx) {
if (idx+nums[idx] >= start)
start = idx;
}
return (start == 0);
}
};