谁能帮我理解这段代码？

Question

谁能帮我理解这段代码？这段代码就是用来解决这个问题的。您正在手机上玩游戏。给定一个长度为 n 的数组，索引从 0 到 n−1。数组的每个元素要么是 0 要么是 1。您只能移动到包含 0 的索引。首先您位于第 0 个位置。在每一步中，您可以执行以下操作之一：

向前或向后走一步。向前跳跃正好长度 m。这意味着您可以一次从位置 x 移动到 x+1、x−1 或 x+m。新位置必须包含0。也可以移动到任何大于n-1的位置。

你不能从位置0向后移动。如果你移动到任何大于n−1的位置，你就赢了。

给定数组和跳跃的长度，你需要判断是否有可能赢得比赛。

        n = sc.nextInt();
        m = sc.nextInt();
        field = new int[n];
        for (int i = 0; i < n; i++) {
            field[i] = sc.nextInt();
        }

        if (makeMove(0, new LinkedList<Integer>()))
            System.out.println("YES");
        else
            System.out.println("NO");

。 . .

private boolean makeMove(int position, List<Integer> prevPositions) 
  {
  if (prevPositions.contains(position)) 
    return false;
    prevPositions.add(position);

    if (position < 0) return false;
    else if (position >= n) return true;
    else if (field[position] == 1) return false;
    else {
        return makeMove(position + m, prevPositions) ||
                makeMove(position + 1, prevPositions) ||
                makeMove(position - 1, prevPositions);
    }
}

输入：6 2

   0 0 0 1 0 0

输出：是

输入：6 2

   0 0 1 1 0 0

输出：否

Answer 1

因此，我假设您了解递归的概念，即在自身内部调用方法，否则您可能需要查找它。

第一段代码很简单。它初始化移动长度 m 和长度数组 n 并用随机二进制数字填充它。

makeMove 方法通过几个基本案例来查看递归分支是失败还是成功。

1.) if (prevPositions.contains(position)) return false; prevPositions.add(position);

移动后，此代码会检查您是否已经到达此位置。如果你有，它 returns false 因为这种情况已经被认为是错误的，否则该方法已经 returned true.

2.) if (position < 0) return false; else if (position >= n) return true; else if (field[position] == 1) return false;

-不能有负仓位，所以returns false。 - 如果你的位置大于 n 那么你赢了，所以 return true - 你不能移动到包含非零数字的位置，所以return false

3.) return makeMove(position + m, prevPositions) || makeMove(position + 1, prevPositions) || makeMove(position - 1, prevPositions);

此代码从可能的位置递归调用其他移动，如果这些调用中的任何一个为真，则 returns true。既然可以跳到 position+m，那么如果 makeMove(position+m, prevPositions) 为真，那么 makeMove(position, prevPositions) 也为真。同样，您可以移动到 position+1 和 position-1，因此对这些位置的 makeMove 的调用应 return 与原始位置的 makeMove 相同的值。希望这是有道理的！

Answer 2

这个解决方案工作正常。请试试这个。您需要传递元素数组长度和跳转值。

public static boolean decideMove(int[] elements, int length, int jump){
    boolean result = false;
    boolean makeMove = true;
    int currentPosition = 0;
        while(makeMove){
            if (currentPosition + jump > length-1){
                return true;
            } 

            if(elements [currentPosition + jump] == 0){
                currentPosition = currentPosition + jump;
                if (currentPosition + jump > length-1){
                    return true;
                } 
            }
            if (elements[currentPosition + 1] == 0){
                currentPosition = currentPosition + 1;
                if (currentPosition + jump > length-1){
                    return true;
                } 
            }

            if(elements[currentPosition +1] ==1 && elements[currentPosition + jump]==1){
                if(elements[currentPosition - 1]==0){
                    currentPosition = currentPosition - 1;
                } else{
                    return false;
                }

            }
        }

    return result;
}

谁能帮我理解这段代码？

Can anyone help me understand this piece of code?

java

arrays

algorithm

linked-list