找到跳跃的最小数量

Question

在寻找最小跳跃数量的算法难题上工作。发布详细的问题陈述和两个代码版本来解决这个问题。我做了测试，似乎两个版本的作品，我的第二个版本是第一版代码的优化版本，这使得我从i=maxIndex开始，而不是连续增加，这可以通过不迭代阵列的所有插槽来节省时间。

我的问题是，想知道我的第二版本代码是否100％正确？如果有人发现任何逻辑问题，欣赏指出。

问题陈述

给定的非负整数的数组，你最初定位该阵列的第一索引处。

数组中的每个元素表示您在该位置的最大跳跃长度。

你的目标是达到最小跳跃次数的最后一个索引。

例如： 鉴于阵列A = [2,3,1,1,4]

跳跃的最小数目以达到最后一个索引是2（跳转从索引0 1个步骤1，然后3个步骤的最后一个索引。）

第一版本代码

class Solution { 
public: 
    int jump(vector<int>& nums) { 
     int i = 0, n = nums.size(), step = 0, end = 0, maxend = 0; 
     while (end < n - 1) { 
      step++; 
      for (;i <= end; i++) { 
       maxend = max(maxend, i + nums[i]); 
       if (maxend >= n - 1) return step; 
      } 
      if(end == maxend) break; 
      end = maxend; 
     } 
     return n == 1 ? 0 : -1; 
    } 
}; 

第二版本代码

class Solution { 
public: 
    int jump(vector<int>& nums) { 
     int i = 0, n = nums.size(), step = 0, end = 0, maxend = 0; 
     int maxIndex = 0; 
     while (end < n - 1) { 
      step++; 
      for (i=maxIndex;i <= end; i++) { 
       if ((i + nums[i]) > maxend) 
       { 
        maxend = i + nums[i]; 
        maxIndex = i; 
       } 

       if (maxend >= n - 1) return step; 
      } 
      if(end == maxend) break; 
      end = maxend; 
     } 
     return n == 1 ? 0 : -1; 
    } 
}; 

在此先感谢， 林

Answer 1

最好的办法就是始终对它进行测试。人类不能总是思考特殊情况，但自动化测试可以涵盖大部分特殊情况。如果你认为你的第一个版本运行良好，你可以比较第一个版本和第二个版本的结果。这里的为例：

/* 
* arraySize : array size to use for the test 
* min   : min jump in the array 
* max   : max jump in the array 
*/ 
void testJumps(int arraySize, int min, int max){ 

    static int counter = 0; 
    std::cout << "-----------Test " << counter << "------------" << std::endl; 
    std::cout << "Array size : " << arraySize << " Minimum Jump : " << min << " Max Jump" << max << std::endl; 
    //Create vector with random numbers 
    std::vector<int> vecNumbers(arraySize, 0); 
    for(unsigned int i = 0; i < vecNumbers.size(); i++) 
     vecNumbers[i] = rand() % max + min; 

    //Value of first function 
    int iVersion1 = jump1(vecNumbers); 

    //Second fucntion 
    int iVersion2 = jump2(vecNumbers); 

    assert(iVersion1 == iVersion2); 

    std::cout << "Test " << counter << " succeeded" << std::endl; 
    std::cout << "-----------------------" << std::endl; 

    counter++; 

} 

int main() 
{ 
    //Two test 
    testJumps(10, 1, 100); 
    testJumps(20, 10, 200); 

    //You can even make a loop of test 
    //... 
}