沿着一维数组移动

最近我在网上编码挑战中遇到了这个问题，但我似乎无法做出任何头脑的方式。沿着一维数组移动

有一维数组由0和1

的玩家开始在索引0，需要超越数组的长度。

一旦阵列的长度超过了玩家的胜利。

玩家仅可以进入具有一个0

指数玩家可以移动1个退一步，1个步骤向前或向前米步骤。

问题是如何找出游戏是否可以赢。

这一切都归结为以下函数签名：

boolean winnable(int[] arr, int m){ 
}

有人可以帮我上手的算法。

以后添加

我所能了这个算法，这当然没有通过大部分测试案例。

public static boolean winnable(int[] arr, int m){ 
     int currPos = 0; 
     for(int i=1; i< arr.length; i++){ 
      if(currPos == arr.length -1 - m) return true; 
      else if(arr[i] == 0)currPos++; 
      else if(arr[i] == 1){ 
       if(arr[currPos + m] == 0) currPos = currPos + m; 
      } 
     } 
     return false; 
    }

来源

2016-03-14 Zeus

你会碰巧有机会访问一些测试用例吗？对'm'有任何约束？ –

我想我找到了[link]（https://www.hackerrank.com/challenges/java-1d-array）。 –

遍历整个数组。对于每个单元格 - > 如果它是1，则将其标记为不可访问。否则，检查它是否可达。一个小区是可达的，如果其中一个是小区之前可达的小区 B）小区m细胞之前它是可及的。

一旦一个单元格被标记为可达，您还必须标记它后面的所有连续单元格，它们都是'0'可达。一旦你标记了一个小于m个小区的小区从可达到的地方，这意味着结束是可达的。如果您将最后的m个单元标记为不可访问，则末端无法访问。

来源

2016-03-15 00:00:09 matanso

您将需要一个队列或其他方式来记住需要检查哪些索引。每次你达到一个以前从未见过的零点时，你需要检查3个索引：前一个，后一个，距离为m。

队列的大小限制为输入数组中零的个数。例如，如果输入数组有10个零，那么队列中可能不会有超过10个项目。因此，您可以将队列实现为与输入数组大小相同的简单数组。

下面是一些伪代码，演示了如何来解决这个问题：

writeToQueue(0) 
while (queue is not empty) 
{ 
    index = readFromQueue 
    if (index >= length-m) 
     the game is winnable 

    array[index] = 1 // mark this index as visited 

    if (index > 0 && array[index-1] == 0) // 1 step back 
     writeToQueue(index-1) 
    if (array[index+1] == 0) // 1 step forward 
     writeToQueue(index+1) 
    if (array[index+m] == 0) // m steps forward 
     writeToQueue(index+m) 
} 
if the queue empties without reaching the end, the game is not winnable

注意，输入数组用于跟踪哪些指标已被访问，即找到的每个0改为一个1，直到比赛获胜，或者没有更多的0可到达。

来源

2016-03-15 05:27:51 user3386109

我刚刚在HackerRank上添加了一个accepted解决方案。

这是一个递归方法。我创建了一个帮助函数，将currentIndx,array,jumpValue和Set of visited indices作为参数。

由于currentIndx不能是< 0，我返回false; 如果currentIndx> arr.length - 1，我们就完成了。如果currentIndx的值不是0，我们必须再次返回false，因为它不在路径中。

现在，在这些检查之后，我们将访问索引添加到集合中。如果add操作返回false，那么该索引必须先前被访问;所以我们返回false。

然后，我们递归。我们使用currentIndx - 1，currentIndx + 1和currentIndx + jumpValue来调用相同的函数来查看返回结果。如果其中任何一个都是真的，我们找到了一条路径。

[Java source code]

来源

2016-03-15 19:14:25

它可以干净地使用BFS来解决。这里是我的解决方案：

private static boolean isReachable(int[] array, int m) { 
    boolean[] visited = new boolean[array.length]; 
    Queue<Integer> queue = new LinkedList<>(); 

    queue.add(0); 
    visited[0] = true; 
    while (!queue.isEmpty()) { 
     Integer current = queue.poll(); 
     if (current+m >= array.length) { 
      return true; 
     } else if (current+m < array.length && array[current+m] == 0 && !visited[current+m]) { 
      queue.add(current+m); 
      visited[current+m] = true; 
     } 

     if (current+1 >= array.length) { 
      return true; 
     } else if (current+1 < array.length && array[current+1] == 0 && !visited[current+1]) { 
      queue.add(current+1); 
      visited[current+1] = true; 
     } 

     if (current-1 >= 0 && array[current-1] == 0 && !visited[current-1]) { 
      queue.add(current-1); 
      visited[current-1] = true; 
     } 
    } 
    return false; 
}

来源

2016-04-30 09:30:09

沿着一维数组移动

回答

相关问题