java - 计算存储在数组中的所有相邻节点列表

Question

这个问题有很多简单的方法，但我正在寻找一个好的解决方案。这是问题(将在 Java 中实现):

您有一个函数 foo(int a, int b)，如果“a”与“b”“相邻”则返回 true，如果“a”不与“b”相邻则返回 false。你有一个像这样的数组 [1,4,5,9,3,2,6,15,89,11,24]，但实际上它的长度很长，比如 120，并且会一遍又一遍地重复(它是一个遗传算法适应度函数)这就是效率很重要的原因。

我想要一个函数来返回数组中每个可能的邻接“列表”的长度，但不包括“列表”，它们只是更大列表的子集。

例如，如果 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，然后有“列表”(1,4,5) 和 (9,3,2,6)，所以长度为 3 和 4。我不但是，我希望它返回 (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;

这是可行的，因为如果某个数字打破了邻接链，那么打破链的数字之前的任何数字都不能成为更长链的一部分，因此您不妨从那一点继续。

在您的示例中进行此操作:

For example, if 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, then there are 'lists' (1,4,5) and (9,3,2,6), so length 3 and 4. I don't want it to return (3,2,6), though, because this is simply a subset of 9,3,2,6

foo(1, 4) -> 真 -> 计数 = 2
foo(1, 5) -> 真 -> 计数 = 3
foo(5, 9) -> false -> 打印 3, count = 1
foo(9, 3) -> 真 -> 计数 = 2
foo(3, 2) -> 真 -> 计数 = 3
foo(2, 6) -> 真 -> 计数 = 4
foo(6, 15) -> 真 -> count = 5

数组结束，只打印计数，所以打印 5。我猜你的例子是错误的，因为 (9, 3, 2, 6) 是 (9, 3, 2, 6, 15) 的子集。 .