线性时间算法达到最终所需的最小跳跃次数

Question

问题:达到结束的最小跳跃次数

给定一个整数数组,其中每个元素表示可以从该元素向前进行的最大步数.编写一个函数来返回到达数组末尾的最小跳转次数(从第一个元素开始).如果元素为0,那么我们就无法遍历该元素.

例:

输入:arr [] = {1,3,5,8,9,2,6,7,6,8,9}输出:3(1-> 3 - > 8 - > 9)第一个元素是1,所以只能转到3.第二个元素是3,所以最多可以制作3个步骤,即5个或8个或9个.

资料来源:http://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/

我已经制作了一个线性时间算法来查找到达数组末尾所需的最小跳跃次数.

源代码如下:

int minJumpsUpdated(int arr[], int n)
{
  int *jumps = malloc(n * sizeof(int));  // jumps[n-1] will hold the result
  int i =1, j = 0;

  jumps[0] = 0;
  for (i = 1; i < n; ) { 

    // if i is out of range of arr[j], then increment j
    if (arr[j] + j < i && j < i) {

      j++;

    // else if i is within range of arr[j], 
    //   jumps for ith element would be jumps[j]+1
    } else if (arr[j] + j >= i && j < i) {

      jumps[i] = jumps[j] + 1;
      i++;

    } else {
      printf("solution does not exist");
      return -1;
    }
  }

  printf("jumps: ");
  for (i = 0; i < n; i++) {
    printf("%d, ", jumps[i]);
  }
  return jumps[n - 1];
}

例:

1.)最初i=1, j=0和arr[] = {1, 3, 6, 1, 0, 9};

jumps[] = 0,0,0,0,0,0

2.)i在arr[j]ie 范围内.i<= j+arr[j],到第i个位置所需的跳跃次数将是最小跳跃次数,直到第j个位置+ 1.

i=2, j=0, jumps[] = 0,1,0,0,0,0

3.)i>j+arr[j]即j++;

i=2, j=1, jumps[] = 0,1,0,0,0,0

4.)i<=j+arr[j]即jumps[i] = jumps[j]+1;

i=3, j=1, jumps[] = 0,1,2,0,0,0

5.)i<=j+arr[j]即jumps[i] = jumps[j]+1;

i=4, j=1, jumps[] = 0,1,2,2,0,0

6.)i<=j+arr[j]即jumps[i] = jumps[j]+1;

i=5, j=1, jumps[] = 0,1,2,2,2,0

7.)i>j+arr[j]即j++;

i=5, j=2, jumps[] = 0,1,2,2,2,0

8.)i<=j+arr[j]即jumps[i] = jumps[j]+1;

i=6, j=2, jumps[] = 0,1,2,2,2,3

- - - 结束 - - -

我无法弄清楚这个程序在哪个测试用例下不起作用.我问这个是因为在互联网上优化的解决方案是使用DP,即O(n ^ 2).我的解决方案是线性时间.即O(n).所以我假设有一些这种算法无法处理的情况.所以我很好奇它没有处理的情况.

我们将不胜感激.

谢谢.

Answer 1

算法摘要:

1. 拿第一个项目,然后看看你可以得到多远
   (增加i直到arr[j]+j < i)
2. 转到第一个可以从第一个到达的项目,它至少会带您到i项目.
3. 重复此操作,直到到达最后一个条目.

第一:
是的,它运行在O(n)自算法推动双方i的j距离只有一次1到n最坏的情况.

其次,
我没有看到O(n²)最佳时间复杂度的证据.

THRID
您可以观察arr这样 所以这正是你的算法所做的.您可以使用它来通过归纳证明您的算法是正确的.但正如@Leo所提到的,必须有一个解决方案.

修复无解决案例
确保j < i保留.

Answer 2

我认为你的代码只有在有解决方案的情况下才是正确的，如果没有解决方案怎么办，例如如果输入是 [0, 2 , 3 , 4] 该怎么办？

除此之外，我认为你的算法是正确的，这是我解决这个问题时的解决方案，它只需要恒定的空间，并且仍然是线性时间。基本上对于每个步骤，您只跳转到可以跳过下一步中大多数步骤的位置。

int jump(int A[], int n) {
    int jumps = 0;
    if(n < 2){
        return jumps;
    }
    int cur = 0; // current index,
    int cur_step;// number of step you can jump in current index 
    int last;    // last index
    int temp_max = cur; // temporary max jump distance 
    int temp_index = cur;// temporary index.

    while(cur < n){
        last = cur;
        cur_step = A[cur];
        if((cur + cur_step) >= n-1){ // if reached end of the array, return.
            jumps++;
            return jumps;
        }
        for(int ii = cur + 1; ii <= cur + cur_step; ii++){//go thru all the possible next position, and find the one that could jump most steps.
            if(A[ii] == 0){
                continue;
            }
            if(A[ii] + ii > temp_max){ // find the one that could jump most steps.
                temp_index = ii;
                temp_max = A[ii] + ii;
            }
        }
        cur = temp_index; // jump to this position, temp index holds index that jump most steps in next jump.
        if(cur != last){
            jumps++;
        }else{
            break;
        }
    }
    return -1;


}
};