统计存储在一个数组中的所有相邻节点的列表

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月份的子阵列向前（即推进子阵列的开始和结束），直到你得到“好”的答案。
• 推进子阵列的结束，直到你得到答案“不好”。在你得到“坏”之前的子阵列是那个位置上最长的好子阵列 - 数它（或者保存它，或者你希望用它做的任何事情）。
• 现在推进子阵列的开始，直到你得到答案“好”;如果您赶上子阵列的末尾，则向前滑动两个向前。然后重复上一步。
• 当你的子数组的末尾碰到你的完整数组的末尾时，你就完成了。