设计一个比较器来排列单词，以便每个单词的最后一个字母是下一个单词的第一个字母？

好吧，所以我有一个程序，其中包含我需要的一部分“排列这些词，使列表中每个项目的最后一个字母是下一个项目的第一个字母，这是一个由最后一个链接在一起的单词链和第一个字母。“设计一个比较器来排列单词，以便每个单词的最后一个字母是下一个单词的第一个字母？

样本输入是狗，大象，长颈鹿，犀牛，老虎和正确的输出是狗，长颈鹿，大象，老虎，犀牛而我的输出是老虎，犀牛，狗，长颈鹿，大象。

的比较是这样的：

class linkedSort implements Comparator { 
    //will return 1 for a match 
    //returns 0 if no match 

    public int compare(Object t, Object t1) { 
     char[] charArr1 = t.toString().toCharArray(); 
     char[] charArr2 = t1.toString().toCharArray(); 

     if (charArr1[charArr1.length - 1] == charArr2[0]) { 
      return -1; 
     } else { 
      return 1; 
     } 
    } 
}

任何帮助将大大appriciated！

来源

2012-02-15 Samuel French

你的问题是什么？ – SLaks 2012-02-15 21:50:26

你的第一个问题是你的评论说返回1或0，并且方法返回-1或1.另外，正如@SLaks所说的，请描述你已经尝试了什么，以及它是如何失败/意外执行的。 – Thomas 2012-02-15 21:53:24

你不能用简单的比较器和排序来解决这个问题，因为比较没有定义一个total order。全序是一个在以下四个属性持有：

自反性：X ≤ x是总是如此。
反对称：如果x ≤ y和x ≠ Y，则y ≤ x是不正确的。
及物：如果x ≤ y和y ≤ Z，则x ≤Ž
整体性：对于任何x和y中，x ≤ Y的至少一种和y ≤ X成立。

您的订单不是全部订单。首先，它打破了反身性：例如，“a”≤“a”。其次，它打破反对称：“缓和”≤“前夕”和“前夕”≤“缓解”。第三，它打破了传递性：“东”≤“茶”和“茶”≤“阿弗尔”，但“东”≤“阿弗尔”是错误的。最后，它不是总数：“东”不小于“西”，“西”不小于“东”。

要解决此问题，您需要采用不同的方法。作为提示，您可能想将问题看作一个图形，其中字母是节点，单词是连接开始和结束字母的边。你能在这个图表中找到一条路径，每条边缘只访问一次？

希望这会有所帮助！

来源

2012-02-15 21:51:19 templatetypedef

+1，很好的解释。 – Perception 2012-02-15 22:14:55

如果你希望用sort做到这一点，那么这将无法正常工作。比较器需要对集合总共订购，但您的要求不是这样的。

来源

2012-02-15 21:51:30

Comparator方法不起作用。排序只使用本地比较，但问题是全局“优化”。

为了说明，这里是Arrays.sort(array, comparator)的实际比较。请注意，一些掉期打破了之前做出的正确选择，因为它们只有本地知识。

start: dog,elephant,giraffe,rhinoceros,tiger 

dog, elephant (swap) 

-> elephant,dog,giraffe,rhinoceros,tiger 

dog, giraffe (OK) 

-> elephant,dog,giraffe,rhinoceros,tiger 

giraffe, rhinoceros (swap) 

-> elephant,dog,rhinoceros,giraffe,tiger 

dog, rhinoceros (swap) 

-> elephant,rhinoceros,dog,giraffe,tiger 

elephant, rhinoceros (swap) 

-> rhinoceros,elephant,dog,giraffe,tiger 

giraffe, tiger (swap) 

-> rhinoceros,elephant,dog,tiger,giraffe 

dog, tiger (swap) 

-> rhinoceros,elephant,tiger,dog,giraffe 

elephant, tiger (OK) 

-> rhinoceros, elephant, tiger, dog, giraffe

来源

2012-02-15 21:53:32 DNA

这等效于这样的问题：Detecting when matrix multiplication is possible

创建节点对每个字母
加入两个字母与相应的动物的有向边（允许同一顶点对之间的多个边缘）
找到Eularian足迹

来源

2012-02-15 21:55:53 ElKamina

我不认为他的图是Eularian。我想他想要一个汉密尔顿电路来访问每个单词一次（但是，如果单词尾的末尾不需要连接到单词尾的开头，那么他需要最长的路径，它不会使用同一个节点两次，其中单词是节点） – 2012-02-15 23:25:44

@robertking这取决于你如何制定它。如果你将单词表达为节点，你需要找到哈密尔顿电路，这是一个NP完全问题。如果你将单词表达为边缘，那么你需要找到接近线性时间的尤拉路径。 – ElKamina 2012-02-15 23:30:58

我明白了，你说的是欧拉足迹而不是欧拉赛道。但我认为你不需要遍历所有的边缘。例如“蚂蚁，羚羊，蟾蜍，谜”，谜将对蚂蚁和羚羊都有优势，但你只能使用其中一条边 – 2012-02-15 23:41:11

设计一个比较器来排列单词，以便每个单词的最后一个字母是下一个单词的第一个字母？

回答

相关问题