2

我正在尝试为我遇到类似问题的问题找到解决方案

  1. A > B
  2. B > C
  3. B > D
  4. C > D

我应该得到 A > B > C > D 的答案。

这个问题的条件

  1. 输出将涉及所有元素。
  2. 该问题不会有任何虚假输入。例如，(A>B) (C>D) 是虚假输入，因为我们无法确定输出。
  3. 输入可以是任意大小，但绝不是虚假的，并且总会有解决问题的方法。

我需要使用 Java Collections 找到最佳解决方案。欢迎任何提示/提示。

提前致谢！

4

4 回答 4

8

它被称为拓扑排序。 http://en.wikipedia.org/wiki/Topological_sorting

鉴于此，您应该能够自己完成作业。

于 2010-02-11T13:48:37.520 回答
1

我打赌你最近在这门课上介绍了图表……
你认为图表可以如何应用在这里？
你能想出一个基于问题输入（A>B>、A>D、C>A 等）构建的结构吗？也许某种有向图...

一旦在这样的图表中表达了问题，解决方案将涉及导航该图表......

于 2010-02-11T13:53:06.783 回答
0

你开始把它们放在一个List. 该列表将被排序，因此对于第nth pair (a, b)，您a使用二分搜索查找。如果它已经存在，则跳过，如果不存在，则在适当的位置插入。由于a > b，您b在列表的其余部分再次执行此操作。希望这有帮助。

于 2010-02-11T13:54:08.547 回答
0

You can do this with a Map of the inputs and a recursive method that adds it's answer to a returned List (or just prints each node as it descends the tree.) If you are returning the answer then pre-pending to the returned list will prevent the answer from being reversed D->C->B->A when complete (or you can just .reverse() the list at the end.) Don't forget to test for a break condition when recursing. (hint: key not found)

于 2010-02-11T15:24:51.967 回答