LeetCode 55. Jump Game
一个数组存储了非负整型数据，数组中的第i个元素nums[i]，代表了可以从数组第i 个位置最多向前跳跃nums[i]步;已知数组各元素的情况下，求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置?
例如:
nums = [2, 3, 1, 1, 4] ，可以从nums[0] = 2 跳跃至 nums[4] = 4; nums = [3, 2, 1, 0, 4] ，不可以从nums[0] = 3 跳跃至 nums[4] = 4。
贪心规律
若此时处在第i位置，该位置最远可以跳至第j位置(index[i])，故第i位置还可跳至: 第i+1、i+2、...、j-1、j位置;
从第i位应跳至第i+1、i+2、...、j-1、j位中可以跳的更远位置的位置，即 index[i+1]、index[i+2]、...、index[j-1]、index[j]最大的那个!
原因:
假设该位置为x，index[x]最大，故从位置x出发，可以跳至i+1、i+2、...、j-1、j所有 位置可以达到的位置;所以跳至位置x最理想。
算法思路
1.求从第i位置最远可跳至第index[i]位置: 根据从第i位置最远可跳nums[i]步: index[i] = nums[i] + i;
2.初始化:
1)设置变量jump代表当前所处的位置，初始化为0; 2)设置变量max_index代表从第0位置至第jump位置这个过程中，最远可到达的位置，初始化为index[0]。
3.利用jump扫描index数组，直到jump达到index数组尾部或jump超过max_index，扫描过程中， 更新max_index。
4.若最终jump 为数组长度，则返回true，否则返回false。
#include<vector>
class Solution{
public:
bool canJump(std::vector<int> & nums){
std::vector<int> index; //最远可以跳至的位置
for(int i = 0;i<nums.size();i++){
index.push_back(i+ nums[i]);
}
int jump = 0;
int max_index =index[0];
while(jump < index.size && jump <= max_index){
if(max_index < index[jump]){
max_index = index[jump];
}
jump ++;
}
if(max_index == index.size()){
return true;
}
return false;
}
};
跳跃游戏2
LeetCode 45. Jump Game II
一个数组存储了非负整型数据，数组中的第i个元素nums[i]，代表了可以从数组第i 个位置最多向前跳跃nums[i]步;已知数组各元素的情况下，确认可以从第0位置跳跃到数组最后一个位置，求最少需要跳跃几次?
例如:
nums = [2, 3, 1, 1, 4] ，从第0位置跳到第1位置，从第1位置跳至最后一个位置。
贪心规律
在到达某点前若一直不跳跃，发现从该点不能跳到更远的地方了，在这之前肯定 有次必要的跳跃!
结论:只有在无法到达更远的位置时，我们才应该选择跳跃，而选择从这之间的哪个位置跳跃?应选择一个可以到达更远位置的位置，跳到这个位置后，再往前跳。
算法思路
1.设置current_max_index为当前可达到的最远位置;
2.设置pre_max_max_index为在遍历各个位置的过程中，各个位置可达到的最远位置;
3.设置jump_min为最少跳跃的次数。
4.利用i遍历nums数组，若i超过current_max_index，jump_min加1，current_max_index = pre_max_max_index
5.遍历过程中，若nums[i]+i (index[i])更大，则更新pre_max_max_index = nums[i] + i。
#include<vetor>
class Solution{
public:
int jump(std::vector<int> &nums){
if(nums.size() < 2){
return 0;
}
int current_max_index = nums[0];// 当前可达到的最远位置
int pre_max_max_index = nums[0];//遍历各个位置过程中，可达到的最远位置
int jump_min =1 ;
for(int i = 1; i< nums.size();i++){
if(i > current_max_index){ // 若无法再向前移动，才进行跳跃
jump_min++;
curren_max_max_index = pre_max_max_index;
}
if(pre_max_max_index < num[i] + 1){
pre_max_max_index = nums[i]+i;
}
return jump_min;
}
}
};
