java - 到达数组末尾所需的最少跳转 - 获取索引位置

Question

问题是获取 minimum jumps以及数组中导致 array 结束的相应索引跳跃较少。例如: {3,2,3,1,5,4}需要 2 jump秒。

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

Jump，我的意思是跳跃；即需要多少跳。如果你是一个特定的索引，你可以跳到该索引中的值。

这是我在 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

我看到你已经接受了一个答案，但我有满足你需要的代码:

-它打印出最小跳跃的路径(不只是一个，而是所有)。

-它还会告诉您是否无法到达数组末尾。

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

}