Codility - 国家网络，如何解决它

Question

我试图采取编码测试，我堆放在第一次测试。任何人都有机会拥有这一款，并可以指出我的正确方式？我已经为城市建立了阵容，可以从每个城市进行访问，并对其进行排序，以便能够在其上散步。它适用于我的绘图，但我有一些问题来实现它。

对于给定的城市数组：

T[0] = 1 
    T[1] = 2 
    T[2] = 3 
    T[3] = 3 
    T[4] = 2 
    T[5] = 1 
    T[6] = 4 

我已经创建了如下的步行数组，其中第一个数字是当前城市和在括号中的数字是可能的方式：0[1], 1[0,2,5],2[1,3,4],3[2],4[2,6],5[1],6[4]。但在此之后，我无法弄清楚如何去做。

这是我

一个国家的网络由N个城市和N的问题 - 1路连接它们给出。城市在[0 ..（N - 1）]范围内标有不同的整数。道路将城市连接起来，使得每一对不同的城市通过直接的道路或通过由直接道路组成的道路相连。从任何其他城市到达任何城市都有一条途径。

从城市K出发，你必须计划一系列的日常旅行。你每天都想要访问以前未访问的城市，在通往该城市的路线上，你还将经过其他未访问城市的最大数量（这将被视为已访问过）。我们说目的地城市是我们的日常旅行目标。

在平局的情况下，您应该选择最小标签的城市。每个城市至少参观过一次，这些旅行就会停止。

例如，考虑K = 2和由七个城市和六条公路下面的网络：

你开始在全市2.从这里您做出以下车次：

day 1 − from city 2 to city 0 (cities 1 and 0 become visited), 
    day 2 − from city 0 to city 6 (cities 4 and 6 become visited), 
    day 3 − from city 6 to city 3 (city 3 becomes visited), 
    day 4 − from city 3 to city 5 (city 5 becomes visited). 

目标是要找出旅行目标的顺序。在上面的例子中，我们有以下旅行目标：（2，0，6，3，5）。

struct Results { 
    int * D; 
    int X; 
}; 

写功能：

struct Results solution(int K, int T[], int N); 

，鉴于非空零索引阵列T由N个整数描述n个城市的一个网络和N - 1条道路，返回的序列旅行目标。

阵列T描述了城市网络如下：

if T[P] = Q and P ≠ Q, then there is a direct road between cities P and Q. 

例如，给定包括七个要素的以下数组T（此数组描述上面所示的网络）和K = 2：

T[0] = 1 
T[1] = 2 
T[2] = 3 
T[3] = 3 
T[4] = 2 
T[5] = 1 
T[6] = 4 

函数应该返回的序列[2，0，6,3，5]，如上所述。

假设：

N is an integer within the range [1..90,000]; 
    each element of array T is an integer within the range [0..(N−1)]; 
    there is exactly one (possibly indirect) connection between any two distinct roads. 

复杂性：

expected worst-case time complexity is O(N); 
    expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). 

输入数组的元素可以被修改。

Answer 1

我解决了这个问题上Quora的位置：http://www.quora.com/Algorithms/How-do-I-determine-the-order-of-visiting-all-leaves-of-a-rooted-tree-so-that-in-each-step-I-visit-a-leaf-whose-path-from-root-contains-the-most-unvisited-nodes#

Java代码：

import java.util.*; 

