沿着一維數組移動

最近我在網上編碼挑戰中遇到了這個問題，但我似乎無法做出任何頭腦的方式。沿着一維數組移動

有一維數組由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

沿着一維數組移動

回答

相關問題