統計存儲在一個數組中的所有相鄰節點的列表

Question

有很多天真的方法來解決這個問題，但我正在尋找一個好的解決方案。您有一個函數foo（int a，int b），如果'a'與'b'相鄰'則返回true，如果'a'是'false'，則返回false不與'b'相鄰。你有這樣一個數組[1,4,5,9,3,2,6,15,89,11,24]，但實際上有一個很長的長度，如120，並且會一遍又一遍地重複（其遺傳算法適應度函數），這就是爲什麼效率很重要。

我想要一個函數，它返回數組中每個可能的'list'列表的長度，但不包括'lists'，它只是一個較大列表的子集。例如，如果foo（1,4） - > true，foo（4,5） - > true，foo（5,9） - > false，foo（9,3）& foo（3,2） ）& foo（2,6），foo（6,15） - > true，則有'lists'（1,4,5）和（9,3,2,6），所以長度爲3和4. I不想讓它返回（3,2,6），因爲這只是9,3,2,6的子集。

謝謝。

編輯

對不起，我才意識到我沒有解釋整個問題，剩下的部分是什麼，是如此困難。讓我們重新開始。忘記第一篇文章。這會讓我們感到困惑。假設有一個函數foo（int [] array），如果該數組是「好」數組，則返回true;如果該數組是「壞」數組，則返回false。什麼使它好或壞在這裏並不重要。

鑑於完整數組[1,6,8,9,5,11,45,16,9]，可以說子數組[1,6,8]是一個「好」數組，[9,5 ，11,45]是一個「好」的陣列。此外[5,11,45,16,9]是一個「好」陣列，也是最長的「好」子陣列。注意雖然[9,5,11,45]是一個「好」數組，而[5,11,45,16,9]是一個「好」數組，[9,5,11,45,16,9] ]是一個「壞」數組。

我們想要所有「好」數組的長度計數，但不是「好」數組的子數組。此外，如上所述，一個「好」數組可能會在另一個「好」數組的中間開始，但這兩者的組合可能是「壞」數組。

Answer 1

我覺得這個O(n)算法能做到你想要的。我懷疑你可以做得更快，因爲你必須分析每個元素。

count = 1; 
for each index i from 1 to N 
    if (foo(array[i-1], array[i]) == true) 
     ++count; 
    else 
     print count; 
     count = 1; 

這工作，因爲如果一定數量打破鄰接鏈，那麼所有的數字，打破了鏈可以是長鏈的一部分，在號碼前，所以你還不如從該點繼續。

這個工作在你的例子：

例如，如果FOO（1,4） - >真，FOO（4,5） - >真，FOO（5,9） - >假， foo（9,3）& foo（3,2）& foo（2,6），foo（6,15） - > true，則有'lists'（1,4,5）和（9,3， 2,6），所以長度爲3和4。我不希望它返回（3,2,6），因爲這只是一個子集9,3,2,0

foo（1,4） - > true - > count = 2
FOO（1,5） - >真 - >計數= 3
FOO（5,9） - >假 - >print 3，計數= 1個
FOO（9,3） - >真 - >計數= 2
FOO（3，2） - >真 - >計數= 3
FOO（2，6） - >真 - >計數= 4
FOO（6，15） - >真 - >計數= 5

數組結束，只是打印計數，所以print 5。我猜你的例子是錯誤的，因爲(9, 3, 2, 6)是(9, 3, 2, 6, 15)一個子集...

Answer 2

這是，我認爲，在類的可以在一個單一的傳球來解決時間最長的串式的問題（在O(n)） ，只要你有這樣的屬性，如果從A到B的子數組是「好的」，那麼任何更小的子數組也是好的。

該算法是這樣的：

• 啓動與由所述第一元件的子陣列（或一對，或任何最短的單元是）。
• 3月份的子陣列向前（即推進子陣列的開始和結束），直到你得到「好」的答案。
• 推進子陣列的結束，直到你得到答案「不好」。在你得到「壞」之前的子陣列是那個位置上最長的好子陣列 - 數它（或者保存它，或者你希望用它做的任何事情）。
• 現在推進子陣列的開始，直到你得到答案「好」;如果您趕上子陣列的末尾，則向前滑動兩個向前。然後重複上一步。
• 當你的子數組的末尾碰到你的完整數組的末尾時，你就完成了。