蛙跳--进军硅谷

给出一维非负元素的数组，每个元素代表从该元素位置能跳的最远距离。假设初始位置在第一个元素，现根据输入数组判断是否能跳到数组的末尾。

书中解法：第一个指针扫描当前值，第二个指针记录能跳的最远距离Curmax=max(A[i]+i,Curmax)。如果Curmax>=A.length-1,return true;如果Curmax等于第一个指针位置并且第一个指针值为0，则不能到末尾。

 1 bool canJump(int A[],int length)
 2 {
 3     if(length<=1)
 4         return true;
 5         int i,curMax=0;
 6         for(i=0;i<length-1;i++)
 7         {
 8                if(A[i]==0&&curMax<i+1)   return false;
 9                if(A[i]+i>curMax&&A[i]>0)
10                 {
11                         curMax=i+A[i];
12                         if(curMax>=length-1) return true;
13                 }
14         }
15         return false;
16 }

View Code

扩张问题：假设输入数组能满足达到数组末尾的条件，求出最少跳数。

第一个指针记录上一次的最远到达距离，第二个指针记录当前能到达的最远距离。当遍历数组的时候，如果当前位置超过了第一个指针位置，则跳数加1并且更新第一个指针的位置为第二个指针的位置。如果当前位置加A[i]超过了第二个指针的位置，则更新第二个指针的值。

 1 int jump(int A[],int length)
 2 {
 3     int result=0;
 4     int last=0,curr=0;
 5     for(int i=0;i<length;++i)
 6     {
 7         if(i>last)
 8         {
 9             last = curr;
10             result++;
11         }
12         curr = max(curr,i+A[i]);
13     }
14     return result;
15 }

View Code