到达数组末尾所需的最小跳跃次数-获取索引位置

Question

问题是获取最小跳跃和数组中相应的索引，这些索引导致数组以较小的跳跃结束。例如：{3,2,3,1,5,4}将需要2跳跃s...

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

我说的跳跃是指跳跃；i、 e需要多少啤酒花。如果您是一个特定的索引，则可以通过该索引中的值进行跳跃。

下面是我在Java中的实现，它正确地给出了最小的跳转次数，但是我很难用索引更新我拥有的列表，该索引对应于跳转位置。我怎样才能让它工作呢？

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);

    }

我使用的跳转游戏算法如下所述：面试谜题：跳转游戏




Answer 1

虽然我不清楚您的问题，但当您增加分钟步数时，似乎需要将索引添加到跳跃。

您需要取消注释jumps.add（最远的）；并传递i而不是最远的。此外，您可能需要删除jumps.add（i）与in if条件。希望这能有所帮助。

编辑：看起来你的逻辑很好，除了第一次跳转总是在索引0处。因此，将0添加到循环前的跳转中。

更新好的，我没有经过测试，也没有通过你提供的算法链接。算法解释说，我们需要考虑元素e和indexi，并获得元素从当前位置到arr[e]的max，但这并没有发生。我试图复制解决方案提到的确切步骤。希望这对你有帮助。

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），其中n是数组的长度，k是数组中最大元素的数值。

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);
    }

}