java - 确定从最高平台到第 i 个平台所需的最少跳跃次数

Question

一排有N个平台，每个平台都有一个独特的高度。您以大小为 N 的数组 A 的形式给出平台，其中第 i 个平台的高度为 A[i] (1<=i<=N)。您可以执行以下操作：

如果你站在第 i 个平台上，你可以在任何第 j 个平台上跳跃，使得第 i 个平台的高度大于第 j 个平台的高度，并且在第 i 个和第 j 个平台之间没有平台高度大于第 j 个平台。

确定从最高平台到第 i 个平台所需的最小跳跃次数（对于每个有效的 i）

笔记

您必须独立回答每个有效的 i。

• 假设基于 1 的索引，

• 每个平台的高度都是独一无二的。

解释

第一行包含测试用例的数量，T = 2。

对于第一个测试用例

给定

N = 4

A = [13, 5]

方法

• 对于第一个平台，从第二个平台直接跳到第一个平台。因此需要 1 次跳跃。

• 对于第二个平台，您已经在第二个平台上，因此需要0 次跳跃。

对于第二个测试用例

给定

• N = 5

• A = [5, 1, 3, 4,7]

方法

• 对于第一个平台，从第五个平台直接跳到第一个平台。因此需要 1 次跳跃。

• 对于第 2 个平台，从第 5 个平台跳到第 1 个平台，然后跳到第 2 个平台。因此需要 2 次跳跃。

• 对于第 3 个平台，从第 5 个平台跳到第 4 个平台，然后跳到第 3 个平台。因此需要 2 次跳跃。

• 对于第4 个平台，从第5 个平台直接跳到第4 个平台。因此需要 1 次跳跃。

• 对于第 5 个平台，您已经在第 5 个平台上，因此需要 0 次跳跃。

我试图解决这个问题，但无法找到正确的解决方案。谁能帮我解决它。

//Function to find the index of max number in array
    static int Tallest(int[] arr)
 {
   //since have to use 1based indexing
     int max = 0;

     for (int i = 1; i < arr.length; i++)
         if (arr[i] > arr[max])
             max = i;

     return max;
 }  
                         
static int[] Min_Jumps(int N, int[] A)
 {
   int[] result = {0};
   int count = 0;
   int tall = Tallest(A);
     for(int i=1;i<N;i++)
      {
     if(i == tall)
       {
         result[i] = 0;
       }
     else 
         {
             count = tall - i;
             result[i] = count;
         }
     }
      return result;
  }

标签： javac#algorithm

Answer 1

这是一个有趣的测验任务！希望我能解决你的问题。我用一个类Node解决了这个问题，以创建平台的树状表示。一个Node的 ArrayList childNodes包含所有可以通过一次跳转到达的下一个平台。

class Node {
    int value;
    ArrayList<Node> childNodes = new ArrayList<>();

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" + value + "}";
    }
}

要运行算法，只需从main()调用Min_Jumps()函数。

static int[] Min_Jumps(int N, int[] A) {
    ArrayList<Node> nodeList = createNodeList(A);
    assignChildNodes(nodeList);

    // Optional print of created Node Structure
    // printNodeStructure(nodeList);

    int[] result = new int[N];
    Node startNode = nodeList.get(Tallest(A));

    // Get number of jumps to reach each platform
    for (int platform = 0; platform < nodeList.size(); platform++) {
        Node destination = nodeList.get(platform);
        for (int jumps = 0; jumps < nodeList.size(); jumps++) {
            HashSet<Node> nextReachableNodes = reachableNodesFromNodeWithJumps(startNode, jumps);
            if (nextReachableNodes.contains(destination)) {
                result[platform] = jumps;
                break;
            }
        }
    }

    // Print results
    for (int e : result) {
        System.out.println(e);
    }
    return result;
}

static ArrayList<Node> createNodeList(int[] arr) {
    ArrayList<Node> nodeList = new ArrayList<>();
    for (int e : arr) {
        nodeList.add(new Node(e));
    }
    return nodeList;
}

static void assignChildNodes(ArrayList<Node> nodeList) {
    for (int outerNodeIndex = 0; outerNodeIndex < nodeList.size(); outerNodeIndex++) {
        Node outerNode = nodeList.get(outerNodeIndex);
        for (int innerNodeIndex = 0; innerNodeIndex < nodeList.size(); innerNodeIndex++) {
            Node innerNode = nodeList.get(innerNodeIndex);
            if (outerNode.value > innerNode.value) {
                List<Node> sublist;
                if (outerNodeIndex < innerNodeIndex) {
                    sublist = nodeList.subList(outerNodeIndex + 1, innerNodeIndex);
                } else {
                    sublist = nodeList.subList(innerNodeIndex + 1, outerNodeIndex);
                }
                if (sublist.size() == 0) {
                    outerNode.childNodes.add(innerNode);
                } else {
                    loop:
                    {
                        for (Node element : sublist) {
                            if (element.value > innerNode.value) {
                                break loop;
                            }
                        }
                        outerNode.childNodes.add(innerNode);
                    }
                }
            }
        }
    }
}

static HashSet<Node> reachableNodesFromNodeWithJumps(Node node, int jumps) {
    HashSet<Node> nextReachableNodes = new HashSet<>();
    nextReachableNodes.add(node);
    while (jumps > 0) {
        ArrayList<Node> nextNodes = new ArrayList<>();
        nextReachableNodes.forEach(n -> nextNodes.addAll(n.childNodes));
        nextReachableNodes.addAll(nextNodes);
        jumps -= 1;
    }
    return nextReachableNodes;
}

static void printNodeStructure(ArrayList<Node> nodes) {
    for (Node node : nodes) {
        System.out.println(node.toString());
        System.out.println("Childs:");
        node.childNodes.forEach(childNode -> System.out.println(childNode.toString()));
        System.out.println("-------------");
    }
}

//Function to find the index of max number in array
static int Tallest(int[] arr) {
    //since have to use 1based indexing
    int max = 0;

    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > arr[max]) {
            max = i;
        }
    }
    return max;
}