贪心算法之跳跃游戏_算法 跳跃障碍物,固定落脚点

【题目】

问题一：能否跳到终点

如何判断能否到终点？
只要某个点x，满足x+nums[x]>=终点的index，那么就可以到达终点，同时需要满足x是可以到达的

如何判断x是否能到达？同理，只要能到达某个点i，满足i+nums[i]>=x，那么x就是能到达的

我们维护一个farthest，就是目前能到达的最远的点，表示从0-farthest的中间所有点都可以通过某种跳跃方式到达；遍历数组的过程中更新farthest
当farthest>=终点index的时候，就说明能到终点
当farthest<下一个要遍历的位置index（用i表示），说明从0开始跳，中间有（0,i-1]这些落脚点，不论在哪里落脚跳跃，最远都到不了i的位置，那么就不可能继续跳了。

eg:
nums=[2,1,0,3]
当从0开始跳，farthest=2
然后遍历i=1,nums[1]=1,farthest=max(farthest,1+nums[1])=2
然后遍历i=2,nums[2]=0,farthest=max(farthest,2+nums[2])=2
然后遍历i=3,此时farthest<i，表示通过前两的位置，不论怎么跳，最远只能到2，那么无法到3，就不能继续跳，所以这个nums最远只能到2

farthest=0;
for(int i=0;i<n;i++)
{
    if(farthest<i) return false;//表示最远也跳不到i的位置，只能到当前的farthest了
    else{
        //之前的farthest>i，说明至少能跳到i点
        //那么i+nums[i]计算从i点起跳最远能跳到哪儿，如果超过了之前的farthest就更新
        farthest=max(farthest,i+nums[i]);
        if(farthest>n-1) return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

问题二：最少跳多少步能到达终点？

题目保证一定能到达终点

假设nums[0]=3，那么从0可以跳到[0,0+nums[0]]中间任意位置，即0,1,2,3，我们选择跳到哪一个呢？
应该跳到j+nums[j]最大的那个对应的j的位置
eg:nums=[3,2,5,3]
1+nums[1]=1+2=3
2+nums[2]=2+5=7
3+nums[3]=3+3=6
我们应该选择跳从0到2

为什么呢？
因为跳到2以后，可以继续选择跳动的范围是最远能到7，能选择跳动的范围最广，能继续跳更远的可能性最大
eg:nums[4,5,6]=1，nums[7]=5
可能再从7跳一下就超过终点了。

所以在可以跳到的范围中，每次选择max(i+nums[i])的位置i去，就可以跳的最少

实现：
假设目前位置在i，那么应该遍历j=i~i+nums[i]，找max(j+nums[j]）,然后跳到j

我们用i维护当前可以跳到的每一个位置（遍历），用end维护当前可以跳到的最远位置，用p记录当前i+nums[i]的最大的时候的i值（即从i起跳应该落到哪个位置），用farthest记录i+nums[i]最大值，如果超过n就是跳到终点了

上一次确认了跳到位置p，那么end=p+nums[p]，然后给i赋值了这个位置p，让for循环从p继续
if(i==end) //说明遍历到了从p起跳能到达的最远距离
//此时已经得到新的p，就是下一个要跳到的位置

count=0;//跳跃次数，从0开始起跳
p_end=0+nums[0];//从0起跳能跳到的位置
p=0;
farthest=0+nums[0];
if(farthest>=n-1) return 1;
for(int i=1;i<n;i++)
{
    if(i+nums[i]>farthest)
    {
        p=i;//维护p是目前能跳到的范围里最有潜力的位置
        farthest=i+nums[i];//维护目前能跳到最远的位置
        if(farthest>=n-1)//从当前位置跳到i后，再跳一次就到终点了
            return count+2;
    }
    if(i==p_end)//说明从当前所在位置能跳到的范围已经遍历结束
    {
        count++;//确定了p的位置，可以从当前跳到p了
        p_end=p+nums[p];//从p可以跳到的最远范围是p_end
        i=p;//让for循环从p往后继续到新的p_end找下一个最有潜力的点
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

注意区分end和far，end是指从上一个p起跳，跳一次能到的最远的点end=p+nums[p]
far指的是最远能跳到哪儿，因为用i遍历[p,p+nums[p]]，而far是max(i+nums[i])相当于是从p起跳，跳到i，再从i起跳，跳两次能到的最远的点