javascript - 查找数组元素索引和值的最长链

Question

我解决不了问题。
我们有一个数组。如果我们取一个值，它的索引表示端口 ID，而值本身表示它连接到的另一个端口 ID。需要找到与值为-1的元素的最长顺序连接的起始索引。
我做了一个图形解释来描述数组 [2, 2, 1, 5, 3, -1, 4, 5, 2, 3] 的情况。在图像上，最长的连接是紫色的(3 段)。

我需要通过函数 getResult(connections) 来解决用一个论点。我不知道该怎么做，所以我决定返回另一个带有几个参数的函数，这让我可以做出递归解决方案。

function getResult(connections) {
  return f(connections.findIndex(e => e === -1), connections, 0, []);
}

function f(index, cnx, counter, branches) {
  counter++;  
  for (let i = 0; i < cnx.length; i++) {
    if (cnx[i] === index) {
      branches.push([i, counter]);
      return f(i, cnx, counter, branches);
    }
  }
  return branches.sort((a, b) => b[1] - a[1])[0][0];
}

console.log(getResult([1, 2, -1])); // expected 0
console.log(getResult([1, -1, 1, 2])); // expected 3
console.log(getResult([2, 1, -1])); // expected 0
console.log(getResult([3, 4, 1, -1, 3])); // expected 2
console.log(getResult([1, 0, -1, 2])); // expected 3
console.log(getResult([3, 2, 1, -1])); // expected 0
console.log(getResult([2, 2, 1, 5, 3, -1, 4, 5, 2, 3])); // expected 6

无论如何，代码不能完全正常工作。
你能解释一下我的错误吗？
是否可以通过仅具有一个原始参数的函数来解决问题？

Answer 1

The code doesn't work completely properly. Would you please explain my mistakes?

你非常接近。主要问题是 return递归调用前面的关键字终止 for循环和整个 f过早发挥作用。这将导致它仅访问第一个可能分支上的节点，而不是所有节点。
另一个问题是 branches函数结束时可能为空，但您仍然可以访问 [0][0] .而是从 f 返回整个数组, 并访问 getResult 中的第一个元组.
这两个小修复已经使函数工作1:

function getResult(connections) {
  return f(connections.findIndex(e => e === -1), connections, 0, [])[0][0];
}

function f(index, cnx, counter, branches) {
  counter++;  
  for (let i = 0; i < cnx.length; i++) {
    if (cnx[i] === index) {
      branches.push([i, counter]);
      f(i, cnx, counter, branches);
    }
  }
  return branches.sort((a, b) => b[1] - a[1]);
}

console.log(getResult([1, 2, -1])); // expected 0
console.log(getResult([1, -1, 1, 2])); // expected 3
console.log(getResult([2, 1, -1])); // expected 0
console.log(getResult([3, 4, 1, -1, 3])); // expected 2
console.log(getResult([1, 0, -1, 2])); // expected 3
console.log(getResult([3, 2, 1, -1])); // expected 0
console.log(getResult([2, 2, 1, 5, 3, -1, 4, 5, 2, 3])); // expected 6

1:实际上，有一个边缘情况它仍然不起作用:当在空数组上调用为 getResult([]) 时, 如果 branches 不应该抛出异常是空的。这可以通过使用 if 专门处理该情况来解决。条件，或通过包含元组 [-1, 0] (无节点，距离 0)在 branches .
额外的改进是在 getResult 的末尾只进行一次排序。 , 并直接使用 f(-1, connections, 0, []); 开始搜索而不是使用 findIndex .

Is it possible to solve the problem by a function with just one original argument? I don't know how to do it, so i decided to return another function with several arguments which allows me to make a recursive solution.

引入辅助函数是一个完全合适的解决方案，这种方法很好!
虽然总是可以将递归方案编写为带有显式堆栈的循环，但这通常是笨拙且难以理解的。与 DFS approach您选择了，递归函数是编写它的最简单和最干净的方法。
如果你不想创建额外的全局变量，你甚至可以在 getResult 中声明你的辅助函数。 .这也允许访问 connections直接从上层作用域，而不是将其作为函数参数传入。对 branches 也可以这样做。多变的:

function getResult(connections) {
  const branches = [];
  function f(index, distance) {
    branches.push([index, distance]);
    for (let i = 0; i < connections.length; i++) {
      if (connections[i] === index) {
        f(i, distance+1);
      }
    }
  }
  f(-1, 0);
  branches.sort((a, b) => b[1] - a[1]);
  return branches[0][0];
}

console.log(getResult([1, 2, -1])); // expected 0
console.log(getResult([1, -1, 1, 2])); // expected 3
console.log(getResult([2, 1, -1])); // expected 0
console.log(getResult([3, 4, 1, -1, 3])); // expected 2
console.log(getResult([1, 0, -1, 2])); // expected 3
console.log(getResult([3, 2, 1, -1])); // expected 0
console.log(getResult([2, 2, 1, 5, 3, -1, 4, 5, 2, 3])); // expected 6

至于进一步的替代方案和优化:

您可以使用迭代 BFS有一个队列。请注意，尽管您的输入格式通常是图形，但您将遍历的连接组件保证是一棵以 -1 为根的树。 ，每个子节点都指向它的父节点，永远不会形成一个圆圈(因为没有节点 -1 指向任何地方)。

与其在列表中保留所有“分支”(节点索引及其距离)，不如只保留迄今为止遇到的最大距离的那个。

而不是反复迭代 connections数组来查找节点的子节点( i 引用当前 index )，在 connections 的单次迭代中构建实际的树结构，然后遍历该树以找到最深的分支。