設計一個比較器來排列單詞，以便每個單詞的最後一個字母是下一個單詞的第一個字母？

好吧，所以我有一個程序，其中包含我需要的一部分「排列這些詞，使列表中每個項目的最後一個字母是下一個項目的第一個字母，這是一個由最後一個鏈接在一起的單詞鏈和第一個字母。「設計一個比較器來排列單詞，以便每個單詞的最後一個字母是下一個單詞的第一個字母？

樣本輸入是狗，大象，長頸鹿，犀牛，老虎和正確的輸出是狗，長頸鹿，大象，老虎，犀牛而我的輸出是老虎，犀牛，狗，長頸鹿，大象。

的比較是這樣的：

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

設計一個比較器來排列單詞，以便每個單詞的最後一個字母是下一個單詞的第一個字母？

回答

相關問題