達到陣列末端所需的最小跳躍數 - 獲取索引位置

Question

問題是得到minimum jumps和數組中相應的索引，導致跳轉較少的array結束。例如： {3,2,3,1,5,4}需要2 jump s。

Jump 1 from index 0 to index 2 
jump 2 from index 2 to index 5 

By跳，我的意思是跳;即需要多少次啤酒花。如果你是一個特定的索引，你可以跳過該索引中的值。

這是我在Java實施，這給正確的跳躍的最小數目，但我有困難更新list我與對應跳位置indices。我怎樣才能使它工作？

public static int minJumps2(int[] arr, List<Integer> jumps){ 
     int minsteps=0; 
     boolean reachedEnd=false; 
     if (arr.length<2) 
      return 0; 
     int farthest=0; 
     for (int i=0;i<=farthest;i++){ 
      farthest=Math.max(farthest, arr[i]+i); 
      if (farthest>=arr.length-1){ 
       jumps.add(i); 
       reachedEnd=true; 
       break; 
      } 
      //jumps.add(farthest); 
      minsteps++; 

     } 
     if (!reachedEnd){ 
      System.out.println("unreachable"); 
      return -1; 
     } 
     System.out.println(minsteps); 
     System.out.println(jumps); 
     return minsteps; 
    } 

public static void main(String[] args){ 

     int[] arr= {3,2,3,1,5}; 
     List<Integer> jumps=new ArrayList<Integer>(); 
     minJumps2(arr,jumps); 

    } 

我現在用的是跳轉博弈算法如下所述：Interview puzzle: Jump Game

Answer 1

雖然我不明白你的問題清楚，但似乎你需要的時候你遞增minsteps++到索引添加到jumps。

您需要註銷jumps.add(farthest);並通過i而不是farthest。此外，您可能需要刪除帶有in if條件的jumps.add(i)。希望這可以幫助。

編輯： 看來你的邏輯是，除了第一跳是在指數0總是很好。因此，在循環之前將0添加到您的jumps。

UPDATE 好的，我沒有測試，也沒有通過你提供的算法鏈接。算法解釋說，我們需要考慮一個元素e和索引i並從當前位置獲取元素的max到arr[e]並且這不會發生。我試圖複製提到的解決方案的確切步驟。希望這可以幫助你。

public static int minJumps2(int[] arr, List<Integer> jumps) { 
     boolean reachedEnd = false; 
     if (arr.length < 2) 
      return 0; 

     //calculate (index + value) 
     int[] sums = new int[arr.length]; 
     for (int i = 0; i < arr.length; i++) { 
      sums[i] = i + arr[i]; 
     } 
     // start with first index 
     jumps.add(0); 

     while (true) { 
      int currentPosition = jumps.get(jumps.size() - 1); 
      int jumpValue = arr[currentPosition]; 

      // See if we can jump to the goal 
      if (arr.length - 1 - currentPosition <= jumpValue) { 
       jumps.add(arr.length - 1); 
       reachedEnd = true; 
       break; 
      } else { 
       int maxIndex = currentPosition; 
       int currentMax = sums[maxIndex]; 
       // max of the reachable elements 
       for (int i = currentPosition; i <= currentPosition + jumpValue; i++) { 
        if (sums[i] > currentMax) { 
         maxIndex = i; 
         currentMax = sums[i]; 
        } 
       } 
       if (maxIndex == currentPosition) { 
        break; 
       } 

       jumps.add(maxIndex); 
      } 
     } 
     System.out.println(jumps.size()); 
     System.out.println(jumps); 
     return jumps.size(); 
    } 

Answer 2

我看你已經接受了答案，但我有一些代碼，做你所需要的：

- 它打印出來分的路徑跳（不只是一個，但所有）。

- 它也會告訴你，如果數組的末尾無法訪問。

它使用DP，複雜性= O（NK），其中Ñ是陣列的長度，並ķ是在陣列最大元素的數值。

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 

public class MinHops { 

    private static class Node { 
     int minHops; 
     int value; 
     List<Node> predecessors = new ArrayList<>(); 

     Node(int distanceFromStart, int value) { 
      this.minHops = distanceFromStart; 
      this.value = value; 
     } 
    } 

    public static void allMinHopsToEnd(int[] arr) { 
     Node[] store = new Node[arr.length]; 
     store[0] = new Node(0, arr[0]); 
     for (int i = 1; i < arr.length; i++) { 
      store[i] = new Node(Integer.MAX_VALUE, arr[i]); 
     } 

     for (int index = 0; index < arr.length; index++) { 
      try { 
       updateHopsInRange(arr, store, index); 
      } catch (RuntimeException r) { 
       System.out.println("End of array is unreachable"); 
       return; 
      } 
     } 

     Node end = store[store.length-1]; 
     List<ArrayList<Integer>> paths = pathsTo(end); 
     System.out.println("min jumps for: " + Arrays.toString(arr)); 
     for (ArrayList<Integer> path : paths) { 
      System.out.println(path.toString()); 
     } 

     System.out.println(); 
    } 

    private static void updateHopsInRange(int[] arr, Node[] store, int currentIndex) { 
     if (store[currentIndex].minHops == Integer.MAX_VALUE) { 
      throw new RuntimeException("unreachable node"); 
     } 

     int range = arr[currentIndex]; 
     for (int i = currentIndex + 1; i <= (currentIndex + range); i++) { 
      if (i == arr.length) return; 
      int currentHops = store[i].minHops; 
      int hopsViaNewNode = store[currentIndex].minHops + 1; 

      if (hopsViaNewNode < currentHops) { //strictly better path 
       store[i].minHops = hopsViaNewNode; 
       store[i].predecessors.clear(); 
       store[i].predecessors.add(store[currentIndex]); 
      } else if (hopsViaNewNode == currentHops) { //equivalently good path 
       store[i].predecessors.add(store[currentIndex]); 
      } 
     } 
    } 

    private static List<ArrayList<Integer>> pathsTo(Node node) { 
     List<ArrayList<Integer>> paths = new ArrayList<>(); 
     if (node.predecessors.size() == 0) { 
      paths.add(new ArrayList<>(Arrays.asList(node.value))); 
     } 

     for (Node pred : node.predecessors) { 
      List<ArrayList<Integer>> pathsToPred = pathsTo(pred); 
      for (ArrayList<Integer> path : pathsToPred) { 
       path.add(node.value); 
      } 

      paths.addAll(pathsToPred); 
     } 

     return paths; 
    } 

    public static void main(String[] args) { 
     int[] arr = {4, 0, 0, 3, 6, 5, 4, 7, 1, 0, 1, 2}; 
     int[] arr1 = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}; 
     int[] arr2 = {2, 3, 1, 1, 4}; 
     int[] arr3 = {1, 0, 0, 4, 0}; 
     allMinHopsToEnd(arr); 
     allMinHopsToEnd(arr1); 
     allMinHopsToEnd(arr2); 
     allMinHopsToEnd(arr3); 
    } 

}