for循环条件未按预期工作——LeetCode跳跃游戏II问题排查

我正在编写LeetCode第45题「跳跃游戏II」的代码，目标是找出从索引0到索引n-1的最少跳跃步数，nums[i]表示在第i个位置能跳跃的最大步数。当前代码运行时，遇到nums[i]==0的情况，for循环会直接终止，但我预期是跳过该迭代。改用if语句单独判断nums[i]==0的情况时，代码就能正常运行。

以下是我的Java代码：

import java.util.*;
class HelloWorld {
    public static void main(String[] args) {
        int[] nums = {2,3,0,1,0};
        int val = jump(nums);
        System.out.println(val);
    }
    public static int jump(int[] nums) {
        int[] paths = new int[nums.length];
        int curr = nums.length-1;
        int dest = nums.length-1;
        for(int i=curr;i>=0 && nums[i]!=0;i--){
            int diff = dest-i;
            System.out.println("i=>"+i+" diff=>"+diff+" nums[i]=>"+nums[i]);

            // if(nums[i]==0){
            //     paths[i]=0;
            // }

            if(diff==0){
                paths[i]=0;
            }
            else if(diff<=nums[i]){
                paths[i]=1;
            }else{
                int min = diff;
                for(int j=1;j<=nums[i] && paths[i+j]!=0;j++){
                    // if(paths[i+j]!=0){
                        min=Math.min(1+paths[i+j],min);
                    // }
                    
                }
                paths[i]=min;
            }
            System.out.println(Arrays.toString(paths));
        }
        return paths[0];
    }
}

问题原因 #

问题出在for循环的终止条件上：for(int i=curr;i>=0 && nums[i]!=0;i--)。这里的&& nums[i]!=0是循环继续执行的必要条件，一旦遍历到某个i对应的nums[i]==0，整个循环就会直接停止，而不是跳过当前i的处理。

修复方案 #

把nums[i]==0的判断从循环条件中移除，放到循环内部处理：

1. 修改for循环为for(int i=curr;i>=0;i--)，确保能遍历所有索引
2. 在循环开头添加判断，遇到nums[i]==0时，设置paths[i]=0后直接跳过当前迭代

修改后的代码示例：

import java.util.*;
class HelloWorld {
    public static void main(String[] args) {
        int[] nums = {2,3,0,1,0};
        int val = jump(nums);
        System.out.println(val);
    }
    public static int jump(int[] nums) {
        int[] paths = new int[nums.length];
        int curr = nums.length-1;
        int dest = nums.length-1;
        // 移除循环条件中的nums[i]!=0判断
        for(int i=curr;i>=0;i--){
            // 单独处理nums[i]==0的情况
            if(nums[i]==0){
                paths[i]=0;
                continue; // 跳过当前迭代
            }
            int diff = dest-i;
            System.out.println("i=>"+i+" diff=>"+diff+" nums[i]=>"+nums[i]);

            if(diff==0){
                paths[i]=0;
            }
            else if(diff<=nums[i]){
                paths[i]=1;
            }else{
                int min = diff;
                for(int j=1;j<=nums[i] && paths[i+j]!=0;j++){
                    min=Math.min(1+paths[i+j],min);
                }
                paths[i]=min;
            }
            System.out.println(Arrays.toString(paths));
        }
        return paths[0];
    }
}

内容的提问来源于stack exchange，提问作者jainyashit