我在minJumps问题中的思维过程有什么错误？

Question

问题在于到达数组末尾的最小跳转次数。 我的逻辑是通过元素循环数组，直到 i+arr[i]

public static int minJumps(int[] arr){
            // your code here
            if(arr.length==1){
                return -1;
            }
            int jumps=1;
            int maxIndex=0;

            int i=0;

            while(i+arr[i]<arr.length-1){
                if(arr[i]==0){
                    return -1;
                }
                int max=0;
                for(int j=i+1;j<=arr[i]+i;j++){

                    if(arr[j]>=max){
                        max=arr[j];
                        maxIndex=j;
                    }

                }


                i=maxIndex;





                jumps++;


            }
            return jumps;

        }

Answer 1

• 在 while 循环条件

  while(i+arr[i]<arr.length-1)

  中，似乎您在到达数组的最后一个元素之前停止循环。您应该将其更改为

  while (i < arr.length - 1)

  以也包含最后一个元素

• 在 for 循环

  for(int j=i+1;j<=arr[i]+i;j++)

  中，您需要确保

  j

  不超出数组边界

  (j < arr.length)

  。否则，它可能会抛出

  IndexOutOfBoundsException

• 如果数组包含值为 0 的元素，则代码返回 -1，这意味着不可能到达数组末尾。然而，情况可能并非总是如此。你应该更准确地处理这个问题。例如，如果当前元素为0，则可以跳过它并继续查找下一个最大可达索引

public static int minJumps(int[] arr) {
    if (arr.length == 1) {
        return 0; // if there's only one element, no jump needed
    }
    
    int jumps = 0;
    int maxReach = arr[0];
    int stepsLeft = arr[0];
    
    for (int i = 1; i < arr.length - 1; i++) {
        maxReach = Math.max(maxReach, i + arr[i]);
        stepsLeft--;

        if (stepsLeft == 0) {
            jumps++;
            stepsLeft = maxReach - i;
        }
    }
    
    return jumps + 1; // we need one more jump to reach the end
}