algorithm - 在采访中无法弄清楚这一点。找到这个数组中的最小循环？

Question

我需要找到最小循环的长度。比如[1, 2, 1, 2]的循环长度为2。那么[1, 2, 1, 2, 1]的最小长度为2。那么1, 2, 1, 2的长度, 3 应该是 5 因为整个列表没有重复(我不知道为什么这应该是 5)。 1, 2, 1, 2, 1, 1, 2的最小长度为5。

这是我尝试做的:1.使用Dijkstra的算法，然后遍历路径找到最小长度cyle2.我试着有一个慢指针和快指针，然后我找到了循环。然后，我再次遍历循环以找到循环的总长度。我也有一套不再通过相同的数字。任何帮助将不胜感激。

Answer 1

有点不清楚“最小循环”的含义。话虽如此，我想你可能有点想多了。考虑它的一种更简单的方法是考虑偏移量。例如，给定一个数组 [1, 2, 1, 2, 1]，您可以考虑当偏移给定数量时此数组匹配的方式。当它偏移两个时，它完美地对齐:

offset = 2 cycle = [1, 2]
[1, 2, 1, 2, 1]
      [1, 2, 1, 2, 1]

offset = 5 cycle = [1, 2, 1, 2, 1]
[1, 2, 1, 2, 1, 1, 2]
               [1, 2, 1, 2, 1, 1, 2]

考虑到这一点，蛮力算法就很清楚了:

function findCycle(arr) {
  let offset = 1;

  while (offset < arr.length) {
    let suffix = arr.slice(offset)
    // compare - does the array match everywhere with this offset
    let matches = suffix.every((n, i) => n === arr[i])
    // is so this is the smallest cycle
    if (matches) break
    offset++
  }
  console.log(offset)
}

findCycle([1, 2, 1, 2, 3, 1, 2])
findCycle([1, 2, 1, 2, 1])
// degenerate case:
findCycle([1])
findCycle([]) // 1 but maybe should be zero?