给定一个数组，我们可以在其中跳跃任意距离 y，使得 y ≤ x。找到到达数组末尾的最小跳跃次数

Question

public class HelloWorld{

     public static void main(String []args){
       int[] arr = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        int result = minJumps(arr);
        System.out.println("Minimum jumps: " + result);
       
    }
    
    
    static int minJumps(int[] arr){
       int N=arr.length;
       int i=N-1;
       int count=0;
       int res=N;
       
      while(i>=0)
       {
         for( int j=res-2;j>=0;j--)
         {
           if((i-j)<=arr[j])
           {
              res=j;
             
             
            }
            count++;
            i=res;
            j=res-1;
           
         }
       }
       return count;
       
       
    }
}

整个问题都在gfg上。 给定一个由 N 个整数组成的数组 arr[]，其中每个元素代表可以从该元素向前跳转的最大长度。这意味着如果 arr[i] = x，那么我们可以跳跃任意距离 y，使得 y ≤ x。 找到到达数组末尾的最小跳转次数（从第一个元素开始）。如果某个元素为 0，则您无法移动该元素。

我尝试了 o(N2) 逻辑，任何人都可以指出这种方法的错误。 代码没有运行，但我已经尝试过代码的试运行。

Answer 1

1. 您的循环条件不正确。外部 while 循环应该运行到 i 大于或等于 0，而不仅仅是直到 i 大于或等于 0。

2. 内循环的条件j >= 0 是不必要的。当您找到有效的跳转或当 j 低于 0 时，您应该跳出内部循环。

3. 您应该在内循环中更新 i 的值，而不是在循环后更新一次。

这是代码的更正版本：

public class HelloWorld {

    public static void main(String []args) {
        int[] arr = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        int result = minJumps(arr);
        System.out.println("Minimum jumps: " + result);
    }

    static int minJumps(int[] arr) {
        int N = arr.length;
        int i = 0; // Start from the first element
        int count = 0;

        while (i < N - 1) {
            int maxReach = i + arr[i];
            int nextJump = i;

            for (int j = i + 1; j <= maxReach && j < N; j++) {
                if (j + arr[j] > maxReach) {
                    maxReach = j + arr[j];
                    nextJump = j;
                }
            }

            i = nextJump;
            count++;
        }
        return count;
    }
}

Answer 2

o(N)

逻辑解决你的问题：

static int minJumps(int[] arr) {
    int jumps = 0; // Jump countt
    int currentMax = 0; // The maximum index 
    int farthest = 0; // The farthest index

    for (int i = 0; i < arr.length - 1; i++) {
        farthest = Math.max(farthest, i + arr[i]);

        if (i == currentMax) {
            jumps++;
            currentMax = farthest;

            // Reached the end of the array
            if (currentMax >= arr.length - 1) {
                break;
            }
        }
    }
    
    return jumps;
}