поиск минимального количества прыжков

Question

Работа над алгоритмом под алгоритмом поиска минимального количества прыжков. Чтобы решить эту проблему, добавьте подробное описание проблемы и две версии кода. Я тестировал, и, похоже, обе версии работают, а моя вторая версия - это оптимизированная версия кода версии 1, которая заставляет меня начинаться с i=maxIndex, кроме непрерывного увеличения, что может сэкономить время, не итерации всех слотов массива.

Вопрос в том, интересует ли мой код второй версии на 100% правильно? Если кто-нибудь найдет какие-либо логические проблемы, оцените, указав.

Постановка задачи

Учитывая массив неотрицательных целых чисел, вы изначально позиционировался на первый индекс массива.

Каждый элемент массива представляет вашу максимальную длину прыжка в этом положении.

Ваша цель - достичь последнего индекса в минимальном количестве прыжков.

Например: Учитывая массив А = [2,3,1,1,4]

Минимальное количество переходов, чтобы достигнуть последнего индекса равно 2. (Перейти 1 шаг от индекса 0 до 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

Лучший способ всегда, чтобы проверить это. Человек не всегда может думать о специальных случаях, но автоматизированный тест может охватывать большинство особых случаев. Если вы считаете, что ваша первая версия работает хорошо, вы можете сравнить результат первого со вторым. Здесь Exemple:

/* 
* 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 
    //... 
}