以最少的跳数遍历数组，技术公司面试的在线编码挑战

Question

我做了一个面试问题/编码挑战，我需要想出通过一个数组"arr“的最短数量的”跃点“，其中在每个索引处我可以跳跃1->arri。

其中一个问题是，我不能在任何值为0的索引上登陆。

当我开始解决这个问题时，我开始将数组看作一个有向图，其中每个索引是一个节点i，它们的子节点由所有可达节点i+1->i+arri表示。

当您将其想象为一个图时，我认为使用Dijkstra是一个很好的方法，因为这样我就不需要遍历数组一百万次来找到最佳路径。

对于工程师来说，这不是一个足够的答案，我是不是想错了？或者我只是没有在我的实现中执行。

import java.util.LinkedList;
import java.util.Scanner;

public class Solution {
    public static void main(String args[] ) throws Exception {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */

        // get canyon from standard in
        Integer[] canyon = getInput();

        // This problem is a twist on the shortest path algorithm (Dijkstras), the array is like a graph
        // with the values being used to determine the "edges" to different "nodes" aka other indexes with
        // non zero values

        // these are used for tracking the necessary details of our "graph"
        // we could have make an actual graph or made an array of objects with these fields but given
        // the potential size of the input, 3 arrays made most sense

        // the current ammount of jumps to reach this space, set to int max for starters
        int[] cost = getIntArray(canyon.length, true);

        // tracking if the "nodes" are yet "known"/"discovered" by the algorithm
        // dragon nodes are set to known so the algorithm will ignore them
        boolean[] known = getBoolArray(canyon, canyon.length);

        // used to point back ward to the previos step in the shorts path to each node
        // can be traversed backwards from destination to get shortest path from root
        int[] path = getIntArray(canyon.length, false);

        // starting at the beginning, we are assuming the starting place cannot be null
        if (canyon[0] == 0){
            System.out.println("failure");
            return;
        }

        // start by adding the root to "known" paths
        int root = 0;
        cost[root] = 0;
        known[root] = true;
        // do not need to calculate path to root

        //now the traverse the canyon, how far can we jump at first?
        int maxJump = canyon[root];

        //lets find every node we can jump to that's not a dragon
        for(int jump = 1; jump <= maxJump; jump++){
            int leap;

            //we need to handle the case of jumping beyond the canyon, which should map to a sngle "node"
            //this is handled in our cost, path, and known arrays
            if (root + jump >= canyon.length){
                leap = canyon.length;
            } else {
                leap = root + jump;
            }

            if (!known[leap]){
                // we can jump here! lets set the cost and path to reachable nodes

                //our "so far" best path to this node has gone up by one jump
                //including root here to show that's its a jump from root
                cost[leap]++;
                path[leap] = root;
            }

            // we've already passed the end of the canyon, we're done
            if(leap == canyon.length)
                break;
        }

        // now we traverse the canyon until we've discovered every node, and know its shortest path
        // one invariant of the algorithm is that once you "know" a node, you know (one of) its shortest paths
        while (remainingUnknownNodes(known)){

            //find the node with the lowest cost
            int minNextNode = getUnknownNodeWithLowestCost(known, cost);

            if (minNextNode == -1){
                // this means we couldn't find a next place to jump that wasn't a dragon
                // we're doomed!
                System.out.println("failure");
                return;
            }

            known[minNextNode] = true;

            // check if we just discovered the shortest path out
            if (minNextNode == canyon.length)
                break;

            // still searching, lets check where we can jump and see if we can update their paths
            maxJump = canyon[minNextNode];
            for(int jump = 1; jump <= maxJump; jump++){
                int leap;
                if (minNextNode + jump >= canyon.length){
                    leap = canyon.length;
                } else {
                    leap = minNextNode + jump;
                }
                if (!known[leap]){
                    int costNow = cost[leap];
                    int costNew = cost[minNextNode] + 1;

                    if (costNew < costNow){
                        cost[leap]++;
                        path[leap] = minNextNode;
                    }
                }

                // we've already passed the end of the canyon, we're done
                if(leap == canyon.length)
                    break;
            }
        }

        // lets print out our path of "nodes"
        System.out.println(printPath(path, path.length - 1));
    }

    // returns an array of ints used for tracking current paths and costs of each node
    // depending on the context
    private static int[] getIntArray(int length, boolean isCostArray){
        int[] arr = new int[length + 1]; // extra index to represent beyond the canyon
        for (int i = 0; i < length; i++){
            if(isCostArray){
                arr[i] = Integer.MAX_VALUE;
            } else {
                // path array
                arr[i] = -1;
            }
        }
        if(isCostArray){
            arr[length] = Integer.MAX_VALUE;
        } else {
            // path array
            arr[length] = -1;
        }
        return arr;
    }

    // returns a boolean array used for tracing which nodes are "known" to the algorithm
    private static boolean[] getBoolArray(Integer[] canyon, int length){
        boolean[] arr = new boolean[length + 1]; // extra index to represent beyond the canyon
        for (int i = 0; i < length; i++){
            if(canyon[i] == 0){
                // this spot has a dragon so we don't want to include it in our search
                // so we'll just say we "know" it
                arr[i] = true;
            } else {
                arr[i] = false;
            }
        }
        arr[length] = false;
        return arr;
    }

    // helper method to see if there are any remaining nodes that are unknown
    private static boolean remainingUnknownNodes(boolean[] known){
        for (int i = 0; i < known.length; i ++){
            if (known[i] == false)
                return true;
        }
        return false;
    }

    // helper method used to get the next node in the shortest path algorithm
    private static int getUnknownNodeWithLowestCost(boolean[] known, int[] cost){
        int minCost = Integer.MAX_VALUE;

        int minNode = -1;

        for(int i = 0; i < known.length; i++){
            if (!known[i] && cost[i] < minCost){
                minCost = cost[i];
                minNode = i;
            }
        }
        return minNode;
    }


    // helper method that prints the path
    private static String printPath(int[] path, int index){
        if (index == 0){
            return Integer.toString(index);
        } else {
            String str = index == path.length - 1 ? "out" : Integer.toString(index);

            return printPath(path, path[index]) + ", " + str;
        }
    }

    //helper method that gets input from STDIN
    private static Integer[] getInput(){
        Scanner in = new Scanner(System.in);

        LinkedList<Integer> initialNumbers = new LinkedList<Integer>();
        while(in.hasNextInt()) {
            initialNumbers.add(in.nextInt());
        }
        Integer[] canyon = new Integer[initialNumbers.size()];

        for (int i = 0; i < canyon.length; i++){
            canyon[i] = initialNumbers.get(i);
        }

        return canyon;
    }
}

Answer 1

我假设你签了保密协议如果你通过HackerRank..。在这种情况下，你可能不应该在Stackoverflow上发布你的解决方案，无论你是通过还是失败。

这种解决方案的效率很低，因为您不必要地使用了Dijkstra的算法-可以在不知道数组中每个索引的成本的情况下找到解决方案。“更聪明地工作，而不是更努力地工作”是一句恰当的格言。像这样的问题可以这样解决，第一个得到的答案是最好的。