public class LeafOrder { 
    public static void main(String[] args) { 
     /*********************************************************************\ 
     * Build tree              * 
     \*********************************************************************/ 

     final int n = 16; 
     TreeNode[] nodes = new TreeNode[n]; 

     for (int i = 0; i < n; i++) { 
      nodes[i] = new TreeNode(i); 
     } 

     // Level 1 
     TreeNode root = nodes[9]; 

     // Level 2 
     root.addChild(nodes[8]); 
     root.addChild(nodes[2]); 
     root.addChild(nodes[13]); 

     // Level 3 
     nodes[8].addChild(nodes[10]); 
     nodes[2].addChild(nodes[1]); 
     nodes[2].addChild(nodes[0]); 
     nodes[13].addChild(nodes[7]); 

     // Level 4 
     nodes[0].addChild(nodes[14]); 
     nodes[0].addChild(nodes[15]); 
     nodes[0].addChild(nodes[5]); 
     nodes[0].addChild(nodes[6]); 
     nodes[7].addChild(nodes[11]); 

     // Level 5 
     nodes[15].addChild(nodes[4]); 
     nodes[11].addChild(nodes[12]); 

     // Level 6 
     nodes[4].addChild(nodes[3]); 

     /*********************************************************************\ 
     * Preprocessing              * 
     \*********************************************************************/ 

     preprocessDeepestReachingChildren(root); 

     /*********************************************************************\ 
     * Level-by-level traversal           * 
     \*********************************************************************/ 

     Queue<NodeRank> queue = new LinkedList<NodeRank>(); 
     queue.offer(new NodeRank(root, 0)); 

     List<List<Integer>> rank = new ArrayList<List<Integer>>(n); 
     boolean[] valueIsLeaf = new boolean[n]; 
     int[] valueToRank = new int[n]; 
     int[] rankToIndex = new int[n]; 

     for (int i = 0; i < n; i++) { 
      rank.add(new ArrayList<Integer>()); 
     } 

     while (!queue.isEmpty()) { 
      NodeRank dequeued = queue.poll(); 
      TreeNode currentNode = dequeued.getNode(); 
      int currentValue = currentNode.getValue(); 
      int currentRank = dequeued.getRank(); 
      ArrayList<TreeNode> children = currentNode.getChildren(); 
      TreeNode deepestReachingChild = currentNode.getDeepestReachingChild(); 
      int numChildren = children.size(); 

      if (numChildren == 0) { 
       List<Integer> rankList = rank.get(currentRank); 
       rankList.add(currentValue); 

       valueToRank[currentValue] = currentRank; 
       valueIsLeaf[currentValue] = true; 
      } 

      for (int i = 0; i < numChildren; i++) { 
       TreeNode currentChild = children.get(i); 
       int currentChildRank = 1 + ((currentChild == deepestReachingChild) ? currentRank : 0); 

       queue.offer(new NodeRank(currentChild, currentChildRank)); 
      } 
     } 

     /*********************************************************************\ 
     * Building answer in sorted order         * 
     \*********************************************************************/ 

     for (int i = n - 1, currentIndex = 0; i >= 0; i--) { 
      List<Integer> rankList = rank.get(i); 
      int rankListSize = rankList.size(); 

      if (rankListSize == 0) { 
       continue; 
      } 

      rankToIndex[i] = currentIndex; 
      currentIndex += rankListSize; 
     } 

     int[] answer = new int[n]; 
     int highestIndexSet = 0; 

     for (int i = 0; i < n; i++) { 
      if (!valueIsLeaf[i]) { 
       continue; 
      } 

      int rankForValue = valueToRank[i]; 
      int indexForRank = rankToIndex[rankForValue]; 

      rankToIndex[rankForValue]++; 

      answer[indexForRank] = i; 
      highestIndexSet = Math.max(highestIndexSet, indexForRank); 
     } 

     /*********************************************************************\ 
     * Outputting answer             * 
     \*********************************************************************/ 

     for (int i = 0; i <= highestIndexSet; i++) { 
      System.out.print(answer[i] + ((i != highestIndexSet) ? ", " : "")); 
     } 

     System.out.println(); 
    } 

    public static int preprocessDeepestReachingChildren(TreeNode root) { 
     return preprocessDeepestReachingChildren(root, 0); 
    } 

