Java拼圖在整數陣列中左右移動

Question

我有一個整數數組。從第一個位置開始，我然後在給定索引處添加或減去值以在數組中移動。這個謎題的目的是到達數組的最後一個元素0。我知道這個問題已經在遞歸中解決了，但我應該給出一個非遞歸解決方案。 爲了避免無限循環，我提出一個條件

if (a[index] == a[index+temp]) 

和代碼工作正常，當我傳遞一個數組是這樣的：

int a [] = { 3, 1, 2, 3, 0 }; 

但後來我通過int a [] = {3, 6, 4, 3, 3, 4, 3, 5, 3, 0 }，它告訴我的拼圖沒有解決方案，這是不正確的。 這裏是我的代碼部分：

 int temp; 
     int index = 0; 

     while (index < (a.length-1) && index >= 0) 
      { 
       temp = a[index]; 

       if ((index+temp) <= a.length-1) 
       { 
        if (a[index] == a[index+temp]){ 
         solution = false; 
         break; 
        } 
        index = index + temp; 
       } 
       else if ((index-temp) >=0) 
       { 

        index = index - temp; 
       } 

     } 

我附上照片從我的任務這也解釋了算法的行爲。

Answer 1

你在這裏有什麼基本上是一個有向無權圖。每個索引都與1或2個其他索引連接。

現在，考慮到這一點，您可以使用「breadth first search」算法很容易地解決此問題，該算法工作得很好，無需遞歸。

這裏是相當冗長的實施例：https://ideone.com/yzeBzz

List<Integer> solve(int... a) { 
    //Value in each element is the index, from where we can come here 
    int[] path = new int[a.length]; 
    Arrays.fill(path, -1); //No index is accessible yet 

    //Queue of positions that were visited from somewhere, but nothing was tried to be 
    //visited from them. At the beginning, 0 is in the list, because it's starting point. 
    //Then, if we visit index 3, it is added to this list for later processing. 
    Queue<Integer> posQueue = new LinkedList<>(); 
    posQueue.add(0); 
    path[0] = 0; //0 index is accessible from itself, this is starting position 

    while (!posQueue.isEmpty()) { 
     int pos = posQueue.remove(); 
     int prPos = pos - a[pos]; 
     int nxPos = pos + a[pos]; 
     if (prPos >= 0 && path[prPos] == -1) { 
      path[prPos] = pos; 
      posQueue.add(prPos); 
     } 
     if (nxPos < a.length && path[nxPos] == -1) { 
      path[nxPos] = pos; 
      posQueue.add(nxPos); 
     } 

     if (path[a.length-1] != -1) { 
      break; 
     } 
    } 

    if (path[a.length-1] == -1) { 
     return null; 
    } 

    //Collect the path 
    List<Integer> result = new ArrayList<>(); 
    int idx = a.length-1; 
    while (idx != 0) { 
     result.add(0, idx); 
     idx = path[idx]; 
    } 
    result.add(0, 0); 
    return result; 
} 

正如任何廣度搜索算法中，複雜度爲O（N）。

Answer 2

這可能會實現：

boolean solve(int... a) { 
    for (int i = 0; i < 1 << a.length; i++) { 
     int pos = 0; 
     for (int j = 0; j < 32; j++) { 
      if ((i & (1 << j)) == 0) { 
       if ((pos -= a[pos]) < 0) { 
        break; 
       } 
      } else { 
       if ((pos += a[pos]) >= a.length) { 
        break; 
       } 
      } 
      if (a[pos] == 0) { 
       return true; 
      } 
     } 
    } 
    return false; 
}