一：Jump Game
题目：
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.
For example:A =[2,3,1,1,4], returntrue.
A =[3,2,1,0,4], returnfalse.
链接：https://leetcode.com/problems/jump-game/
代码：
class Solution {public:bool canJump(int A[], int n) {if(n == 0 || n == 1) return true;int maxStep = A[0]; // 当前位置所能跳出的最远距离for(int i = 1; i < n; i++){if(maxStep == 0) return false;// 上次最大跳跃数等于0 表示已经不能到这一步了maxStep = max(–maxStep, A[i]); //i位置所能跳出的最远距离等于i-1位置处跳出的最远距离-1 与他自己值的最大值if(i+maxStep >= n-1)return true; // 局部最优达到全局最优}return false;}};二：Jump Game II
题目：
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.
Your goal is to reach the last index in the minimum number of jumps.
For example:Given array A =[2,3,1,1,4]
The minimum number of jumps to reach the last index is2. (Jump1step from index 0 to 1, then3steps to the last index.)
链接：https://leetcode.com/problems/jump-game-ii/
分析：变形II不仅要求能否到达终点，还要求解最少跳跃次数，这里仍然是贪心算法，但每步需要记录三个变量，上次跳跃的最远位置last，当前跳跃的圆位置curr以及跳跃次数ret。初始化都为0，当i++后到当前位置，，如果i>curr表明目前所能跳跃的最远距离已经无法到达该位置了，故不能达到终点，return -1；如果i>last,表示上次跳跃的最远位置已经不能到达了，故需要ret++且将当前curr赋值给last；并且更新当前所能跳跃的最远距离curr = max(curr, i+A[i])
class Solution {public:int jump(int A[], int n) {int ret = 0;int last = 0; // 上一跳所能到达的最远距离int curr = 0; // 当前跳所能到达的最远距离for(int i = 0; i < n; i++){if(i > curr) return -1; // i++后已经超过了当前所能到达的最远位置故无法到达if(i > last){ // i++后当前位置大于上一次能跳跃的最远距离 则更新并跳跃次数++last=curr;ret++;}curr = max(curr, i+A[i]); // 更新当前所能到达的最远位置}return ret;}};
谁也不跟谁一辈子，有些事情没必要记在心上。