    public static int preprocessDeepestReachingChildren(TreeNode root, int depth) { 
     int maxDepth = 0; 
     TreeNode maxChild = null; 
     ArrayList<TreeNode> children = root.getChildren(); 
     int numChildren = children.size(); 

     if (numChildren == 0) { 
      return depth; 
     } 

     for (int i = 0; i < numChildren; i++) { 
      TreeNode currentChild = children.get(i); 
      int currentChildDepth = preprocessDeepestReachingChildren(currentChild, depth + 1); 

      if (maxChild == null || currentChildDepth > maxDepth || (currentChildDepth == maxDepth && currentChild.getValue() < maxChild.getValue())) { 
       maxDepth = currentChildDepth; 
       maxChild = currentChild; 
      } 
     } 

     root.setDeepestReachingChild(maxChild); 

     return maxDepth; 
    } 
} 

class TreeNode { 
    private int value; 
    private ArrayList<TreeNode> children; 
    private TreeNode deepestReachingChild; 

    public TreeNode(int nodeValue) { 
     this.value = nodeValue; 
     this.children = new ArrayList<TreeNode>(); 
    } 

    public int getValue() { 
     return this.value; 
    } 

    public void addChild(TreeNode child) { 
     this.children.add(child); 
    } 

    public ArrayList<TreeNode> getChildren() { 
     return this.children; 
    } 

    public TreeNode getDeepestReachingChild() { 
     return this.deepestReachingChild; 
    } 

    public void setDeepestReachingChild(TreeNode child) { 
     this.deepestReachingChild = child; 
    } 
} 

class NodeRank { 
    private TreeNode node; 
    private int rank; 

    public NodeRank(TreeNode node, int rank) { 
     this.node = node; 
     this.rank = rank; 
    } 

    public TreeNode getNode() { 
     return this.node; 
    } 

    public int getRank() { 
     return this.rank; 
    } 
} 

Answer 2

我已经写在StackOverflow上和今天的职位收到了很多的帮助，我决定签下的，做我谦逊的小贡献。

我用来解决这个问题的算法是@Sir Ben Benji建议的“贪婪算法”。

我的做法是分裂“贪婪Algorith”逻辑到结构下面的Java方法如下所示：

1. A candidate set, from which a solution is created 
2. A selection function, which chooses the best candidate to be added to the solution 
3. A feasibility function, that is used to determine if a candidate can be used to contribute to a solution 
4. An objective function, which assigns a value to a solution, or a partial solution 
5. A solution function, which will indicate when we have discovered a complete solution 

这念叨“贪婪算法”下一个维基百科的链接后，被带到接近：

http://en.wikipedia.org/wiki/Greedy_algorithm

在我的代码以上说明的本功能被编码在类“TravelingGreedyAlgorythm.java”具有下列名称：

1. public void setInitialCandidates(int[] destinyCities) 
2. private PathCandidate selectNextPathDestinyCity(int originCityId) 
3. private PathCandidate selectNextPathDestinyCity(int originCityId) 
4. private void storeNextPathSolutionIfScoreIsMaximum(PathCandidate currentPath) 
5. private boolean isCompleteSolution() 

而且，因为这是需要几个数据结构，我决定类作为分割算法：

- TravelingGreedyAlgorythm: The main class containing the algorithm logic.</li> 
- CityCandidates: The set of candidate cities (contains the city graph structure)  
- PathCandidatesQueue: Wraps a queue of available paths of type pathCandidate for every iteration 
- PathCandidate: Path of cities such as [0, 1, 2, ..., N] 

现在所有您需要做的是看看实现。我还添加了一个名为测试类：

TestTravelingGreedyAlgorythm.java 

在这个类中，我添加上面给出的例子：在我的GitHub帐户

Graph: T[0] = 1 T[1] = 2 T[2] = 3 T[3] = 3 T[4] = 2 T[5] = 1 T[6] = 4 
Output sequence:</b> [2, 0, 6, 3, 5], as explained above. 

该解决方案已发行（工作）如果你有兴趣。你可以看看clicking here。

（作为初学者，我不知道是否最好在这里编写我的代码，因为它分成几个类，可能很麻烦）。

我希望它可以帮助任何人。谢谢阅读！