打印達到數組末尾所需的最小跳轉次數序列

Question

我給出了一個整數值大於或等於0的數組，例如： [5,6,0,4,2， 4，1，0，0，4]

我要求實現一種算法來遍歷在「跳」開始的最短編號的數組在索引0處，在那裏遍歷定義如下：

- >從數組的第一個（第0）索引處開始，查看那裏的數組值，並且可以向前跳到任何數組索引，該索引不超過該值。因此，在本例中，您從包含值5的索引0開始，現在可以考慮跳轉到索引1到5中的任何一個。

如果我選擇跳到索引3，它包含值4，我可以從我當前的索引（3）中再跳到4個點 - 現在我考慮索引4到7作爲序列中的下一步。

我的算法必須確定最小跳數解決方案，但可以在具有相同跳數的解決方案中任意選擇。

在這個例子中，以下將是有效的輸出：

0，5，9，出

這是我的執行情況：

public class ArrayJumper { 

    /** 
    * @param args the command line arguments 
    */ 
    int[] minJumps(int arr[], int n) { 
     int jumps[] = new int[n]; 
     int tab[] = new int[n];// jumps[n-1] will hold the result 
     int i, j; 
     jumps[0] = 0; 
     tab[0] = 0; 

     if (n == 0 || arr[0] == 0) { 
      return jumps; 
     } 

     // Find the minimum number of jumps to reach arr[i] 
     // from arr[0], and assign this value to jumps[i] 

     for (i = 1; i < n; i++) { 
      jumps[i] = Integer.MAX_VALUE; 
      for (j = 0; j < i; j++) { 
       if (i <= j + arr[j] && jumps[j] != Integer.MAX_VALUE) { 
        if (jumps[i] >= jumps[j] + 1) { 
         jumps[i] = jumps[j] + 1; 
         tab[i] = j; 
         //break; 
        } 
       } 
      } 
     } 
     System.out.println(Arrays.toString(jumps)); 

     return tab; 
    } 

    public static void main(String[] args) { 
     // TODO code application logic here 
     int arr[] = {5, 6, 0, 4, 2, 4, 1, 0, 0, 4}; 
     //int arr[] = {2,3,1,1,2,4,2,0,1,1}; 
     int n = arr.length; 
     int res[] = new int[n]; 
     int inn[] = new int[n]; 
     ArrayJumper a = new ArrayJumper(); 
     inn = a.minJumps(arr, n); 
     System.out.println(Arrays.toString(inn)); 

     inn[0] = 0; 
     String ans = " 0 ,"; 

     for (int i = 0; i < n - 1; i++) { 
      if (inn[i] != inn[i + 1]) { 
       ans = ans.concat(inn[i + 1] + ","); 
      } 
     } 
     if (arr[inn[n - 1]] + inn[n - 1] == n - 1) { 
      ans = ans.concat(n - 1 + ","); 
     } 

     ans = ans.concat("out"); 
     System.out.println(ans); 
    } 
} 

但是該解決方案適用於給定的輸入，它在以下輸出中失敗： {2,3,1,1,2,4,2,0,1,1}; 我不知道我錯過了哪裏。註釋輸入都正常工作如果我分別更改break語句。 那麼如何修改這個progroam得到

0,1,4,5,9，out爲輸入{2,3,1,1,2,4,2,0,1,1}。

和 0，5，9，以便根據輸入信號{5,6，0，4，2，4，1，0，0，4}

Answer 1

相信你minJumps()是否正常工作。你的問題是建立答案，ans字符串。

我不明白你想要做到這一點的邏輯。我相信你需要從「out」向後建立字符串。當inn[3]等於2，這意味着如果您解決方案經過輸入指數3，它應該通過指數2 3之前但是，你還不知道該解決方案是否會通過指數跳3

所以爲了把它建立起來，你從「out」開始，在「out」之前出現什麼？爲了說明，你需要讓結果數組有一個元素更長，以便新的最後一個元素告訴你在「out」之前訪問的最後一個索引。然後，你可以這樣做：

String ans = "out"; 
    int index = n; 
    while (index > 0) { 
     index = inn[index]; 
     ans = "" + index + ", " + ans; 
    } 
    System.out.println(ans); 

要構建數組中的一個元素，不再需要只是你的方法了一些簡單的修改：

int jumps[] = new int[n + 1]; 
    int tab[] = new int[n + 1];// jumps[n-1] will hold the result 

和

for (i = 1; i <= n; i++) { 

有了這些變化，輸入{​​5 ，6,0,4,2,4,1,0,0,4}產量

0, 5, 9, out 

輸入{2,3,1,1,2,4,2,0,1,1}給出

0, 1, 4, 5, 9, out