HackerRank 上的一维数组游戏

Question

我花了好几个小时在 HackerRank 上尝试解决这个问题。基本问题陈述如下：

您有一个仅包含 0s 和 1s 的一维数组。您从第 0 个索引开始。让我们假设数组的大小为 n。如果你能超出数组的范围（即索引 > n-1），你就赢了。但是你只能通过两种方式移动：

向前或向后走一步。
向前跳 'm' 长度。

此外，您只能踩到值为 0 的元素。第 0 个索引处的值已知为 0。（因此您从有效位置开始）

'm' 作为输入提供，它可以是 0 到 100 之间的任何值（含 0 和 100）。数组大小可以是 2 到 100 之间的任何值（含 2 和 100）。

如果有可能获胜，程序应该打印 "YES"。否则 "NO".

我尝试在 Java 中使用回溯算法解决它。但它被大多数测试用例拒绝了。

请帮助我。提前致谢。

public class Solution {

public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);

         int n=sc.nextInt();
         int m=sc.nextInt();
         int[] array = new int[n];

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

         if(m<2){
             for(int i=0;i<n;i++){
                  if(array[i] == 1){
                        System.out.println("NO");
                        break;
                    } 
                }
                System.out.println("YES");
            }

            else{
        if(isSolvable(array,0,m,n))  
        {System.out.println("YES");}
        else 
        {System.out.println("NO");}

        }

    }

    static boolean isSolvable(int[] array,int x,int m,int n){
        if(x>n-1){ 
            //System.out.print(x + " "); 
            return true;
        }
        if(array[x] == 1) return false;
        if(isSolvable(array,x+m,m,n)){
            //System.out.print(x + " "); 
            return true;
        }
        if(isSolvable(array,x+1,m,n)){
            //System.out.print(x + " "); 
            return true;
        }
        return false;
    }  
 }

Answer 1

编写这个游戏对于业余爱好者来说有点困难，但可以解释我认为可以解决问题的算法。

首先，我认为可以一步到位和"m"进一步的点是这个问题的关键点。我的意思是你可以从他们那里选择另一种方式。如果你到达它们 3 次，那么它们就没用了，等等。我认为将它们放在一个数组中很重要。

定义数组为WellPoints
检查数组的第一个点，您可以在其中进行一步，"m" 进一步进行。保存为 firstWellPoint 或 WellPoints[0].
尝试使用简单的回溯算法通过一个或 "m" 步到达这一点。如果你不能，那只是"NO".
如果你能到达firstWellPoint，定义一个counter来统计你访问了多少次WellPoints。
在检查每个点的后续步骤时，还要检查点是否适合一个步骤和 m 个步骤。如果 one 和 m step further 两者都为“0”，则将其放入 WellPoints 数组。
现在，如果下一次检查不成立，返回到 WellPoints 数组的最后一个元素并将 counter 增加 1。
当您找到新的 WellPoint 时，将您的 counter 重置为 1。
如果counter = 3，则删除此WellPoint并通过其他方式从这之前的一个重新开始检查，这意味着WellPoint数组的新最后一个元素.它可以通过检查 counter 来决定方式，例如 if counter=1 try one steps 当你再次来到这里时，这意味着 if counter=2 try m steps.
如果 WellPoint 数组的第一个元素，或者如我所解释的那样 firstWellPoint 通过在 WellPoint 数组上回溯 3 次再次到达，你将删除这个 WellPoint 也是这样你的阵列将无法走到尽头。
如果你到达数组的末尾，那么你知道...

Answer 2

我没有用回溯来做这件事，只是用递归，我能够解决问题并使所有测试用例都正确。您发布的代码也不进行任何回溯。我还看到，在您的条件下，您缺少向后移动 1 的条件，这会导致您在某些情况下失败。

例如：0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 m=5。

上面的例子，先跳到x+m，然后再试x+m，再试x+1，否则就出局。

分解这个测试用例：

0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1

          ^ x+m True
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1

                    ^ x+m False
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1

            ^ x+1 False
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1

  ^ x+1 False

使用您的代码，您会 return false 而要解决此问题，您需要执行以下操作：

0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1

          ^ x+m

0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1

        ^ x-1
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1

                  ^ x+m

然后再加两个 x+m 来完成 return true。

要使用您的代码完成此操作，您需要添加条件以向后移动一个 space，但是这样做时，您可以合并一个无限递归循环，例如：(-1+1-1+ 1-1+1) 这将导致计算器溢出。我建议包括的其中一件事是 boolean 数组，用于保存您之前看过的景点的记忆。

HackerRank 上的一维数组游戏

1D array game on HackerRank

java

arrays

backtracking